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