Игра с арифметической прогрессией - Arithmetic progression game - Wikipedia

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

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

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

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

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

Рекомендации

1. Бек, Йожеф (1981). «Игры типа Ван дер Вардена и Рэмси». Комбинаторика. 1 (2): 103–116. Дои:10.1007 / bf02579267. ISSN  0209-9683.