A game on integers

Question

$A$ and $B$ take turns to pick integers: $A$ picks one integer and then $B$ picks $k > 1$ integers ($k$ being fixed). A player cannot pick a number that his opponent has picked. If $A$ has $5$ integers that form an arithmetic sequence, then $A$ wins. $B$'s goal is to prevent that from happening. Who has a winning strategy (after finite number of turns)? Does it depend on $k$?

Answer 1

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.

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.

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 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? What if $f=o(2^i)$?

Answer 2

Joel's answer uses heavy machinery to give a much stronger result. Below is a strong result for $k=1$ using heavy computations (not mine.)

My suspicion is that for the question as asked there might be a relatively simple strategy. However I don't have one.

For $k=1,$ player A can win even with the further restrictions that the progression $1 \leq a,a+d,a+2d,a+3d,a+4d$ must have $d \in \{1,14,15,16\}$ and $a+4d \leq 225$ and that $B$ wins if they get such an arithmetic progression.

This is based on the game Gomoku played on a $15 \times 15$ board. According to the linked article, computer analysis shows that the game is a first player win. Numbering grid intersect $(i,j)$ with $i+15(j-1)$ gives the correspondence. Since humans still play the game in tournaments, it isn't trivial to find a strategy (though there may be rules to even things out).

Allowing arbitrary arithmetic progression gives A many more ways to win, although $k \gt 1$ is also an advantage for B.

Answer 3

The minimalist strategy for $A$ of "don't think, just pick the smallest unchosen non-negative integer!" has a simple counter strategy for $B$ which is interesting to analyze as to how far it gets before it eventually fails. I wonder how good it is.

The number of turns for $A$ before winning increases exponentially with $k$ (provided $A$ uses this minimalist strategy and $B$ uses the one I will describe.) This is true also for thee term arithmetic progressions.

Consider the game where $A$ needs to get an arithmetic progression of length $m$ to win and $B$ gets $k$ choices each turn. Then I think my strategy for $B$ matched with the minimalist strategy for $A$ will have $A$ win on a turn no smaller than $k^c$ where $$c=\log_{\frac{m}{m-1}}(m-1).$$

A better strategy (for three term sequences) for $A$ would win in $k+2$ turns (this could easily be improved to $\frac{k}3$ turns.) Roughly, on the first $k$ turns $A$ selects available even numbers $a_1,\cdots,a_{k}$ then, whatever choices $B$ has made so far, it is possible to pick an even $a_{k+1}$ so that none of $\frac{a_{k+1}-a_i}2$ have been chosen yet. $B$ must leave one of those unchosen on her turn so $A$ picks that next turn and wins.

How to extend this to longer progressions is not clear however that argument shows that wlog $A$ gets three free moves on the first turn (we could arrange that the entire progression determined by $a_i,a_{k+1}$ is free.)

Below is a strategy for $B$ if she knows for sure that $A$ will blindly follow the minimalist strategy. The moves are all known in advance so it is just a question of when $A$ wins. For ease of analysis I will allow $k \gt 0$ to be any real number and interpret this as: on turn $t$ if $B$ has previously chosen $m$ integers she has $\lfloor kt \rfloor-m$ moves available and can make none or some or all and hold the rest for future turns.

The strategy is that she will pick in order the non-negative integers with a $4$ in their base $5$ expansion and let $A$ work up through the rest one at a time. This blocks any $5$ term progressions as long as $B$ stays ahead. However $B$ will save her moves and only pick enough numbers that $A$ will not win on the next turn (which may turn out to take more moves than she has).

When $B$ loses it will because $A$ was able to play a number in some interval $[5^j-5^{j-1},5^j-1].$ This will happen in the event that $$\frac{5^{j-1}-4^{j-1}}{4^{j-1}} \leq k \lt \frac{5^{j}-4^{j}}{4^{j}}.$$ The exact winning move depends on where $k$ falls in that range.

For example, If $k \geq \frac{61}{64} =0.953125$ then $A$ at some point picks $125$ without having won. No problems occur until after the turn when $A$ picks $468=3333_5.$ At this point anything in $[469,624]$ would be a winner for $A$ on the next move. But $B$ has moves in reserve, certainly enough to choose all of $[629,499].$ However to be able to go on and choose all of $[500,634]$ requires $k \geq \frac{369}{256}=1.44140625.$ If so, then everything is good until at least $2499.$