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

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

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

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

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

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

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

Этот игра -связанная статья является заглушка. Вы можете помочь Википедии расширяя это.

Эта статья по математике заглушка. Вы можете помочь Википедии расширяя это.