Высшая проба 2026, 10 класс, задача 6
(22 балла) На плоскости ввели прямоугольную систему координат и отметили все точек, у которых обе координаты являются натуральными числами, причём абсцисса не превышает , а ордината не превышает . Затем все отрезки между двумя отмеченными точками, координаты которых отличаются ровно на ровно в одной из координат, покрасили в белый или чёрный цвет. За один шаг разрешается выбрать точку и перекрасить все выходящие из неё отрезки в противоположный цвет. Всегда ли можно за несколько шагов добиться того, чтобы все отрезки стали одного цвета?
Ответ
Ответ. Не всегда.
Решение. Переформулируем задачу в терминах раскраски клеток квадрата . Каждому отрезку сопоставим клетку: горизонтальным и вертикальным отрезкам соответствуют клетки, а шаг с выбранной точкой меняет цвета всех клеток, стоящих в одной строке или одном столбце с этой точкой в нужной интерпретации. Достаточно предъявить раскраску, которую нельзя привести к одноцветной.
Рассмотрим следующую последовательность перекрашиваний отрезков:
Она переводит раскраску всех отрезков одного цвета в некоторую раскраску.
Покажем, что полученную раскраску нельзя сделать одноцветной. Предположим, что можно. Тогда если сначала выполнить указанную выше последовательность, а затем выполнить шаги, приводящие раскраску к одноцветной, мы получим последовательность шагов, которая переводит одноцветную раскраску в одноцветную.
Всего есть возможных шагов, и каждый шаг достаточно выполнять не более одного раза, потому что два одинаковых шага взаимно уничтожаются. Поэтому любая такая последовательность задаётся подмножеством этих шагов. Если последовательность переводит одноцветную раскраску в одноцветную, то для любых двух соседних клеток число применённых к ним шагов должно иметь одинаковую чётность. Значит, эта чётность одинакова для всех клеток, и возможны только два случая: не выполнено ни одного шага или выполнены все шагов.
Но первая указанная последовательность содержит шагов. Значит, чтобы получить одноцветную раскраску, оставшаяся последовательность должна отличаться от неё либо ровно этими шагами, либо дополнением из шагов. Непосредственная проверка показывает, что дополнение к первой последовательности не является допустимой последовательностью такого вида: например, последовательность
не меняет раскраску, но не совпадает ни с пустой последовательностью, ни со всеми шагами.
Следовательно, существует исходная раскраска, которую нельзя привести к одноцветной, и ответ на вопрос задачи отрицательный