Return to Answer

Question 3. For which functions $f$ does player A still have a winning strategy? For example, if $f$ is linear or even polynomial, does player A have a winning strategy?

Question 3. For which functions $f$ does player A still have a winning strategy? For example, if $f$ is linear or even polynomial, does player A have a winning strategy? What if $f=o(2^i)$?

In any infinite play of the game played according to this strategy, the set played by A will have proportion at least $1/(k+1)$ in any initial segment of the positive integers. Thus, the set played by A will have positive asymptotic 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 already won at some stage. So it is a winning strategy.

Further remarks. In the original $G_k^n$ game, the play-the-smallest-available-number strategy is a winning strategy, but I am not sure how long this takes to win, or whether this strategy is efficient in any sense in winning. Perhaps the finite combinatorics experts can place bounds on how long the game will take. Presumably there is a number $N$, depending on $n$ and $k$, such that player A can force a win in at most $N$ moves, but I don't know how big $N$ will be or even whether there is such an $N$. The existence of such a number $N$ is equivalent to the assertion that this game has a finite game value (but note that not all open games have a finite game value).

To see that this is a winning strategy, consider any infinite play of the game played according to it. For such a play, the key observation to make is that this strategy ensures that the set of numbers played by A will have proportion at least $1/(k+1)$ in any initial segment of the positive integers. In particular, the set played by A will have positive asymptotic 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 already won at some stage. So it is a winning strategy.

Further remarks and questions. In the original $G_k^n$ game, the play-the-smallest-available-number strategy is a winning strategy, but I am not sure how long this takes to win, or whether this strategy is efficient in any sense in winning. Perhaps the finite combinatorics experts can place bounds on how long the game will take. Presumably there is a number $N$, depending on $n$ and $k$, such that player A can force a win in at most $N$ moves, but I don't know how big $N$ will be or even whether there is such an $N$. The existence of such a number $N$ is equivalent to the assertion that this game has a finite game value (but note that not all open games have a finite game value).

Question 1. How quickly can player A win the game $G_k^n$? Does the play-the-smallest-available-number strategy achieve the best bound?

Question 2. For fixed $n$ and $k$, is there a uniform bound $N_k^n$ for the length of play, not depending on the moves of player B?

In the game where $k$ is not fixed, one can imagine the game $G_f^n$, where the function $f:\mathbb{N}\to\mathbb{N}$ is used to specify the size $f(i)$ of the set played by B on move $i$. The argument I gave shows that if $f$ is sufficiently exponential, then player B wins. Meanwhile, constant functions $f(i)=k$ correspond to the original arithmetic progression game.

Question 3. For which functions $f$ does player A still have a winning strategy? For example, if $f$ is linear or even polynomial, does player A have a winning strategy?

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.

I claim that Player A has a winning strategy in your game, and furthermore, it is a winning strategy for her simply to play the smallest available number.

Let me consider the game along with several natural variations.

Player A wins the original arithmetic progression game. To be a little more specific about the game, let us consider what I should like to propose we call the arithmetic progression game $G_k^n$ for positive integers $k$ and $n$, a two-player game of perfect information. On each turn, player A plays a new integer and player B plays up to $k$ integers, with all played numbers distinct; player A wins if there is an arithmetic progression of length $n$ amongst her numbers, and player B is aiming to prevent this.

In this notation, your original game is $G_k^5$. These are all open games for player A, meaning that any win for player A, if it occurs, will occur at a finite stage of play. It follows by the Gale-Stewart theorem that one of the players will have a winning strategy.

But in fact, we can explicitly describe a winning strategy for player A: let her simply play the smallest available positive integer. I find it interesting that the same strategy works uniformly in $n$ and $k$, and player A doesn't even have to know these game parameters in advance. Further, the strategy doesn't depend on the history of play, but only on the current sets of already-played numbers. 

In any infinite play of the game played according to this strategy, the set played by A will have proportion at least $1/(k+1)$ in any initial segment of the positive integers. Thus, the set played by A will have positive asymptotic 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 already won at some stage. So it is a winning strategy.

Let us consider several natural variations of the game.

Player A wins the arbitrarily long finite progressions game. Consider an infinite version of the game, denoted $G_k^{<\omega}$, where play continues through all finite stages, and player A wins such an infinite play if the set of her numbers contains arithmetic progressions of every finite length. The argument above using Szemerédi's theorem shows that the play-the-smallest-available-number strategy is still a winning strategy for player A in this modified game, since she can ensure that her set has positive density and therefore contains arithmetic progressions of any desired length.

Player B wins the infinite arithmetic progression game. If we modify the winning condition of the game, however, to the game $G_k^\omega$, where player A wins only when her set contains an infinite arithmetic progression, then I claim that player B has a winning strategy. The reason is that there are only countably many infinite arithmetic progressions in the integers, since each is determined by its starting point and the difference. Since there are only finitely many numbers played by any given finite stage of play, it follows that player B can block the $n^{th}$ infinite arithmetic progression with a single number played on move $n$. So even when $k=1$, player B has a winning strategy to block an infinite arithmetic progression in A's set.

Player B wins the variant where $k$ is not fixed. Lastly, consider the version of the game where $k$ is not fixed, so that player B is free to play an arbitrary finite set on each move. We may denote it by $G_{<\omega}^n$. For this variant, player B has a winning strategy to block all arithmetic progressions even of length $n=3$ for A. The strategy is simply to fill in all the numbers up to double the current largest number played. In this way, no three numbers played by A can have their differences in an arithmetic progression, since each next number played by A has a larger difference than any two previous numbers. So this is a winning strategy to prevent A from forming an arithmetic progression of length $3$.

Further remarks. In the original $G_k^n$ game, the play-the-smallest-available-number strategy is a winning strategy, but I am not sure how long this takes to win, or whether this strategy is efficient in any sense in winning. Perhaps the finite combinatorics experts can place bounds on how long the game will take. Presumably there is a number $N$, depending on $n$ and $k$, such that player A can force a win in at most $N$ moves, but I don't know how big $N$ will be or even whether there is such an $N$. The existence of such a number $N$ is equivalent to the assertion that this game has a finite game value (but note that not all open games have a finite game value).