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

Марат пен Әлібек екі жаққа шексіз созылған шаршылы жолақта ойын ойнайды. Жолақ шаршылары қатар келген бүтін сандармен солдан оңға қарай нөмірленген ($\ldots$, $-2,$ $-1,$ 0, 1, 2, $\ldots$). Марат өз жүрісінде кез келген бос шаршыға крест қояды, ал Әлібек өз жүрісінде кез келген 2020 бос шаршыларға нөл қояды. Егер Марат, нөмірлері арифметикалық прогрессия құрайтын төрт крест қойылған шаршылар ала алса, онда ол жеңеді. Әлібектің мақсаты — Маратқа төтеп беру. Олар кезектесіп жүреді, және ойынды Марат бастайды. Әлібектің қалай ойнағанына да қарамастан, Марат осы ойынды ұта алады ма? ( Зиманов А. )

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

Комментарии от администратора Комментарии от администратора №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]$ и задача решена.