|
|
 |
Условие
Дан бесконечный запас белых, синих и красных кубиков. По кругу расставляют любые $N$ из них. Робот, став в любое место круга, идёт по часовой стрелке и, пока не останется один кубик, постоянно повторяет такую операцию: уничтожает два ближайших кубика перед собой и ставит позади себя новый кубик того же цвета, если уничтоженные одинаковы, и третьего цвета, если уничтоженные двух разных цветов. Назовём расстановку кубиков хорошей, если цвет оставшегося в конце кубика не зависит от места, с которого стартовал робот. Назовём $N$ удачным, если при любом выборе $N$ кубиков все их расстановки хорошие. Найдите все удачные $N$.
Решение 1
Присвоим цветам остатки 0, 1, 2 от деления на 3 произвольным образом. Все операции с ними также будем производить по модулю 3. Тогда операция, производимая роботом, такова: если уничтожаются кубики цветов $a$ и $b$, то появляется кубик цвета $- a - b$.
Если $N = 2^k$, то после каждого прохода полного круга количество кубиков уменьшается вдвое, а их сумма меняет знак. Значит, в конце получится кубик цвета $(-1)^k(a_1 + ... + a_N)$, вне зависимости от места старта. Итак, степени двойки удачны.
Если $N = 2^k + d$, где 1 ≤ $d$ ≤ $2^k - 1$, то рассмотрим расстановку из одного красного кубика и $N - 1$ белого. Если робот стартует перед красным кубиком, то после $d$ ходов останутся один синий кубик и $2^k$ – 1 белых. Если робот стартует непосредственно после красного кубика, то через $d$ ходов останутся один красный кубик и $2^k$ – 1 белых. Вышеприведённые аргументы для степени двойки показывают, что в этих двух ситуациях итоговые цвета будут разными, то есть $N$ неудачно.
Решение 2
Заметим, что если чётное число $N$ удачно, то и $\frac{N}{2}$ тоже. Действительно, если в расстановке $N$ кубиков робот будет начинать только с чётных позиций, то после $\frac{N}{2}$ ходов он будет получать одну и ту же расстановку, в которой он стоит на всевозможных позициях. Поскольку каждая расстановка $\frac{N}{2}$ кубиков может быть получена таким образом, получаем требуемое.
Рассмотрим две расстановки, отличающиеся ровно в одном месте. Запустим в них по роботу параллельно; тогда получающиеся расстановки всегда будут отличаться ровно в одном месте. В частности, итоговые цвета будут различны.
Отсюда уже следует, что все нечётные $N = 2k$ + 1 > 1 (а значит, по замечанию, и все $N$, кроме степеней двойки) неудачны. Действительно, начнём с расстановки с одним красным и 2$k$ белыми кубиками. Если робот стоял перед красным кубиком, через $k$ + 1 ход останутся один красный и $k - 1$ белый кубик, робот стоит после красного. Если же робот стартует непосредственно после красного, через $k$ + 1 ход останутся один синий и $k - 1$ белых кубиков, робот стоит непосредственно после синего. Как показано выше, итоговые цвета в этих двух ситуациях будут разными.
Покажем теперь, что, если $N$ – степень двойки, то итоговый цвет не зависит от места старта. Для этого сделаем ещё одно наблюдение по поводу замены цвета. Если цвет одного кубика в расстановке сменить на следующий в циклическом порядке Б $\to$ К $\to$ С $\to$ Б, то после одного использования цвет сдвинется в противоположную сторону. Значит, если $N = 2^k$, любая такая замена исходного кубика приведёт к сдвигу цвета итогового кубика в одну и ту же сторону. Осталось заметить, что две расстановки, отличающиеся поворотом, получаются из расстановки всех белых кубиков за одинаковое количество замен "вперёд по циклу".
Ответ
Степени двойки.
