Игра «Арифметическая прогрессия»

Игра в арифметическую прогрессию — это позиционная игра , в которой два игрока поочередно выбирают числа, стремясь занять полную арифметическую прогрессию заданного размера.

Игра параметризуется двумя целыми числами n > k . Игровое поле представляет собой набор {1,..., n }. Выигрышными наборами являются все арифметические прогрессии длины k . В варианте игры Maker-Breaker первый игрок (Maker) побеждает, занимая арифметическую прогрессию длины k , в противном случае побеждает второй игрок (Breaker).

Эту игру еще называют игрой Ван дер Вардена . назван в честь теоремы Ван дер Вардена . Он говорит, что для любого k существует некоторое целое число W (2, k ) такое, что если целые числа {1, ..., W (2, k )} произвольно разделены на два множества, то хотя бы одно множество содержит арифметическую прогрессию длины k . Это означает, что если $n\geq W(2,k)$, то у Maker есть выигрышная стратегия.

К сожалению, это утверждение неконструктивно — оно не указывает на конкретную стратегию Maker. Более того, текущая верхняя граница для W (2, k ) чрезвычайно велика (известные на данный момент границы: $2^{k}/k^{\varepsilon }<W(2,k)<2^{2^{2^{2^{k+9}}}}$).

Пусть W *(2, k ) — наименьшее целое число, такое, что у Maker есть выигрышная стратегия. Бек доказывает, что $2^{k-7k^{7/8}}<W^{*}(2,k)<k^{3}2^{k-4}$. В частности, если $k^{3}2^{k-4}<n$, то игра является выигрышем Создателя (хотя оно намного меньше числа, гарантирующего отсутствие ничьей).