ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66999
Темы:    [ Теория алгоритмов (прочее) ]
[ Арифметика остатков (прочее) ]
Сложность: 4
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

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


Ответ

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

Источники и прецеденты использования

олимпиада
Название Турнир городов
номер/год
Номер 41
Год 2019/20
тур
Вариант устный тур
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .