?

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 ]

задачка (решение) [авг. 18, 2008|11:12 am]
Anatoly Vorobey
Решение задачи про овец. Кажется, в комментариях там правильного решения второго вопроса все же нет. Это доказательство я придумал сам; возможно, есть какое-то короче/интереснее, не знаю.

Повторю условие:

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

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

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

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


Решение:

1) Общее число овец должно быть "треугольным числом", т.е. числом вида 1+2+3+....+N. Тогда овцы могут выстроиться в N групп размером 1,2,3,...N, и ясно, что это стабильная конфигурация. С другой стороны, докажем, что любая стабильная конфигурация выглядит именно так. Пусть в стабильной конфигурации есть k групп, тогда на следующем шагу возникнет одна новая, значит ровно одна должна исчезнуть, поэтому есть ровно одна группа из одной овцы. Т.к. на следующем шагу опять должна быть ровно одна из одной, сейчас есть ровно одна из двух. Продолжая так дальше, мы видим, что есть ровно одна группа размером 1,2,3... и так до наибольшей по размеру группы. Ясно, что наибольшей по размеру группой должна быть как раз k, потому что она возникнет на следующем шагу. Итак, группы обязаны быть 1,2,3....k.

2) Мы хотим доказать следующее: если число овец равно 1+2+3...+N+(N+1), то с чего бы мы ни начали, закончим конфигурацией 1,2,3....N+1. Я сформулировал это сразу для N+1, чтобы легче было использовать индукцию. Итак, пусть у нас есть 1+2+...+(N+1) овец, возьмем любые N+1 из них и покрасим в черный цвет (все остальные овцы белые). Теперь будем все делать как раньше, только всякий раз, когда овцы отделяются от каждой группы, чтобы сформировать новую, будем всегда отделять белую овцу, если это возможно. Теперь можно легко убедиться, что в таком случае белые овцы ведут себя в точности по правилам в применении только к белым овцам, как будто черных вовсе нет. Поэтому к ним (а их 1+2+....+N) можно применить допущение индукции, т.е. мы знаем, что белые овцы рано или поздно стабилизируются в группы 1,2,3...N (отныне мы будем считать, что это уже случилось). В каждой из таких групп, кроме того, может быть какое-то количество черных овец, а кроме того, могут быть отдельные черные группы. Мы хотим доказать, что рано или поздно после этого черные овцы расположатся так, что в каждой белой группе будет одна черная овца, плюс еще будет одна отдельная черная овца. Это и будет стабильной конфигурацией 1,2,3...N+1.

Пронумеруем группы по числу белых овец в них: например, 3-группа это та, в которой 3 белых овцы (плюс возможно еще есть черные). У нас есть белые группы: по одной 1-группе, 2-группе итд. до N-группы, плюс какое-то количество черных 0-групп. Назовем белую группу политкорректной, если в ней есть хотя бы одна черная овца. Если в группе есть больше одной черной овцы, назовем всех добавочных черных овец (кроме первой) беспризорными овцами. Обратим внимание на то, как черные овцы ведут себя от шага к шагу: они мигрируют из k-группы в k-1-группу, пока не дойдут до 0-группы; кроме того, на каждом шагу формируется новая N-группа, которая захватывает по одной черной овце из всех имеющихся на тот момент 0-групп.

Нам осталось доказать одно за другим несколько простых утверждений, которые приведут нас к искомому:

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

Доказательство: пусть k-группа политкорректна, т.е. в ней X черных овец, где X > 0. Тогда через k шагов она станет 0-группой с X овцами, а это значит, что на k+1 шаге сформируется новая N-группа, которая будет политкорректной, и к N+1 шагу эта N-группа станет k-группой.

б) Если в какой-то белой k-группе (k < N) есть беспризорные овцы, то через N+1 шагов одна из этих овец перейдет к k+1-группе, и либо сделает ее политкорректной (если до того она не была таковой), либо будет в ней беспризорной овцой.

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

в) Если в N-группе есть беспризорные овцы, то через N+1 шагов будет больше одной 0-группы (кроме случая, когда 0-групп не было вообще, но тогда одна появится). Если сейчас есть больше одной 0-группы, то через 2(N+1) будет беспризорная овца в 1-группе (кроме случая, когда 1-группа не была политкорректной, но тогда она ей станет).

Доказательство: просто проследить за эволюцией. Во второй части 2(N+1) появляется потому, что из состояния "больше одной 0-группы" мы сначала за N+1 шагов переходим в состояние "0-группа из более чем одной овцы", а потом еще за N+1 шагов - к тому, что требуется.

