Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

задачка (решение)

Решение задачи про овец. Кажется, в комментариях там правильного решения второго вопроса все же нет. Это доказательство я придумал сам; возможно, есть какое-то короче/интереснее, не знаю.

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

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

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

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-группу.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 13 comments