Arithmetic progression game

Positional 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, 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 $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: $2^{k}/k^{\varepsilon }<W(2,k)<2^{2^{2^{2^{2^{k+9}}}}}$ for every $\varepsilon >0$ ).

Let W*(2,k) be the smallest integer such that Maker has a winning strategy. Beck proves that $2^{k-7k^{7/8}}<W^{*}(2,k)<k^{3}2^{k-4}$ . In particular, if $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).

References

^ 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 Misplaced Pages by expanding it.

Categories: