Страница 1 из 2 | << | [1] [2] | >> |
Или чего-то не хватило в условии (мне не хватило :)), или есть всего три овцы.
Не уверен, что именно вы не поняли :)
На первый взгляд все просто, группы должны быть такими: 1, 2, 3, 4,.. n тогда если от всех групп отнять по одно, то получим новую группу размерностью n, при этом их общее кол-во не изменится.
По поводу №1 - я так понимаю, оно должно быть вида n*(n+1)/2
Так и есть сумма арифметической прогрессии.
Вот только как доказать, что стабилизация возможна?
Число овец должно быть треугольным.
1) чтобы число групп не менялось (именно, не росло), по крайней мере одна группа должна состоять из одной овцы 2) групп по одной овце не может быть больше 1 (иначе число групп уменьшится на следующем шаге) 3) поскольку после деления должна остаться группа ровно с одной овцой, то есть группа с двумя овцами. В силу 2), такая группа ровно одна (или ни одной, если существует только одна овца) 4) далее более-менее ясно, что состав групп 1, 2,...,n, где n>=1
что касается стабилизации - кажется верным, что произойдет
![[User Picture]](https://l-userpic.livejournal.com/81048954/111931) | From: avva 2008-08-13 04:14 pm
Re: вроде бы так | (Link)
|
С первый вопросом все верно, да.
1) N = k(k+1)/2 для натурального k, соответствующего числу групп. Доказательство: поскольку число групп не меняется, в одной (и только одной) группе была одна овца. Поэтому (если k>1) в одной (и только одной) группе было две овцы. Далее аналогично.
From: (Anonymous) 2008-08-13 04:37 pm
| (Link)
|
две группы по две овцы. отход одной овцы эквивалентен отходу другой (если не вдаваться в психологию овец и не допрашивать, кто был инициатором отхода). овцы свингуют типа
Со стабильным количеством овец вроде уже решили. Со стабилизацией всё тоже достаточно просто, сортируем их по размеру и смотрим -- если количество групп овец больше стабильного, то обязательно найдутся две (или более) групп с одинаковым количеством овец, которые обязательно одновременно исчезнут на каком-то шаге. Соответственно, если количество групп овец меньше стабильного, то значит какая-то группа из N овец отсутствует, и через N шагов у нас не будет группы из 1ой овцы, и на этом шаге количество групп увеличится.
Кол-во групп может и возрастать, и уменьшаться со временем - возрастать, если нет групп из одной овцы (и расти долго, если нет групп с небольшим кол-вом овец); уменьшаться, если есть группы с одинаковым кол-вом овец. Ваше объяснение никак не опровергает того, что эти два явления могут происходить одновременно (и воссоздавать друг друга: как группы с размером, равным уже существующей группе, так и "дырки" могут образовываться заново).
первый вопрос - по формуле арифм прогрессии считается, а вот второй вопрос что-то не осилил 
Три овцы: шаг 0 - 1 группа в 3 овцы шаг 1 - 2 группы - 2 и 1 овца шаг 2 - 2 группы - 1 и 2 овцы подходит? или я чего-то недопонял в условии?
ну это один пример стабилизации, да.
А почему именно три? Почему понятия овцы, каждая группа и т.д. не понять - как "ненулевое множество", тогда одной овцы хватит... Тогда и второй вопрос - тривиален :)
Похожая задача: за столом сидят семь гномов, у каждого пивная кружка с некоторым (неотрицательным) кол-вом пива в ней. Каждый из гномов по очереди распределяет все пиво из своей кружки поровну между остальными шестью гномами, после чего у них в кружках кол-во пива становится равным начальному.
Вопрос: сколько пива было у гномов в кружках изначально?
(тривиальное решение со всеми пустыми кружками не предлагать)
эксперимент показывает, что процесс устаканивается к треугольной конфигурации независимо от начальных условий за не более чем n*(n-1) итераций, при (n+1)*n/2 овцах.
что, впрочем, почти не приближает к доказательству этого факта.
From: ex_rofer 2008-08-13 09:10 pm
синхронизация овец со светофорами | (Link)
|
украдено у mi3ch'a: 
![[User Picture]](https://l-userpic.livejournal.com/81048954/111931) | From: avva 2008-08-13 10:42 pm
Re: синхронизация овец со светофорами | (Link)
|
:-) Страница 1 из 2 | << | [1] [2] | >> |
|