г) Овцы стабилизируются.

Доказательство: Посмотрим на картинку в любой момент (после стабилизации белых овец, конечно), и после этого будет смотреть на нее прыжками через N+1 шагов. Согласно а), политкорректные группы всегда такими и останутся. Согласно б), беспризорные овцы будут мигрировать "вверх" от группы к группе, пока не найдут неполиткорректную "дырку" и не заполнят ее. Однако может случиться, что все неполиткорректные группы меньше, чем группы с беспризорные овцами. Но тогда согласно в), беспризорная овца мигрирует сквозь 0-группы к 1-группе и все равно найдет свою неполиткорректную жертву. Поскольку у нас есть N+1 черная овца и N белых групп, пока есть неполиткорректные группы, есть также беспризорные овцы, поэтому рано или поздно все группы станут политкорректными. К этому моменту у нас останется одна дополнительная черная овца, которая уже либо будет стоять на месте в одиночной 0-группе, либо будет беспризорной где-нибудь в белых, и тогда опять согласно в) вскорости мигрирует в 0-группу.
СсылкаОтветить

Comments:
[User Picture]From: buddha239
2008-08-18 09:26 am
Интересное рассуждение - хотя дочитывать лень.:) Стандартное (вроде бы:)) решение другое - надо нумеровать овец в каждой группе и группы в порядке убывания числа овец (на каждом ходу, скажем, от 1) и просуммировать по всем овцам (номер овцы в группе + номер группы). Эта величина невозрастает, и стабилизируется только для стабильной конфигурации (если число овец какое нужно). Тут лучше смотреть на диаграммы Юнга.
(Ответить) (Thread)
[User Picture]From: avva
2008-08-18 11:28 am
В комментах к записи с задачей кто-то предлагал такое решение, но в нем была дырка. Ее наверняка можно исправить, но я не увидел немедленного пути.
(Ответить) (Parent) (Thread)
[User Picture]From: buddha239
2008-08-18 11:42 am
Таки удобнее представлять себе диаграмму Юнга.:)
http://en.wikipedia.org/wiki/Young_tableau
Если проишодит стабилизация - значит, все клетки едут по своим диагоналям. Следовательно, если над не до конца заполненнои диагональю есть клетки, то через какое-то время они окажутся над "дыркой". И все.:)
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-08-18 12:49 pm
Не знаю, по-моему это hand-waving, а не аргумент. Он даже не учитывает точного числа клеток.

Наверное, его можно уточнить, но тогда получится, по-моему, примерно то же, что я и написал (возможно, без использования индукции, которая тут просто сильно проясняет картинку, предоставляя бесплатно базисный фундамент для диаграммы). Диаграммами ясно, что полезно пользоваться для того, чтобы на это смотреть, я так и делал (не помня, что они так называются).
(Ответить) (Parent) (Thread)
[User Picture]From: buddha239
2008-08-18 03:54 pm
Собственно, я и не претендовал на формализованное доказательство.:) Я вообще мало на что претендовал, поскольку вряд ли сам придумал это решение 17 лет назад.:)

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

Кстати, я не стал писать решение подробно, потому что мне всегда было лень так писать, равно как и читать подробные решения других.:) Поэтому я и не прочитал альтернативное до конца решение.:) Однако первая его часть мне понравилась - и мне кажется, что 1. так решать можно 2. это решение непохоже на "классическое" (то, о котором говорю я:)).
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-08-18 04:05 pm
Ага, спасибо :-)
(Ответить) (Parent) (Thread)
[User Picture]From: lelia_br
2008-08-18 12:33 pm
This a classical self-stabilizing algorithm. I even remember solving such a question (but chain of numbers instead of sheeps) during my MSc distributed computing course. My advisor "sobaku s#el" on self-stabilization.
(Ответить) (Thread)
From: (Anonymous)
2008-08-18 03:55 pm
спасибо ;)
(Ответить) (Thread)
(Удалённый комментарий)
[User Picture]From: avva
2008-08-18 05:16 pm
Факт. Я сам об этом забыл (и сейчас заново ее решил), потом мне напомнили.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-08-18 05:16 pm
Там было с картами, 45 карт.
(Ответить) (Parent) (Thread)
From: 9000
2008-08-18 10:17 pm
За слово "политкорректная" особенное спасибо :))
(Ответить) (Thread)
[User Picture]From: rus_arbuz
2008-08-20 08:10 am

Мне кажется должно быть простое решение.

Что-то мне все это напоминает затухающие колебания.
(Ответить) (Thread)