The arithmetic progression game is a

positional game A positional game is a kind of a combinatorial game for two players. It is described by: *Xa finite set of elements. Often ''X'' is called the ''board'' and its elements are called ''positions''. *\mathcala family of subsets of X. These subset ...

where two players alternately pick numbers, trying to occupy a complete

arithmetic progression An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...

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 A Maker-Breaker game is a kind of positional game. Like most positional games, it is described by its set of ''positions/points/elements'' (X) and its family of ''winning-sets'' (\mathcal- a family of subsets of X). It is played by two players, ca ...

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 Van der Waerden's theorem is a theorem in the branch of mathematics called Ramsey theory. Van der Waerden's theorem states that for any given positive integers ''r'' and ''k'', there is some number ''N'' such that if the integers are colored, eac ...

. 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^\varepsilon < W(2,k) < 2^

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

Beck Beck David Hansen (born Bek David Campbell; July 8, 1970) is an American musician, singer, songwriter, and record producer. He rose to fame in the early 1990s with his Experimental music, experimental and Lo-fi music, lo-fi style, and became ...

proves that

2^ < W^*(2,k) < k^3 2^

. In particular, if

k^3 2^ < n

, then the game is Maker's win (even though it is much smaller than the number that guarantees no-draw).

References

Positional games {{math-stub