На бесконечном листе клетчатой бумаги двое играют в такую игру: первый окрашивает какую-нибудь клетку в красный цвет, второй — $k$ (неокрашенных) клеток — в синий цвет, затем снова первый одну (неокрашенную) — в красный, второй — $k$ клеток — в синий и т. д. Первый стремится к тому, чтобы какие-нибудь четыре красные клетки расположились в вершинах квадрата (со сторонами, параллельными линиям сетки). Сможет ли второй ему помешать
Рис. 1. Выигрышные позиции для первого игрока а) при произвольном $k\ge1$; б) при $k=1$. Клетки, обведённые рамками, не окрашены ни красным, ни синим цветом. Звёздочкой помечена последняя клетка, окрашенная первым игрокомРис. 2Рис. 3
Ответ: второй игрок не сможет помешать первому ни при каком $k$.
Решать задачу удобно с конца. Ясно, что первый игрок (будем называть его $K$ — «красный») выиграет, если каким-то своим ходом он построит сразу $k+1$ «неполных» квадратов, в трёх вершинах каждого из которых стоят красные клетки, а в четвёртой — неокрашенная. Тогда после ответа второго игрока (назовём его $C$ — «синий») хотя бы одна из четвёртых вершин останется неокрашенной и, окрасив её, $K$ получит «красный квадрат». Примеры таких выигрышных позиций приведены на рисунках 1, a — для общего случая — и 1, б — для $k=1$ (в последнем случае $K$ может действовать так же, как и в общем, при произвольном $k\ge1$, но у него есть и более экономный путь к победе, использующий симметрию квадратной решётки). Объясним, как должен играть $K$, чтобы получить эти позиции.
а) Пусть $a$ и $a'$ — первые клетки, окрашенные, соответственно, игроками $K$ и $C$ (рис. 2). Вторым ходом $K$ окрашивает клетку $b$, стоящую в одном столбце с $a$ так, что расстояние между клетками $b$ и $a$ больше, чем между $a'$ и $a$. После ответного хода $C$ одна из клеток $c$ и $c_1$ того же столбца (см. рис. 2), например, $c$, останется неокрашенной. Её окрашивает $K$ третьим ходом. Аналогично, четвёртым ходом $K$ окрашивает клетку $d$ или $d_1$. Допустим, он окрасил $d$, тогда рассмотрим столбцы, содержащие клетки $e$, $f$, $g$ и $h$. Один из них, например, содержащий $e$, свободен от синих клеток, потому что синих клеток всего четыре и одна из них — $a'$ — заведомо не стоит в этих столбцах. Окрасив $e$, игрок $K$ получит позицию рисунка 1, б (клетки $a$, $b$, $c$ и $e$ на рисунке 2).
б), в) Игрок $K$ начинает с того, что окрашивает $N$ клеток одной строки, не обращая внимания на расстояния между ними (число $N$ зависит от $k$; мы уточним его ниже). Затем под первой строкой $K$ выбирает строку, в которой нет синих клеток, и окрашивает в ней клетки, стоящие точно под красными клетками первой строки (пока среди них ещё есть неокрашенные красным или синим цветом). Под второй строкой $K$ выбирает третью (свободную от синих клеток) и окрашивает в ней клетки, стоящие под красными клетками второй строки, и т. д. Заполнив таким образом $n$ строк (число $n$ определим позже), $K$ должен выбрать прямую $l$, проходящую по диагоналям клеток (рис. 3) под всеми окрашенными клетками (красными и синими), и окрасить на ней $k+1$ клеток, стоящих точно под клетками последней, $n$-й строки. Поскольку на каждую новую красную клетку приходится $k$ синих, для этого достаточно, чтобы в $n$-й строке было $k^2+k+1$ красных клеток. (Тогда в ответ на первые $k$ клеток прямой $l$, которые окрасит $K$, $C$ окрасит $k^2$ клеток, после чего под красными клетками $n$-й строки на прямой $l$ останется ещё хотя бы одна неокрашенная клетка.) Красные клетки на прямой $l$ вместе с лежащими над ними клетками одной из $n$ строк и клеткой $a$ на пересечении этой строки с прямой $l$ (рис. 3) и образуют выигрышный «клин», показанный на рисунке 1, a. Надо только выбрать эту строку так, чтобы клетка $a$ и все клетки под ней не были синими. А это всегда можно сделать, если число строк $n$ больше числа синих клеток на прямой $l$ и под ней, которое не превосходит $(k+1)k=k^2+k$, например, при $n=k^2+k+1$.
Итак, число $N$ должно быть настолько велико, чтобы игрок $K$ смог заполнить указанным образом $n=k^2+k+1$ строк и окрасить в последней $n$ клеток. Можно взять $N=(k+1)^n\cdot k+1$. Действительно, как мы видели, чтобы $K$ мог окрасить $k+1$ клеток на прямой $l$, в $n$-й строке надо было окрасить $(k+1)\cdot k+1$ клеток красным цветом; аналогично доказывается, что для этого в $(n-1)$-й строке должно находиться $(k+1)^2\cdot k+1$ красных клеток, в $(n-2)$-й — $(k+1)^3\cdot k+1$, $\ldots$, а в первой — $(k+1)^n\cdot k+1$ красных клеток.
Отметим, что это решение идейно близко к решению задачи M750 («Квант», 1982, № 12; см. также статью С. Н. Беспамятных в «Кванте» № 6 за этот год).
