СПбГУ 2021, 9 класс, задача 5
( баллов) Дана клетчатая доска . Петя и Вася играют в следующую игру. Они по очереди ставят фишки в свободные клетки доски. Выигрывает тот игрок, после хода которого в каждом квадрате будет стоять фишка. Начинает Петя. Кто из игроков может обеспечить себе победу вне зависимости от действий соперника?
Ответ: Вася.
Решение. Вася должен ходить так, чтобы Петя не смог выиграть следующим ходом. Покажем, что он всегда сможет этого добиться. Если на доске есть пара непересекающихся пустых квадратов , Петя должен поставить фишку так, чтобы они остались и после его хода. Если такой ход невозможен, то на доске свободно всего два непересекающихся пустых квадрата , а остальные клетки заняты фишками. Следовательно, на доску поставлено фишек. Их четное число и, значит, сейчас ход Пети. Если же любые два пустых квадрата пересекаются, то найдется клетка, общая для всех квадратов. Тогда Вася поставит фишку в эту клетку и выиграет.