ВсОШ 2021, 10 класс, задача 5
Дана бесконечная клетчатая плоскость. Учительница и класс из 30 учеников играют в игру, делая ходы по очереди - сначала учительница, затем по очереди все ученики, затем снова учительница, и т. д. За один ход можно покрасить единичный отрезок, являющийся границей между двумя соседними клетками. Дважды красить отрезки нельзя. Учительница побеждает, если после хода одного из 31 игроков найдется клетчатый прямоугольник или такой, что у него вся граница покрашена, а единичный отрезок внутри него не покрашен. Докажите, что учительница сможет победить.
(М. Дидин, А. Кузнецов)
Ответ
Решение.
Учительница выберет квадрат размера и будет закрашивать отрезки его границы, если это возможно. Пусть перед -м ее ходом все эти отрезки закрашены. Тогда , поскольку всего на границе отрезков. К этому моменту всего закрашено не более чем отрезков, поэтому хотя бы один отрезок внутри квадрата не закрашен. Каждым следующим ходом учительница будет закрашивать один из отрезков внутри . Спустя несколько ходов все отрезки внутри будут закрашены. Тогда перед ходом игрока, который закрасит последний из таких отрезков, найдется искомый прямоугольник , и учительница победит.