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