Skip to main content
3 of 6
added 374 characters in body
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

Player A has a winning strategy, and furthermore, it is a winning strategy simply to play the smallest available number.

I assume $k$ is fixed, and I claim that we can replace $5$ with any number for the winning condition. So consider the game $G_{n,k}$ in which player A plays one integer each turn and player B plays $k$ integers each turn, with all of them distinct; player A wins when there is a length $n$ arithmetic sequence amongst her numbers.

This game is open for player A, since every win happens at a finite stage of play if at all. So it is determined by the Gale Stewart theorem.

But in fact, we don't need that, since we can describe explicitly a winning strategy for player A: let her simply play the smallest available integer. In any infinite play of the game, it follows that every integer will be played, and the set played by A will have proportion at least $1/(k+1)$ in any initial segment. Thus, the set played by A will have positive density. It follows by Szemerédi's theorem that the set played by A must contain arbitrarily long arithmetic progressions. So player A will have won at some stage.

The argument shows that one can consider an infinite version of the game, where player A must play a set with arbitrarily long arithmetic progressions.

But one cannot insist on an infinite arithmetic progression, since there are only countably many such progressions, and player B can diagonalize against them, even when $k=1$, by playing so as to block the $n^{th}$ such infinite sequence on his $n^{th}$ move. So player B wins the version of the game where A must produce a set covering an infinite arithmetic progression.

Lastly, let me add that if $k$ is not fixed, so that player B is free to play an arbitrary finite set on each move, then player B can easily win by playing all the available numbers up to twice the current largest value played. This prevents any further number played by A of forming an arithmetic progression even of length 3.

Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k