Есть клетчатое поле. Два игрока делают ходы по очереди. Ход состоит в том, что игрок закрашивает несколько клеток, которые вместе образуют один прямоугольник. Перекрашивать клетки нельзя. Проигрывает тот, кто красит последнюю клетку. Кто победит при верной игре, если размеры поля:
а) 1×n клеток;
б) 2×n клеток, n>1;
в) 3×n клеток, n>2.
Задача была предложена на конкурсе по математическим играм Турнира имени Ломоносова в 2008 году.
В пункте а) на поле 1×1 победит второй игрок, иначе же первый, который сразу же закрасит всё поле, кроме одной клетки.
В пункте б) на поле 2×2 победит второй игрок (это легко проверяется), а во всех прочих случаях первый — он своим ходом может оставить второму игроку квадрат со стороной в 2 клетки.
В случае в) победит первый игрок. Опишем выигрышную стратегию для начинающего игру для общего случая m × n клеток, n>m−1. Первый ход начинающего состоит в закрашивании почти всего поля - незакрашенными остаются лишь две полоски размером m×1 по его краям.
Дальнейшая игра будет идти на двух независимых полосках. Начинает второй. Первый придерживается такого правила: на любой ход второго на одной из полосок отвечает таким же (симметричным) ходом на второй. Но: как только при ходе второго игрока его полоска (та, где он только что пошёл) превратилась в набор из k отдельных, не граничащих по сторонам друг с другом клеток (возможно, k=0), первый на второй полоске делает такой ход (назовём его «решающий»), чтобы их (изолированных клеток) там осталось на одну больше или на одну меньше, чем оставил на своей полоске второй игрок. Теперь все клетки изолированы друг от друга, их общее число является суммой двух последовательных чисел и потому нечётно, а тогда игроки будут красить их по очереди, начиная со второго игрока, которому и останется последняя проигрышная клетка.
Докажем, что решающий ход действительно можно осуществить. Пусть второй игрок закрасил прямоугольник l×1 клеток, после чего на его полоске остались изолированные незакрашенные клетки. Если закрашенный им прямоугольник граничил с одной или двумя незакрашенными клетками, первый при своём ходе может закрасить прямоугольник (l+1)×1, включающий тот, что закрашен соперником, и одну из этих клеток. Если же по обоим коротким сторонам от закрашенного вторым игроком прямоугольника l×1 были закрашенные клетки, то первый может закрасить его часть (l−1)×1, оставив лишнюю клетку с краю. Такой ход, казалось бы, невозможен при l=1, но это бы означало, что уже перед ходом второго игрока были бы только одиночные клетки, а мы уговорились, что они впервые появились только после его хода.