Бесконечные конструкции (игры, клетки, множества)

Подсказка 1

Каким свойствами должен обладать предпоследний ход первого игрока, если последний является победным?

Подсказка 2

Ясно, что должно существовать не менее 101 свободной клетки, такие поставив крестик в любую из них, будет образован квадрат из крестиков. Довольно трудно следить за всеми клетками доски одновременно. Давайте ограничимся квадратом N на N - назовем его особенным, где N достаточно большое число (позже мы покажем, что оно существует) и будет ставить в остальные крестики в остальные поля. Наша цель - доказать, что после алгоритма заполнения остальных клеток появится искомая клетка.

Подсказка 3

Если a>=2, то за время его выполнения второй игрок поставит не менее 100N^2 ходов, следовательно, может заполнить квадрат, а значит такой алгоритм не поможет образовать искомую клетку. С другой же стороны если a<2, то при достаточно больших 100N^a < N^2, следовательно, после выполнения любого такого алгоритма в особенном квадрате еще останутся свободные клетки, что является необходимым условием для возможности победы. Теперь давайте определимся с тем, в какие клетки плоскости мы можем ставить остальные крестики.

Подсказка 4

Ясно, что в любом квадрате, который мы стремимся построить как минимум две противоположные вершины должны являться крестиками, клеток, стоящих в одной горизонтале или вертикале с клеткой особенного квадрата. Кроме этого, обе из этих клеток должны стоять на одной из диагоналей клеток нашей доски. Так, естественным будет попытка заполнить часть одной из диагоналей, которые лежат в одной вертикале/горизонтале с какой-то из клеток особенного квадрата. При каком a мы свободны заполнить по крайней мере n^a клеток этого множества, при необходимом a?

Подсказка 5

При любом a<1. Давайте не будет мелочиться и поставим в каждой из двух частей (первая часть - множество клеток, стоящих в одной вертикале с какой-то вертикалей особенного квадрата) каждой новой диагонали n^{0.99}. Это возможно, потому что каждый раз мы можем выбирать диагональ каждая клетка которой свободна. При каком a количество n^a диагоналей будет достаточно, для того, в особенном квадрате появилась клетка, для которой существует не менее 101 пары крестиков, стоящий в одной диагонале.

Подсказка 6

Пусть мы получили n^a диагоналей, в каждой из частей которой не менее n^0.99. Тогда общее количество пар крестиков, стоящих в одной диагонале, равно n^a n^{0.99} n^{0.99}, то есть n^{1.98+a}. Ясно, что если а <= 0.02, то общее количество пар меньше n^2, следовательно, возможна расстановка крестиков, когда для каждого клетки особенного квадрата стоит не более 1 квадрата - а значит искомых клеток может не найтись. Так a > 0.02. Тогда положим a = 0.03.

Подсказка 7

Числом клетки особенного квадрата назовем количество данных пар клеток. Чему может быть равно число клетки? Чему может быть равна сумма всех чисел клеток особенного квадрата?

Подсказка 8

Число клетки не превосходит общего количества заполненных диагоналей - n^0.03. Сумма чисел всех клеток равна количеству пар, стоящих в одной диагонале, но в разных частях. Их количество, как было посчитано ранее, не менее n^{2.01}. Предположим противное - каждая из еще не занятых клеток имеет число не более 101. Какое противоречие теперь можно получить?

Подсказка 9

Предъявите оценку снизу для суммы чисел всех клеток особенного квадрата и покажите, что она больше, чем n^{2.01}.