Назад
Задача

Дан бесконечный запас белых, синих и красных кубиков. По кругу расставляют любые $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$,  любая такая замена исходного кубика приведёт к сдвигу цвета итогового кубика в одну и ту же сторону. Осталось заметить, что две расстановки, отличающиеся поворотом, получаются из расстановки всех белых кубиков за одинаковое количество замен "вперёд по циклу".

Ответ

Степени двойки.

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет