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

Позиционная игра

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

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

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

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

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

Ссылки

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

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

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

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