Разделы 
Дополнительно
Задача по математике - 3358
2019-06-02 
По кругу расставлено несколько коробочек. В каждой из них может лежать один или несколько шариков (или она может быть пустой). За один ход разрешается взять все шарики из любой коробочки и разложить их, двигаясь по часовой стрелке, начиная со следующей коробочки, кладя в каждую коробочку по одному шарику.
а) Докажите, что если на каждом следующем ходе шарики берут из той коробочки, в которую попал последний шарик на предыдущем ходе, то в какой-то момент повторится начальное размещение шариков.
б) Докажите, что за несколько ходов из любого начального размещения шариков по коробочкам можно получить любое другое.
Комментарий. В пункте «б» можно брать камни из любой коробочки, не только той, в которую попал последний шарик на предыдущем ходе.
Решение:
а) Текущее состояние описанной в задаче системы определяется количеством шариков в каждой коробочке и указанием коробочки, с которой нужно начинать раскладывать шарики в следующий раз. Поэтому возможных состояний системы конечное число. Из каждого состояния можно, раскладывая шарики, перейти в другое состояние системы, которое определено однозначно. Наоборот, зная состояние системы в настоящий момент, можно однозначно определить состояние системы перед последним раскладыванием шариков. Действительно, последнее раскладывание должно было закончиться на выделенной коробочке; поэтому, чтобы восстановить предыдущее состояние, нужно взять один шарик из выделенной коробочки и далее, идя против часовой стрелки, брать по шарику из каждой коробочки, пока это возможно. Когда же мы встретим пустую коробочку, мы положим в нее все собранные шарики и объявим ее отмеченной. (Фактически мы дали описание операции, обратной к ходу, описанному в условии задачи.) Если обозначить состояния системы точками, а возможность перехода из одного состояния в другое - стрелкой, соединяющей соответствующие точки (т. е. построить ориентированный граф состояний системы, см. факт 3), то из каждой точки будет выходить ровно одна стрелка и в каждую точку будет входить ровно одна стрелка. Начнем двигаться по стрелкам, начиная с заданного состояния $A_1$. Получаем последовательность состояний $A_2, A_3, \cdots$. Поскольку число состояний конечно, в некоторый момент в последовательности $\{ A_i \}$ возникнет повторение. Пусть, например, $A_k = A_n$, где $k < n$. Поскольку в точку $A_k$ входит ровно одна стрелка, из равенства $A_k = A_n$ следуют равенства $A_{k-1} = A_{n-1}, \cdots, A_1 = A_{n-k+1}$. Тем самым, через $n - k$ ходов мы вернулись в состояние $A_1$.
б) В отличие от задачи «а» теперь состояние системы определяется лишь тем, как разложены шарики по коробочкам. В каждый момент возможно несколько ходов, а именно столько, сколько в данный момент имеется непустых коробочек. Нетрудно видеть, что имеется столько же возможностей выполнить обратную операцию, описанную в решении пункта «а». В терминах графа состояний системы это означает, что из каждой точки выходит столько же стрелок, сколько в нее входит.
Докажем два вспомогательных утверждения.
Лемма 1. При любом начальном состоянии можно добиться того, чтобы все шарики оказались в одной наперед заданной коробочке $X$.
Доказательство. Если при каждой операции брать шарики из непустой коробочки, ближайшей к $X$ при движении против часовой стрелки, то либо число шариков в $X$ увеличится, либо количество шариков в $X$ не изменится, а ближайшая к $X$ непустая коробочка станет еще ближе, что не может продолжаться бесконечно. Лемма доказана.
Лемма 2. Если из состояния $A$ можно попасть в состояние $В$, то из состояния В можно попасть в состояние $A$.
Доказательство. Заметим, что если из $A$ в $C$ ведет стрелка, то из $C$ в $A$ тоже можно попасть, двигаясь по стрелкам. Действительно, пройдем по стрелке из $A$ в $C$, а далее будем действовать как в пункте «а», т. е. на каждом следующем ходе будем брать шарики из той коробочки, в которую попал последний шарик на предыдущем ходе. Тогда, согласно утверждению пункта «а», повторится на¬чальная ситуация - мы попадем в состояние $A$. Поэтому если можно попасть из $A$ в $В$ (за несколько ходов), то можно попасть из $В$ в $A$. Лемма доказана.
Пусть $A$ и $В$ - произвольные состояния. Обозначим через $K$ состояние, при котором все шарики собраны в коробочке $X$. Согласно лемме 1, можно попасть из $A$ в $K$. Из лемм 1 и 2 следует, что можно попасть из $K$ в $В$. Значит, можно попасть из $A$ в $В$.
По кругу расставлено несколько коробочек. В каждой из них может лежать один или несколько шариков (или она может быть пустой). За один ход разрешается взять все шарики из любой коробочки и разложить их, двигаясь по часовой стрелке, начиная со следующей коробочки, кладя в каждую коробочку по одному шарику.
а) Докажите, что если на каждом следующем ходе шарики берут из той коробочки, в которую попал последний шарик на предыдущем ходе, то в какой-то момент повторится начальное размещение шариков.
б) Докажите, что за несколько ходов из любого начального размещения шариков по коробочкам можно получить любое другое.
Комментарий. В пункте «б» можно брать камни из любой коробочки, не только той, в которую попал последний шарик на предыдущем ходе.
Решение:
а) Текущее состояние описанной в задаче системы определяется количеством шариков в каждой коробочке и указанием коробочки, с которой нужно начинать раскладывать шарики в следующий раз. Поэтому возможных состояний системы конечное число. Из каждого состояния можно, раскладывая шарики, перейти в другое состояние системы, которое определено однозначно. Наоборот, зная состояние системы в настоящий момент, можно однозначно определить состояние системы перед последним раскладыванием шариков. Действительно, последнее раскладывание должно было закончиться на выделенной коробочке; поэтому, чтобы восстановить предыдущее состояние, нужно взять один шарик из выделенной коробочки и далее, идя против часовой стрелки, брать по шарику из каждой коробочки, пока это возможно. Когда же мы встретим пустую коробочку, мы положим в нее все собранные шарики и объявим ее отмеченной. (Фактически мы дали описание операции, обратной к ходу, описанному в условии задачи.) Если обозначить состояния системы точками, а возможность перехода из одного состояния в другое - стрелкой, соединяющей соответствующие точки (т. е. построить ориентированный граф состояний системы, см. факт 3), то из каждой точки будет выходить ровно одна стрелка и в каждую точку будет входить ровно одна стрелка. Начнем двигаться по стрелкам, начиная с заданного состояния $A_1$. Получаем последовательность состояний $A_2, A_3, \cdots$. Поскольку число состояний конечно, в некоторый момент в последовательности $\{ A_i \}$ возникнет повторение. Пусть, например, $A_k = A_n$, где $k < n$. Поскольку в точку $A_k$ входит ровно одна стрелка, из равенства $A_k = A_n$ следуют равенства $A_{k-1} = A_{n-1}, \cdots, A_1 = A_{n-k+1}$. Тем самым, через $n - k$ ходов мы вернулись в состояние $A_1$.
б) В отличие от задачи «а» теперь состояние системы определяется лишь тем, как разложены шарики по коробочкам. В каждый момент возможно несколько ходов, а именно столько, сколько в данный момент имеется непустых коробочек. Нетрудно видеть, что имеется столько же возможностей выполнить обратную операцию, описанную в решении пункта «а». В терминах графа состояний системы это означает, что из каждой точки выходит столько же стрелок, сколько в нее входит.
Докажем два вспомогательных утверждения.
Лемма 1. При любом начальном состоянии можно добиться того, чтобы все шарики оказались в одной наперед заданной коробочке $X$.
Доказательство. Если при каждой операции брать шарики из непустой коробочки, ближайшей к $X$ при движении против часовой стрелки, то либо число шариков в $X$ увеличится, либо количество шариков в $X$ не изменится, а ближайшая к $X$ непустая коробочка станет еще ближе, что не может продолжаться бесконечно. Лемма доказана.
Лемма 2. Если из состояния $A$ можно попасть в состояние $В$, то из состояния В можно попасть в состояние $A$.
Доказательство. Заметим, что если из $A$ в $C$ ведет стрелка, то из $C$ в $A$ тоже можно попасть, двигаясь по стрелкам. Действительно, пройдем по стрелке из $A$ в $C$, а далее будем действовать как в пункте «а», т. е. на каждом следующем ходе будем брать шарики из той коробочки, в которую попал последний шарик на предыдущем ходе. Тогда, согласно утверждению пункта «а», повторится на¬чальная ситуация - мы попадем в состояние $A$. Поэтому если можно попасть из $A$ в $В$ (за несколько ходов), то можно попасть из $В$ в $A$. Лемма доказана.
Пусть $A$ и $В$ - произвольные состояния. Обозначим через $K$ состояние, при котором все шарики собраны в коробочке $X$. Согласно лемме 1, можно попасть из $A$ в $K$. Из лемм 1 и 2 следует, что можно попасть из $K$ в $В$. Значит, можно попасть из $A$ в $В$.
