// Workers AI · dad joke modeDoes an arithmetic progression game add up to fun?

In combinatorial game theory, an 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,\dots ,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,\dots ,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.

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).