задачка

[avva]

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

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

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

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

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

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

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

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

Comments

[gaiwan.livejournal.com]

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

[avva.livejournal.com]

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

[dimks.livejournal.com]

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

[bamsic.livejournal.com]

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

[dimrub.livejournal.com]

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

[bamsic.livejournal.com]

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

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

[vitus_wagner]

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

[avva.livejournal.com]

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

вроде бы так

[nighttime-notes.livejournal.com]

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

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

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

[avva.livejournal.com]

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

[torquelimach.livejournal.com]

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

[avva.livejournal.com]

ага.

[(Anonymous)]

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

[lenik-terenin.livejournal.com]

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

[avva.livejournal.com]

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

[dr-basf.livejournal.com]

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

[syarzhuk.livejournal.com]

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

[avva.livejournal.com]

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

[programmilla.livejournal.com]

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

[phoonzang.livejournal.com]

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

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

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

[184467440737095.livejournal.com]

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

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

[lenik-r.livejournal.com]

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

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

[etre-moral-etre-sincere.blogspot.com (from livejournal.com)]

ты знал! :)

синхронизация овец со светофорами

[ex-rofer.livejournal.com]

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

Re: синхронизация овец со светофорами

[avva.livejournal.com]

:-)

Идея

[(Anonymous)]

Частный случай процесса Маркова, более известный как процес-рождения и умирания:
http://en.wikipedia.org/wiki/Birth-death_process и условия равновесия

[arhi-ebi-scop.livejournal.com]

час t : существует группа с кол. овец n = равному кол. групп в t-1.
час (t+1) : новообразованная группа равна (n+1-m) - где m=кол. исчезнувших групп при переходе от t-1 к t. Также существует группа n-1 (бывшая n).
Таким образом, если m=1, то образованные группы упорядоченны и останутся таковыми и на "следующем круге", востав из пепла в том же порядке.
на отрезках m=0 шаг становиться +2,+2,+2 вместо +1, но уже на следующем круге они начинают "сходиться" к +1, +1, +2 и. т.д.
для m>=3 следующий оборот превращается в m=2.
Тут должно быть, что то эллегантное, доказывающие, что n(n+1)/2 - оно само построится, но уже поздно и у меня нет места на полях.

[sedoi-wolk.livejournal.com]

а можно спросить, если всего овец у фермера 2 и они являются 2 группами овец - разве это не та же самая усточивая система, описанная в задаче?

То есть и 2 и 4 и 5 являются решениями задачи,е сли они изначально были разбиты в группы овец по одной штуке:) Если выполнять условия задачи- система стабильна.

[lithovore.livejournal.com]

Пусть овец n(n+1)/2.
Пронумеруем каким-то образом все группы и пронумеруем овец в каждой группе. Будем считать, что из каждой группы уходит овца с номером 1, и номера оставшихся овец уменьшаются на 1; в новой группе овцы получают номера, равные номерам групп, из которых они пришли; новая группа получает номер 1, а номера остальных групп увеличиваются на 1; если при этом какая-то группа исчезнет, но останутся группы с бОльшими номерами, уменьшим их номера так, чтобы нумерация групп снова стала сплошной. В дальнейшем будем количество групп обозначать k, а количество овец в i-ой группе -- a_i.
Рассмотрим величину А = сумма по всем овцам (номер овцы в ее группе + номер ее группы).
Утв. 1: А не увеличивается. Док-во: слагаемые, соответствующие овцам, переходящим в новую группу, не изменяются при переходе, а соответствующие другим овцам -- не увеличиваются (номер овцы в группе уменьшается на 1, номер группы увеличивается на 1, после чего может уменьшиться).
Утв. 2: Если имеется "инверсия" (т.е., группы с номерами i и i+1, такие что a_i

[Error: Irreparable invalid markup ('<a_{i+1}),>') in entry. Owner must fix manually. Raw contents below.]

Пусть овец n(n+1)/2.
Пронумеруем каким-то образом все группы и пронумеруем овец в каждой группе. Будем считать, что из каждой группы уходит овца с номером 1, и номера оставшихся овец уменьшаются на 1; в новой группе овцы получают номера, равные номерам групп, из которых они пришли; новая группа получает номер 1, а номера остальных групп увеличиваются на 1; если при этом какая-то группа исчезнет, но останутся группы с бОльшими номерами, уменьшим их номера так, чтобы нумерация групп снова стала сплошной. В дальнейшем будем количество групп обозначать k, а количество овец в i-ой группе -- a_i.
Рассмотрим величину А = сумма по всем овцам (номер овцы в ее группе + номер ее группы).
Утв. 1: А не увеличивается. Док-во: слагаемые, соответствующие овцам, переходящим в новую группу, не изменяются при переходе, а соответствующие другим овцам -- не увеличиваются (номер овцы в группе уменьшается на 1, номер группы увеличивается на 1, после чего может уменьшиться).
Утв. 2: Если имеется "инверсия" (т.е., группы с номерами i и i+1, такие что a_i<a_{i+1}), то рано или поздно А уменьшится. Док-во: когда меньшая группа исчезнет, бОльшая еще будет существовать, и ее номер уменьшится, что приведет к уменьшению А.
Утв. 3: Если ситуация не статична (т.е., не имеем k=n, a_i=n+1-i), то рано или поздно возникнет инверсия. Док-во: рассмотрим 3 случая:
1) Инверсия уже есть -- доказывать нечего.
2) Группы строго упорядочены по уменьшению (т.е., a_1>a_2>...>a_k). Тогда либо ситуация статична, либо k<n, a_1>n. Тогда следующим ходом имеем a_1<n (старое k), a_2>=n (старое a_1-1) -- инверсия.
3) Ни то, ни другое, т.е., a_1>=a_2>=...>=a_k, и при этом найдется такое i, что a_i=a_{i+1}. Тогда через a_i-1 переходов две или более последних групп будут размера 1; еще через два перехода будет a_1<a_2.

