Комбинаторика на устном туре Турнира Городов

Первое решение.

Присвоим цветам остатки от деления на 3 произвольным образом. Все операции с ними также будем производить по модулю Тогда операция, производимая роботом, такова: если уничтожаются кубики цветов и то появляется кубик цвета

Если то после каждого прохода полного круга количество кубиков уменьшается вдвое, а их сумма меняет знак. Значит, в конце получится кубик цвета вне зависимости от места старта. Мы доказали, что степени двойки удачны.

Если где то рассмотрим расстановку из одного красного кубика и белого. Если робот стартует перед красным кубиком, то после ходов останутся один синий кубик и белых. Если робот стартует непосредственно после красного кубика, то через ходов останутся один красный кубик и белых. Вышеприведённые аргументы для степени двойки показывают, что в этих двух ситуациях итоговые цвета будут разными, то есть неудачно.

Второе решение.

Заметим сразу, что, если чётное число удачно, то и тоже. Действительно, если в расстановке кубиков робот будет начинать только с чётных позиций, то после ходов он будет получать одну и ту же расстановку, в которой он стоит на всевозможных позициях. Поскольку каждая расстановка кубиков может быть получена таким образом, получаем требуемое.

Рассмотрим две расстановки, отличающиеся ровно в одном месте. Запустим в них по роботу параллельно; тогда получающиеся расстановки всегда будут отличаться ровно в одном месте. В частности, итоговые цвета будут различны.

Отсюда уже следует, что все нечётные (а значит, по замечанию, и все кроме степеней двойки) неудачны. Действительно, начнём с расстановки с одним красным и белыми кубиками. Если робот стоял перед красным кубиком, через ход останутся один красный и белый кубик, робот стоит после красного. Если же робот стартует непосредственно после красного, через ход останутся один синий и белых кубиков, робот стоит непосредственно после синего. Как показано выше, итоговые цвета в этих двух ситуациях будут разными.

Покажем теперь, что, если — степень двойки, то итоговый цвет не зависит от места старта. Для этого сделаем ещё одно наблюдение по поводу замены цвета. Если цвет одного кубика в расстановке сменить на следующий в циклическом порядке

то после одного использования цвет сдвинется в противоположную сторону.

Значит, если любая такая замена исходного кубика приведёт к сдвигу цвета итогового кубика в одну и ту же сторону. Осталось заметить, что две расстановки, отличающиеся поворотом, получаются из расстановки всех белых кубиков за одинаковое количество замен "вперёд по циклу".