Всесиб 2024, отборочный этап, 10 класс, задача 4
( баллов) Круг разделён на секторов, в каждом из которых записано или . За один ход можно выбрать любой сектор , в котором записан , изменить цифру в нём на и одновременно изменить символы и в двух секторах, соседних с , на их дополнения и соответственно. Процесс повторяется в некотором порядке до тех пор, пока хотя бы в одном секторе круга записан . В первоначальной конфигурации записан в одном секторе и — во всех остальных. Может ли этот процесс завершиться для а) ? б) ?
Ответ
Ответ. а) Да. б) Нет.
Решение. а) Занумеруем секторы числами по часовой стрелке так, чтобы стоял в первом из них. Проделаем операции последовательно с секторами номер , после чего останется только одна в секторе и — во всех остальных. Разобьём все секторы с нулями на троек соседних, и проделаем операций с секторами номер , центральными в этих тройках. После этого во всех секторах круга будут записаны единицы.
б) Занумеруем секторы числами по часовой стрелке так, чтобы стоял в первом из них. Обозначим за сумму всех чисел, записанных в секторах, номера которых делятся на , а за и — суммы всех чисел, записанных в секторах, номера которых дают при делении на остатки и соответственно. При проведении одного хода чётность каждой из этих сумм меняется, следовательно, чётность каждой из разностей , и остаётся неизменной. Однако в начале эти разности равны , и , среди них две нечётных и одна чётная, а после остановки процесса все они должны стать равными , то есть чётными — противоречие.