Или чего-то не хватило в условии (мне не хватило :)), или есть всего три овцы.

Не уверен, что именно вы не поняли :)

На первый взгляд все просто, группы должны быть такими:
1, 2, 3, 4,.. n
тогда если от всех групп отнять по одно, то получим новую группу размерностью n, при этом их общее кол-во не изменится.

По поводу №1 - я так понимаю, оно должно быть вида n*(n+1)/2

Так и есть сумма арифметической прогрессии.

Вот только как доказать, что стабилизация возможна?

Число овец должно быть треугольным.

А доказать? :)

1) чтобы число групп не менялось (именно, не росло), по крайней мере одна группа должна состоять из одной овцы
2) групп по одной овце не может быть больше 1 (иначе число групп уменьшится на следующем шаге)
3) поскольку после деления должна остаться группа ровно с одной овцой, то есть группа с двумя овцами. В силу 2), такая группа ровно одна (или ни одной, если существует только одна овца)
4) далее более-менее ясно, что состав групп 1, 2,...,n, где n>=1

что касается стабилизации - кажется верным, что произойдет

С первый вопросом все верно, да.

1) N = k(k+1)/2 для натурального k, соответствующего числу групп. Доказательство: поскольку число групп не меняется, в одной (и только одной) группе была одна овца. Поэтому (если k>1) в одной (и только одной) группе было две овцы. Далее аналогично.

ага.

две группы по две овцы. отход одной овцы эквивалентен отходу другой (если не вдаваться в психологию овец и не допрашивать, кто был инициатором отхода). овцы свингуют типа

Со стабильным количеством овец вроде уже решили. Со стабилизацией всё тоже достаточно просто, сортируем их по размеру и смотрим -- если количество групп овец больше стабильного, то обязательно найдутся две (или более) групп с одинаковым количеством овец, которые обязательно одновременно исчезнут на каком-то шаге. Соответственно, если количество групп овец меньше стабильного, то значит какая-то группа из N овец отсутствует, и через N шагов у нас не будет группы из 1ой овцы, и на этом шаге количество групп увеличится.

Кол-во групп может и возрастать, и уменьшаться со временем - возрастать, если нет групп из одной овцы (и расти долго, если нет групп с небольшим кол-вом овец); уменьшаться, если есть группы с одинаковым кол-вом овец. Ваше объяснение никак не опровергает того, что эти два явления могут происходить одновременно (и воссоздавать друг друга: как группы с размером, равным уже существующей группе, так и "дырки" могут образовываться заново).

первый вопрос - по формуле арифм прогрессии считается, а вот второй вопрос что-то не осилил

Три овцы:
шаг 0 - 1 группа в 3 овцы
шаг 1 - 2 группы - 2 и 1 овца
шаг 2 - 2 группы - 1 и 2 овцы
подходит? или я чего-то недопонял в условии?

ну это один пример стабилизации, да.

А почему именно три?
Почему понятия овцы, каждая группа и т.д. не понять - как "ненулевое множество", тогда одной овцы хватит...
Тогда и второй вопрос - тривиален :)

Похожая задача: за столом сидят семь гномов, у каждого пивная кружка с некоторым (неотрицательным) кол-вом пива в ней. Каждый из гномов по очереди распределяет все пиво из своей кружки поровну между остальными шестью гномами, после чего у них в кружках кол-во пива становится равным начальному.

Вопрос: сколько пива было у гномов в кружках изначально?

(тривиальное решение со всеми пустыми кружками не предлагать)

эксперимент показывает, что процесс устаканивается к треугольной конфигурации независимо от начальных условий за не более чем n*(n-1) итераций, при (n+1)*n/2 овцах.

что, впрочем, почти не приближает к доказательству этого факта.

задача также известна как "задача о стаканах"

http://www.sch57.msk.ru/~masha_semenova/MATH/drobi/glass.htm

ты знал! :)

украдено у mi3ch'a:

:-)