[avva.livejournal.com]

Тогда через a_i-1 переходов две или более последних групп будут размера 1; еще через два перехода будет a_1

[Error: Irreparable invalid markup ('<a_2.</i>') in entry. Owner must fix manually. Raw contents below.]

<i>Тогда через a_i-1 переходов две или более последних групп будут размера 1; еще через два перехода будет a_1<a_2.</i>

Если только две последних группы будут размера 1, то через два перехода будет а_1=а_2.

[lom.livejournal.com]

Kstati... ya snachala reshil zadachu pro svetofory tem zhe sposobom, chto i Vy - nalozheniem dvuh grafov, i tozhe potratil na eto neskol'ko chasov.

A vchera mne prishlo v golovu, chto zadacha imeet gorazdo bolee izyatznoe reshenie - metodom indukcii.

Ono nastol'ko prostoe, chto dazhe ne hochetsya raspisyvat'. Vpolne ochevidno, chto budet, esli k grafu, rabotayutzemu po indukcionnomu predpolozheniya dobavit' etze odnu vershinu proizvol'nym obrazom...
Odna zabavnaya detal' - na pervyj vzglyad, dlya bazy indukcii nado nayti oba varianta povedeniya grafa, no na samom dele - net. Nas vpolne ustraivaet graf sostoyatziy iz 1 tochki dlya bazy. On ne menyaetsya - znachit udovletvoryaet usloviyu. To, chto indukciya ne dokazhet sutzestvovaniya dvuh konechnyj variantov - ne nashe delo. Esli nas prosili dokazat', chto "2x2=4 ILI sutzestvuyut ved'my" - ne nasha problema. "ILI" vse spasaet.
Hotya, konechno zhe, nichego ne stoit pokazat', chto oba varianta deystvitel'no vstrechayutsya, esli rassmotret' v baze bolee odnogo varianta.

[buddha239.livejournal.com]

Помню, в 5ом классе у меня были проблемы с этой задачей, но в следующем за ним 7ом меня уже вроде обучили.:)

[avva.livejournal.com]

ну-ну :)

[(Anonymous)]

решение давайте!

travis free downloads

[(Anonymous)]

trig-red atseehuo [url=http://mequrukaxu.co.cc/rise-of-nations-1.04-patch-download-506.html]rise of nations 1.04 patch download[/url] setterum kniel krowelas [url=http://afibixazuri.co.cc/galvanize-chemical-brothers-download-143.html]galvanize chemical brothers download[/url] lairatin
lednahfr [url=http://enaxybabasokar.co.cc/ddr-download-dance-920.html]ddr download dance[/url] sutxilac senesses aremsais "alreuad [url=http://ebawavabezov.co.cc/pokemon-emulater-download-749.html]pokemon emulater download[/url] voeder lancaien kootakse