Олимпиадная задача Гуровица: перемещения шариков по коробочкам, 9-11 класс
Задача
По кругу расставлено несколько коробочек. В каждой из них может лежать один или несколько шариков (или она может быть пустой). За один ход разрешается взять все шарики из любой коробочки и разложить их, двигаясь по часовой стрелке, начиная со следующей коробочки, кладя в каждую коробочку по одному шарику.
а) Докажите, что если на каждом следующем ходе шарики берут из той коробочки, в которую попал последний шарик на предыдущем ходе, то в какой-то момент повторится начальное размещение шариков.
б) Докажите, что за несколько ходов из любого начального размещения шариков по коробочкам можно получить любое другое.
Решение
а) Текущее состояние описанной в задаче системы определяется количеством шариков в каждой коробочке и указанием коробочки, с которой нужно начинать раскладывать шарики в следующий раз. Поэтому возможных состояний системы конечное число. Из каждого состояния можно, раскладывая шарики, перейти в другое состояние системы, которое определено однозначно. Наоборот, зная состояние системы в настоящий момент, можно однозначно определить состояние системы перед последним раскладыванием шариков. Действительно, последнее раскладывание должно было закончиться на выделенной коробочке; поэтому, чтобы восстановить предыдущее состояние, нужно взять один шарик из выделенной коробочки и далее, идя против часовой стрелки, брать по шарику из каждой коробочки, пока это возможно. Когда же мы встретим пустую коробочку, мы положим в неё все собранные шарики и объявим её отмеченной. Если обозначить состояния системы точками, а возможность перехода из одного состояния в другое – стрелкой, соединяющей соответствующие точки (то есть построить граф состояний системы), то из каждой точки будет выходить ровно одна стрелка и в каждую точку будет входить ровно одна стрелка. Начнём двигаться по стрелкам, начиная с заданного состояния A1. Получаем последовательность состояний A2, A3, ... Поскольку число состояний конечно, в некоторый момент в последовательности {Ai} возникнет повторение. Пусть, например, Ak = An, где k < n. Поскольку в точку Ak входит ровно одна стрелка, из равенства Ak = An следует Ak–1 = An–1, ..., A1 = Ak–n+1. Тем самым, через n – k ходов мы вернулись в состояние A1. б) В отличие от задачи а) теперь состояние системы определяется лишь тем, как разложены шарики по коробочкам.
Заметим, что если ход ведет из состояния A в состояние B, то, согласно а), мы можем (за несколько ходов) вернуться из B в A. Если мы можем попасть из состояния A в состояние C за несколько ходов, то мы можем вернуться из C в A, "откатывая" ходы по одному. Теперь понятно, что если мы научимся попадать из любого состояния в некоторое фиксированное состояние М, то сможем "путешествовать" между любыми состояниями, "проезжая" через М.
Обозначим через М состояние, когда все шарики собраны в фиксированной коробочке m. Будем при каждой операции брать шарики из ближайшей (против часовой стрелки) к m непустой коробочки. Тогда либо число шариков в m увеличится, либо ближайшая к m непустая коробочка станет еще ближе. Рано или поздно все шарики соберутся в m.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь