Arithmetic progression game explained

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 . 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 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 ^{k+9}}}} ).

Let W*(2,k) be the smallest integer such that Maker has a winning strategy. Beck proves that

2 ^{k -7 k ^{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).

Notes and References

1. Beck. József. 1981. Van der Waerden and Ramsey type games. Combinatorica. en. 1. 2. 103–116. 10.1007/bf02579267. 0209-9683.