Республиканская олимпиада по математике, 2020 год, 11 класс

Марат и Алибек играют в игру на бесконечной в обе стороны клетчатой полоске, в которой клетки пронумерованы последовательными целыми числами слева направо ($\ldots$, $-2,$ $-1,$ 0, 1, 2, $\ldots$). Марат в свой ход ставит один крестик в любую свободную клетку, а Алибек в свой ход ставит нули в любые 2020 свободных клеток. Марат победит, если ему удастся получить такие 4 клетки отмеченные крестиками, что соответствующие номера клеток будут образовывать арифметическую прогрессию. Цель Алибека в этой игре — помешать Марату выиграть. Они ходят по очереди и первым ходит Марат. Сможет ли Марат выиграть как бы ни играл Алибек? ( Зиманов А. )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.    
Ответ. Да, сможет.
Приведём стратегию для Марата. Для удобства скажем, что $n = 2020$. До какого-то момента (до какого именно будет указано позже в решении) пусть Марат будет ставить крестики только в клетки с четными номерами.
Будем говорить, что клетка с номером $x$ левее клетки с номером $y$, если $x < y$ (аналогично, $x$ правее $y$, если $x > y$). Фигурой будем называть любое подмножество клеток полоски. Для фигуры $P$, через $|P|$ будем обозначать мощность множества клеток $P$, а длиной фигуры $P$ будем называть разность номеров самой правой и самой левой клетки $P$ и будем обозначеть её через $len(P)$. Будем говорить, что две фигуры равны, если одну из них можно получить из другой параллельным переносом вдоль полоски. Подфигурой какой-то фигуры $P$ будем называть фигуру $Q$, у которой множество клеток является подмножеством клеток какой-то фигуры $P'$ равной $P$. Переворотом фигуры $P$ будем называть фигуру $P'$ полученную следующим образом: Пусть $l$ и $r$ — это номера самой левой и самой правой клетки из $P$. Тогда в $P'$ войдут ровно все клетки $x$ такие, что клетка $l + r - x$ входит в $P$.
Определим алгоритм Копипаст для фигуры $P$: Пусть $l$ и $r$ — это номера самой левой и самой правой занятой чем угодно клетки. Зафиксируем целые $L$ и $R$ такие, что $r < L \le R$, $R - L = r - l$ и величина $L - r$ “достаточно” большая (позже в решении будет указано насколько большая). Назовем две клетки $l \le x \le r$ и $L \le y \le R$ соответственными, если $x - l = y - L$. Пусть $P'$ — фигура, соответствующая $P$ (мы будем подбирать $L$ и $R$ так, чтобы все клетки $P'$ были четными). Тогда Марат должен будет отмечать крестиками клетки из $P'$ пока может. Очевидно, что он всегда сможет отметить хотя бы $\dfrac{|P|}{(n + 1)}$ клеток. Будем полученную фигуру из новых крестиков называть результатом алгоритма. Тогда результат будет подфигурой $P'$, а значит и подфигурой $P$.
Пусть Марат в свои первые $k$ ходов будет ставить крестики произвольным образом и назовем фигурой $P_1$ то, что получилось из этих $k$ крестиков. Далее постороим последовательность фигур $P_2, P_3, … , P_t$ следующим образом: $P_{i + 1}$ — это результат Копипаста для фигуры $P_i$. Пусть $Q$ — результат Копипаста для переворота $P_t$. Далее мы снимаем ограничение с Марата ставить крестики только в четные клетки. Так как размер результата Копипаста для любой фигуры не меньше чем $\dfrac{1}{n + 1}$ от размера этой фигуры, то можно взять $k = c (n + 1) ^ t$ и таким образом получить, что размер $Q$ будет не меньше $c$ для сколь угодно большого $c$. Для нашей задачи достаточно взять $c = n + 1$ и, допустим, мы во время последнего Копипаста намеренно остановимся когда размер $Q$ станет ровно $n + 1$.
Рассмотрим произвольное $i$. Так как $Q$ — переворот какой-то подфигуры $P_i$ и все клетки в $P_i$ и $Q$ имеют четные номера, то существует такая клетка $m_i$, для которой выполнено следующее: для любой клетки $x$ из $Q$ клетка $2 m_i - x$ входит в $P_i$ (для фиксированного $i$ будем называть пару клеток $(x, 2 m_i - x)$ хорошей). В последнем Копипасте взяв $L - r > r - l + 100$ можно получить, что все клетки $m_i$ различны и свободны (так как все они будут правее $r$) перед постройкой $Q$. Теперь предположим, что мы уже построили $Q$. Допустим, что клетка $m_i$ оказалась свободна. Если мы поставим крестик в эту клетку, то каждая хорошая пара $(x, 2 m_i - x)$ создаст по угрозе арифметической прогрессии вида $(2 m_i - x, m_i, x, 2 x - m_i)$. Если все клетки вида $2 x - m_i$ (очевидно, что для фиксированного $i$ они все различны) тоже оказались свободными, то следующим своим ходом Алибек не успеет закрыть все угрозы (так как таких клеток $c = n + 1$, а Алибек одним ходом занимает всего $n$ клеток), значит хотя бы одна угроза ко следующему ходу Марата останется свободной и он сможет получить арифметическую прогрессию длины 4. Назовем множество клеток $\{m_i\} \cup \{2 x - m_i \ | \ \forall x \in Q\}$ $i$-ым кластером клеток, и при этом клетку $m_i$ в этом кластере будем называть сложной, а остальные — простыми. Значит, мы сейчас доказали, что если после постройки $Q$ (и соответствующего хода Алибека) найдется полностью свободный кластер, то Марат победил.
Теперь докажем, что можно аккуратненько выбирать $L$ и $R$ во время первых $t - 1$ Копипастов так, что пересечение любой пары различных кластеров будет пусто. Рассмотрим $i$-ый Копипаст (на котором мы построили $P_{i + 1}$ из $P_i$). Предположим, что мы уже построили $Q$. Пусть $a, b, c, d, e, f$ — самая левая клетка $P_i$, самая правая клетка $P_i$, самая левая клетка $P_{i + 1}$, самая правая клетка $P_{i + 1}$, самая левая клетка $Q$, самая правая клетка $Q$, соответственно. Тогда все простые клетки $i$-ого кластера будут лежать на отрезке $[1.5 e - 0.5 b, 1.5 f - 0.5 a]$, а все простые клетки $(i + 1)$-ого кластера будут лежать на отрезке $[1.5 e - 0.5 d, 1.5 f - 0.5 c]$. Тогда если мы сможем сделать $c - b > 3 (f - e)$, мы получим, что все простые клетки $i$-ого кластера будут лежать правее всех простых клеток $(i + 1)$-ого кластера. Так как длина результата Копипаста для любой фигуры не длиннее самой фигуры, то взяв $L - r > 3 \ len(P_1)$ получаем, что $c - b \ge L - r > 3 \ len(P_1) \ge 3 \ len(Q) = 3 (f - e)$.
Опять рассмотрим последний Копипаст. Если уже к поставленным ограничениям на $L$ и $R$ добавим такое: $L > r + 2 \ len(P_1)$, то после несложных выкладок получим, что все сложные клетки всех кластеров различны и находятся правее $r$ и левее самой левой клетки $Q$ и все простые клетки всех кластеров также попарно различны и находятся правее самой правой клетки $Q$. Наконец, возьмем $t = n (n + 1) + 1$. Так как $|Q| = n + 1$ и Алибек одним ходом закрывает ровно n клеток, то хотя бы один кластер по завершению построения $Q$ будет полностью свободным, а значит Марат победит.

Теорема Семереди: Для любого $k\in\mathbb{Z_{>0}}$ и $\varepsilon \in (0;1]$ существует натуральное $N$ так, что любое подмножество множества $\{1,2,\ldots, N\}$ мощности хотя бы $\varepsilon N$ содержит арифметическую прогрессию длины хотя бы $k.$

В частности, если $k=4$ и $\varepsilon = \frac{1}{2021}$, то Марат сможет поставить хотя бы $\frac{N}{2021}$ крестиков внутри полоски $[1;N]$ и задача решена.