Задача 30 из брошюрки Шеня «Игры и стратегии с точки зрения математики»:
Цитата:
Двое игроков ставят крестики и нолики на бесконечной клетчатой бумаге, причём на каждый крестик первого игрока второй отвечает
ноликами. Докажите, что первый может добиться, чтобы некоторые четыре крестика образовали квадрат (со сторонами, параллельными линиям клеток).
Ясно, что число
можно заменить на
, и оно никакой особой роли не играет.
Я пыталась решить задачу разными способами, все они опирались на принцип Дирихле. Неплохо бы было научиться делать «арифметические прогрессии из крестиков», то есть произвольно много крестиков, находящихся на одной линии и располагающихся через фиксированное количество клеток. Но даже этого пока не выходит. Была мысль делить линию на прямоугольники
, или всю плоскость на квадраты, как-то применять индукцию, но все это было бесполезно. Ещё я пыталась использовать идею решения одной похожей задачи:
Цитата:
Плоскость раскрашена в 100 цветов. Докажите, что найдется прямоугольник с вершинами одного цвета.
Но она в разы проще, и даже если бы была возможность строить арифметические прогрессии произвольной длины, не получается свести эту задачу к ней. (Хотя если континуальную плоскость заменить на счетную клетчатую бумагу, то решение там не изменится).
