Комбинаторика на устном туре Турнира Городов

(a) Текущее состояние описанной в задаче системы определяется количеством шариков в каждой коробочке и указанием коробочки, с которой нужно начинать раскладывать шарики в следующий раз. Поэтому возможных состояний системы конечное число. Из каждого состояния можно, раскладывая шарики, перейти в другое состояние системы, которое определено однозначно. Наоборот, зная состояние системы в настоящий момент, можно однозначно определить состояние системы перед последним раскладыванием шариков. Действительно, последнее раскладывание должно было закончиться на выделенной коробочке; поэтому, чтобы восстановить предыдущее состояние, нужно взять один шарик из выделенной коробочки и далее, идя против часовой стрелки, брать по шарику из каждой коробочки, пока это возможно. Когда же мы встретим пустую коробочку, мы положим в неё все собранные шарики и объявим её отмеченной. Если обозначить состояния системы точками, а возможность перехода из одного состояния в другое — стрелкой, соединяющей соответствующие точки (то есть построить граф состояний системы), то из каждой точки будет выходить ровно одна стрелка и в каждую точку будет входить ровно одна стрелка. Начнём двигаться по стрелкам, начиная с заданного состояния Получаем последовательность состояний Поскольку число состояний конечно, в некоторый момент в последовательности возникнет повторение. Пусть, например, где Поскольку в точку входит ровно одна стрелка, из равенства следует Тем самым, через ходов мы вернулись в состояние

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

Заметим, что если ход ведет из состояния в состояние то, согласно первому пункту, мы можем (за несколько ходов) вернуться из в Если мы можем попасть из состояния в состояние за несколько ходов, то мы можем вернуться из в “откатывая” ходы по одному. Теперь понятно, что если мы научимся попадать из любого состояния в некоторое фиксированное состояние то сможем “путешествовать” между любыми состояниями, “проезжая” через

Обозначим через состояние, когда все шарики собраны в фиксированной коробочке Будем при каждой операции брать шарики из ближайшей (против часовой стрелки) к непустой коробочки. Тогда либо число шариков в увеличится, либо ближайшая к непустая коробочка станет еще ближе. Рано или поздно все шарики соберутся в