Arithmetic progression game

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Arithmetic progression game" – news · newspapers · books · scholar · JSTOR (January 2019)

The arithmetic progression game is a positional game where two players alternately pick numbers, trying to occupy a complete arithmetic progression of a given size.

The game is parameterized by two integers n > k. The game-board is the set {1,...,n}. The winning-sets are all the arithmetic progressions of length k. In a Maker-Breaker game variant, the first player (Maker) wins by occupying a k-length arithmetic progression, otherwise the second player (Breaker) wins.

The game is also called the van der Waerden game,^[1] named after Van der Waerden's theorem. It says that, for any k, there exists some integer W(2,k) such that, if the integers {1, ..., W(2,k)} are partitioned arbitrarily into two sets, then at least one set contains an arithmetic progression of length k. This means that, if ${\displaystyle n\geq W(2,k)}$, then Maker has a winning strategy.

Unfortunately, this claim is not constructive - it does not show a specific strategy for Maker. Moreover, the current upper bound for W(2,k) is extremely large (the currently known bounds are: ${\displaystyle 2^{k}/k^{\varepsilon }<W(2,k)<2^{2^{2^{2^{2^{k+9}}}}}}$ for every ${\displaystyle \varepsilon >0}$).

Let W*(2,k) be the smallest integer such that Maker has a winning strategy. Beck^[1] proves that ${\displaystyle 2^{k-7k^{7/8}}<W^{*}(2,k)<k^{3}2^{k-4}}$. In particular, if ${\displaystyle k^{3}2^{k-4}<n}$, then the game is Maker's win (even though it is much smaller than the number that guarantees no-draw).

1. ^ ^{a b} Beck, József (1981). "Van der Waerden and Ramsey type games". Combinatorica. 1 (2): 103–116. doi:10.1007/bf02579267. ISSN 0209-9683.

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.

• v
• t
• e