?

Log in

No account? Create an account
Ни о какой безапелляционности в моих высказываниях не может быть и речи! [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка [авг. 13, 2008|06:39 pm]
Anatoly Vorobey
Во-первых, решение задачи про светофоры, если оно кому-то интересно, есть в журнале flaass'а: вот тут (если оно непонятно из записи - загляните в комментарии, я там немного разжевал).

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

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

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

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

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

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

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

Comments:
Страница 1 из 2
<<[1] [2] >>
[User Picture]From: gaiwan
2008-08-13 03:57 pm
Или чего-то не хватило в условии (мне не хватило :)), или есть всего три овцы.
(Ответить) (Thread)
[User Picture]From: avva
2008-08-13 04:08 pm
Не уверен, что именно вы не поняли :)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: bamsic
2008-08-13 03:58 pm
На первый взгляд все просто, группы должны быть такими:
1, 2, 3, 4,.. n
тогда если от всех групп отнять по одно, то получим новую группу размерностью n, при этом их общее кол-во не изменится.
(Ответить) (Thread)
[User Picture]From: dimrub
2008-08-13 04:01 pm
По поводу №1 - я так понимаю, оно должно быть вида n*(n+1)/2
(Ответить) (Thread)
[User Picture]From: bamsic
2008-08-13 04:03 pm
Так и есть сумма арифметической прогрессии.

Вот только как доказать, что стабилизация возможна?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: vitus_wagner
2008-08-13 04:03 pm
Число овец должно быть треугольным.
(Ответить) (Thread)
[User Picture]From: avva
2008-08-13 04:08 pm
А доказать? :)
(Ответить) (Parent) (Thread)
From: nighttime_notes
2008-08-13 04:04 pm

вроде бы так

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

что касается стабилизации - кажется верным, что произойдет
(Ответить) (Thread)
[User Picture]From: avva
2008-08-13 04:14 pm

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

С первый вопросом все верно, да.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: torquelimach
2008-08-13 04:17 pm
1) N = k(k+1)/2 для натурального k, соответствующего числу групп. Доказательство: поскольку число групп не меняется, в одной (и только одной) группе была одна овца. Поэтому (если k>1) в одной (и только одной) группе было две овцы. Далее аналогично.
(Ответить) (Thread)
[User Picture]From: avva
2008-08-13 04:19 pm
ага.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2008-08-13 04:37 pm
две группы по две овцы. отход одной овцы эквивалентен отходу другой (если не вдаваться в психологию овец и не допрашивать, кто был инициатором отхода). овцы свингуют типа
(Ответить) (Thread)
From: lenik_terenin
2008-08-13 04:44 pm
Со стабильным количеством овец вроде уже решили. Со стабилизацией всё тоже достаточно просто, сортируем их по размеру и смотрим -- если количество групп овец больше стабильного, то обязательно найдутся две (или более) групп с одинаковым количеством овец, которые обязательно одновременно исчезнут на каком-то шаге. Соответственно, если количество групп овец меньше стабильного, то значит какая-то группа из N овец отсутствует, и через N шагов у нас не будет группы из 1ой овцы, и на этом шаге количество групп увеличится.
(Ответить) (Thread)
[User Picture]From: avva
2008-08-13 04:59 pm
Кол-во групп может и возрастать, и уменьшаться со временем - возрастать, если нет групп из одной овцы (и расти долго, если нет групп с небольшим кол-вом овец); уменьшаться, если есть группы с одинаковым кол-вом овец. Ваше объяснение никак не опровергает того, что эти два явления могут происходить одновременно (и воссоздавать друг друга: как группы с размером, равным уже существующей группе, так и "дырки" могут образовываться заново).
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: dr_basf
2008-08-13 05:00 pm
первый вопрос - по формуле арифм прогрессии считается, а вот второй вопрос что-то не осилил
(Ответить) (Thread)
[User Picture]From: syarzhuk
2008-08-13 05:34 pm
Три овцы:
шаг 0 - 1 группа в 3 овцы
шаг 1 - 2 группы - 2 и 1 овца
шаг 2 - 2 группы - 1 и 2 овцы
подходит? или я чего-то недопонял в условии?
(Ответить) (Thread)
[User Picture]From: avva
2008-08-13 05:37 pm
ну это один пример стабилизации, да.
(Ответить) (Parent) (Thread)
[User Picture]From: programmilla
2008-08-13 06:22 pm
А почему именно три?
Почему понятия овцы, каждая группа и т.д. не понять - как "ненулевое множество", тогда одной овцы хватит...
Тогда и второй вопрос - тривиален :)
(Ответить) (Thread)
[User Picture]From: phoonzang
2008-08-13 06:24 pm
Похожая задача: за столом сидят семь гномов, у каждого пивная кружка с некоторым (неотрицательным) кол-вом пива в ней. Каждый из гномов по очереди распределяет все пиво из своей кружки поровну между остальными шестью гномами, после чего у них в кружках кол-во пива становится равным начальному.

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

(тривиальное решение со всеми пустыми кружками не предлагать)
(Ответить) (Thread)
From: 184467440737095
2008-08-13 08:44 pm
эксперимент показывает, что процесс устаканивается к треугольной конфигурации независимо от начальных условий за не более чем n*(n-1) итераций, при (n+1)*n/2 овцах.

что, впрочем, почти не приближает к доказательству этого факта.
(Ответить) (Thread)
[User Picture]From: lenik_r
2008-08-13 08:49 pm
задача также известна как "задача о стаканах"

http://www.sch57.msk.ru/~masha_semenova/MATH/drobi/glass.htm
(Ответить) (Thread)
From: ext_105441
2008-08-15 06:52 am
ты знал! :)
(Ответить) (Parent) (Thread)
From: ex_rofer
2008-08-13 09:10 pm

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

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

(Ответить) (Thread)
[User Picture]From: avva
2008-08-13 10:42 pm

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

:-)
(Ответить) (Parent) (Thread)
Страница 1 из 2
<<[1] [2] >>