задачка

[avva]

Во-первых, решение задачи про светофоры, если оно кому-то интересно, есть в журнале flaass'а: вот тут (если оно непонятно из записи - загляните в комментарии, я там немного разжевал).

Во-вторых, вот новая задачка (далеко не такая сложная :)), из внутренней рассылки на работе. Странно, мне казалось, что я ее когда-то уже решал, но как ни силился, не вспомнил решения и не нашел упоминания в ЖЖ или другом месте. Может, ложная память; так или иначе, решил заново, с удовольствием (хотя, возможно, не самым экономным путем).

На лугу у фермера пасутся овцы, сбившись в группы. Фермер заметил, что ровно раз в час происходит следующее: от каждой группы отходит одна овца, и все эти отошедшие овцы вместе сбиваются в новую группу. Кроме этой операции, состав групп остается неизменен.

Через какое-то время фермер замечает, что количество и размер групп стабилизировались, т.е. после каждой операции, описанной выше, ничего не меняется.

1) Каким должно быть общее число овец, чтобы это было возможно?

2) Верно ли, что если число овец такое, как в ответе на первый вопрос, т.е. стабилизация возможна, то она обязательно произойдет?

Комментарии скрывать не буду, так что не заглядывайте, если хотите решить сами.

Небольшое пояснение. Первый вопрос совсем легкий (и в комментариях есть уже несколько верных ответов, и один с доказательством). Второй посложнее.

Comments

[gaiwan.livejournal.com]

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

[bamsic.livejournal.com]

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

[dimrub.livejournal.com]

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

[bamsic.livejournal.com]

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

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

[vitus_wagner]

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

[dimrub.livejournal.com]

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

Именно.

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

Продолжаем думать :)

вроде бы так

[nighttime-notes.livejournal.com]

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

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

[bamsic.livejournal.com]

На взятом с потолка примере - стабилизация происходит. :-)

[dimrub.livejournal.com]

Да, на вырожденных случаях (все овцы в одной куче, и каждая овца в отдельной куче) работает. Осталось обобщить.

[avva.livejournal.com]

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

[avva.livejournal.com]

Верно, но это еще тоже надо доказать.

[avva.livejournal.com]

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

[dimrub.livejournal.com]

Ну, это вроде бы доказывается по индукции. Возьмем наименьшую группу. После вычитания в ней останется на одну овцу меньше, следовательно, она (эта группа должна изчезнуть), то есть, ее величина - одна овца. После вычитания какая-то из групп должна ее заменить, следовательно есть как минимум одна группа, в которой две овцы, и так далее. Приходим к ситуации, в которой есть k групп величиной в одну, k - величиной в две, и т.п. Дальше осталось только сказать, что k = 1, поскольку иначе после перетасовки получим не группу величиной n (максимальную до перетасовки), а величиной в n*k != n.

[avva.livejournal.com]

Ага, все верно. Теперь попробуй ответить на более интересный вопрос :-)

Re: вроде бы так

[avva.livejournal.com]

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

[torquelimach.livejournal.com]

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

[avva.livejournal.com]

ага.

Re: вроде бы так

[nighttime-notes.livejournal.com]

а, ну да
1 1 2-> 3 1->2 2->1 1 2

Re: вроде бы так

[nighttime-notes.livejournal.com]

хотя нет, оно не n(n+1)/2 :)

[(Anonymous)]

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

[lenik-terenin.livejournal.com]

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

[avva.livejournal.com]

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

[dr-basf.livejournal.com]

первый вопрос - по формуле арифм прогрессии считается, а вот второй вопрос что-то не осилил (http://graphic-tutorials.ru/)

[dimks.livejournal.com]

А почему не две?
Сначала одна группа из двух овец, потом две группы по одной...

[gaiwan.livejournal.com]

:)