The arithmetic progression game and its variations: can you find optimal play?

Question

Consider the arithmetic progression game, a two-player game of perfect information, in which the players take turns playing natural numbers, or finite sets of natural numbers, all distinct, and the first player wins if there is a sufficiently long arithmetic progression amongst her numbers. This question grows out of Haoran Chen's question, A game on the integers, and my answer there.

We have a natural parameterized family of such games, depending on the number of integers each player is allowed to play on each move and the desired length of the winning arithmetic progression.

Specifically, for positive-valued functions $f,g$ on the natural numbers and natural number $n$, let $G(f,g,n)$ be the game in which

• Player A is allowed to play $f(i)$ many numbers on move $i$.
• Player B is allowed to play $g(i)$ many numbers on move $i$.
• Player A wins if she can form an arithmetic progression of length $n$ using her numbers.

All the integers played must be distinct.

Generalizing, let $G(f,g,\omega)$ be the game where player A aims in infinite play to create an infinite arithmetic progression in her set, and let $G(f,g,{<}\omega)$ be the game in which she wins by creating a set with arbitrarily large finite arithmetic progressions.

The original game at the other question was $G(1,k,5)$, with $k$ constant.

It is not difficult to see that all the games $G(f,g,n)$ are determined, meaning that one of the players has a winning strategy. After all, for finite $n$ the game $G(f,g,n)$ is an open game and therefore determined; and the infinitary games $G(f,g,\omega)$ and $G(f,g,<\omega)$ have winning conditions of complexity $\Sigma^0_2$ and $\Pi^0_2$, respectively, and all such games are determined because they are very low in the Borel hierarchy.

In my answer at the other question, I had made several observations.

• Player A wins the game $G(1,k,n)$, where player A plays one number on each move and player B plays at most a constant $k$ many numbers. The winning strategy for A is simply to play the smallest available number, which will ensure that set A has positive density, with proportion $1/(k+1)$ in any initial segment, and all such sets with positive density contain arbitrarily long arithmetic progressions by Szemerédi's theorem.

• Thus, actually, player A wins $G(f,k,<\omega)$ for any $f$ and any $k$, and all with the same strategy.

• A generalization of this argument adapts to show that if $g=O(f)$, then player A wins $G(f,g,n)$ and indeed $G(f,g,<\omega)$, since this hypothesis ensures that she can play a set with positive density, which will therefore have arbitrarily long finite arithmetic progressions.

• Meanwhile, a diagonal argument shows that player B wins $G(f,1,\omega)$ for any $f$, the game where player A is aiming to produce an infinite arithmetic progression, since player B can block the $n^{th}$ progression with a single number at step $n$.

• Thus, player B also wins $G(f,g,\omega)$ for any functions $f$ and $g$.

• Meanwhile, player B also wins $G(1,<\omega,3)$, since at each move player B can play all the numbers up to double the largest current number. This will prevent A from making three numbers in arithmetic progression.

• Indeed, a more refined version of this argument shows that player B wins $G(1,i-1,3)$, using the function $g(i)=i-1$, since at move $i$, player A has added one new number, which creates $i-1$ pairs with earlier numbers, and player B can block each of those pairs from continuing to an arithmetic progression of length $3$ by playing $i-1$ many blocking moves.

I have a number of questions.

Question 1. How quickly can player A win the game $G(1,k,n)$, where $k$ is constant? Is the always-play-the-smallest-available-number strategy in any sense close to (or far from) optimal?

Question 2. Does the game $G(1,k,n)$ have finite game value? That is, can we bound the length of play in advance, where the bound depends only on $k$ and $n$ and not on the particular moves of player B?

I presume the answer is yes, but note that not every open game has a finite game value.

Question 3. For which functions $g$ does player A win $G(1,g,n)$?

Above I argued that player A wins $G(1,g,3)$ for constant $g$, and player B wins for $g(i)=i-1$. For $n=3$, that bound seems likely close to optimal, since if player B ever fails to block a number, then player A can win. But of course, perhaps some of the numbers to be blocked had already been blocked at earlier stages of play. So the answer seems to be somewhere between the constant functions and the predecessor function.

Question 4. Can one show that every unbounded function $g$ enables player B to win $G(1,g,n)$ for some sufficiently large $n$?

Question 5. How much of the analysis carries over to the corresponding geometric progression games? That is, the games where player A aims to create geometric integer progressions.

I don't know if there is a geometric progression analogue of Szemerédi's theorem, but meanwhile, some of the other arguments do generalize.

Answer 1

Regarding Questions 1 and 2, at least for $G(1,k,3),$ player $A$ can easily win in little more than $k$ turns (and with a little thought in maybe $\frac{k}3.$) However player $B$ can force at least $k^{1.7095}$ turns before $A$ wins provided that $A$ is silly enough to neglect winning plays if they aren't the minimal choice. The exponent $1.7095$ is $\log_{3/2}2.$

For $G(1,k,n)$ the strategy I give will have $A$ win on some turn $(n-1)^j+1$ and to avoid that happening requires $k \geq \frac{n^j}{(n-1)^j}-1.$ If I analyzed that correctly, that means that $B$ can delay the win until at least turn $k^c$ where $c=\log_{\frac{m}{m-1}}(m-1).$

A non-integer $k$ can be interpreted as giving $B$ $\lfloor kt \rfloor-\lfloor k(t-1)\rfloor$ moves on turn $t.$

DETAILS

It is not hard to show that any $n$ term arithmetic progression of integers has a member which, when written in base $n$, uses the digit $n-1.$ Furthermore, If $x$ has a digit of $n-1$ then there is an arithmetic progression of length $n$ for which it is the last member and all the previous members do not have such a digit (the $j$ member of the progression is $x$ with all the $n-1$'s changed to $j-1$.)

The strategy for $B$ is to select the numbers having a $n-1$ in their base $n$ expansion. I analyze this (for $5$ term progressions) in my second answer to the question you mentioned.

So the strategy for $B$ in $G(1,k,3)$ (given that $A$ is blindly following the minimalist strategy) is to pick, in order, the integers with a $2$ in their base $3$ expansion (perhaps $k$ at a time.) This will leave $A$ picking the others and without a $3$ term progression until $B$ falls behind. This will happen on some turn $2^j+1$ with $A$ choosing a number in $[2\cdot3^{j-1},3^j-1].$ To avoid this happening requires $k \geq \frac{3^j-2^j}{2^j}.$

Here is an array showing the first $15$ turns. The meaning is that on turn $7$ $A$ will pick $12$ and on turn $8$ will pick $13.$ Before the next turn for $A,$ player $B$ must have eliminated all the $13$ integers in the range $[14,26].$ If this happens then $A$ will next choose $27$, otherwise $A$ wins on the next move.

$ \begin {array}{ccc} 1&0&\cdot\\ 2&1&2 \\ 3&3&\cdot\\ 4&4&5,6,7,8 \\ 5&9&\cdot\\ 6&10&11 \\ 7&12&\cdot\\ 8&13&14-26\\ 9&27&\cdot \\ 10&28&29\\ 11&30&\cdot \\ 12&31&32,33,34,35\\ 13&36&\cdot \\ 14&37&38\\ 15&39&\cdot \\ 16&40&41-80\end {array}$

So to not lose on turn $9,$ $B$ will have to have eliminated $19$ integers meaning that $k \geq \frac{19}{8}=\frac{3^3-2^3}{2^3}=2.375$ is required. With $k=2$ the game will go as follows:

$ \begin {array}{ccc} 1&0&2,5\\ 2&1&6,7 \\ 3&3&8,11\\ 4&4&14,15 \\ 5&9&16,17\\ 6&10&18,19 \\ 7&12&20,21\\ 8&13&22,23\\ 9&\mathbf{24!}&\text{ LOST} \end {array}$

Note that on turn $6$ $A$ will blindly pick the first available thing, namely $10.$ However $A$ would win on that turn if he completed $0,9,18.$

Answer 2

For $G(1,f,3)$, a more optimal strategy for A would be to choose the next available odd power of $2$, unless player A can complete a three term arithmetic progression on this turn.

The reason to choose odd powers of $2$ is that this prevents any "collisions" in the sense that on any round $n$ of the game the set of midpoints between two of A's choices has maximal size $\binom{n}{2}$, and the third elements of an arithmetic progression starting with two of A's choices has maximal size $\binom{n}{2}$. Furthermore, the odd power requirement ensures that these two sets don't overlap.

[Details: If $2^x < 2^y$ are two of player A's choices, the two arithmetic progressions are $2^x,2^{x-1}+2^{y-1},2^y$ and $2^x,2^y,2^{y+1}-2^x$. In either case, it's easy to recover $x$ and $y$ from the third element, whether $2^{x-1}+2^{y-1}$ or $2^{y+1}-2^x$. The restriction to odd $x$ ensures that the binary representation of $2^{x-1}+2^{y-1}$ never has consecutive set bits. On the other hand, the set bits of the binary representation of $2^{y+1}-2^x$ are all contiguous.]

In order for B to win against this strategy, player B must cover all of these third elements at each round. This is only possible if $\sum_{i=1}^n f(i) \geq 2\binom{n}{2}$ for each $n$. Otherwise player A's power of $2$ strategy will necessarily win as soon as B's choices fail to cover all of A's $2\binom{n}{2}$ ways to complete a three element arithmetic progression.

By skipping some odd powers of $2$ so that B cannot preemptively cover any of A's ways to finish a three term arithmetic progression, we see that A can win $G(1,f,3)$ unless $f(n) \geq 2n-2$ for every $n$.

This strategy doesn't require A to know anything about $f$. If A can additionally use information about $f$ then one can devise a winning strategy for A in $G(1,f,3)$ unless $f(n) \geq 3n-3$ for every $n$. The idea is to first choose an astronomical number $\omega$ and rather than playing odd powers of $2$, A chooses numbers of the form $\omega + 2^x$ where $x$ is odd. This way, because $\omega$ is very large, three term arithmetic progressions can also be completed below $\omega$ in addition to the two ways to complete them above $\omega$. Then there are the maximum $3\binom{n}{2}$ ways for player A to complete a three term at round $n$. Note that this requires that $\omega$ to be very large, but a suitable $\omega$ can be calculated using $f$ in such a way that $A$ wins on the first round where $f(n) < 3n-3$.

This is optimal. If $f(n)\geq 3n-3$ for every $n$, then B has a winning strategy by covering all of A's possible ways to complete a three term arithmetic progression at each step.

---

The games $G(r-2,f,r)$ admit a similar analysis. This time, player A's strategy is to pick sufficiently spread out powers of $(r-1)!$ shifted by an astronomical number $\omega$, unless player A can grab the remaining $r-2$ elements of an arithmetic progression containing two previous picks.

Let's look at $r=4$ for a concrete example. Then all of A's picks are powers of $6$. Given two such numbers $\omega+6^i < \omega+6^j$ there are $6 = \binom{4}{2}$ ways to fit these numbers in a four term arithmetic progression:

1. $\omega+6^i,\omega+6^j,\omega+2\cdot6^j-6^i,\omega+3\cdot6^j-3\cdot6^i$
2. $\omega+2\cdot6^i-6^j,\omega+6^i,\omega+6^j,\omega+2\cdot6^j-6^i$
3. $\omega+3\cdot6^i-2\cdot6^j,\omega+2\cdot6^i-6^j,\omega+6^i,\omega+6^j$
4. $\omega+6^i,\omega+6^i/2+6^j/2,\omega+6^j,\omega-6^i/2+3\cdot6^j/2$
5. $\omega+3\cdot6^i/2-6^j/2,\omega+6^i,\omega+6^i/2+6^j/2,\omega+6^j$
6. $\omega+6^i,\omega+2\cdot6^i/3+6^j/3,\omega+6^i/3+2\cdot6^j/3,\omega+6^j$

Excluding $\omega+6^i,\omega+6^j$, the union of these arithmetic progressions consists of the nine numbers $$F(i,j) = \left\{ \begin{split} &\omega+3\cdot6^i-2\cdot6^j,\quad & &\omega+2\cdot6^i-6^j,\quad & &\omega+3\cdot6^i/2-6^j/2, \\ &\omega+2\cdot6^i/3+6^j/3,\quad& &\omega+6^i/2+6^j/2,\quad& &\omega+6^i/3+2\cdot6^j/3, \\ &\omega-6^i/2+3\cdot6^j/2,\quad& &\omega+2\cdot6^j-6^i,\quad& &\omega+3\cdot6^j-2\cdot6^i \end{split}\right\}.$$ The "spread" requirements on picks by A should be that any two such sets are disjoint from each other, and disjoint from B's previous picks.

By inspection, in order to block all six arithmetic progressions containing $\omega+6^i$ and $\omega+6^j$, player B must pick at least four of the nine numbers from $F(i,j)$. This means that at round $n$, we must have $\sum_{i=1}^n f(i) \geq 4\binom{2n}{2}$. In fact, we must have $f(n) \geq 16n-12$ for every $n$ or else A's strategy will win at the first $n\geq1$ such that $f(n)<16n-12$.

Similar calculations for $r>4$ show that there is always a linear function $an+b$, where $a$ and $b$ depend on $r$, such that player A's strategy will win at the first $n$ such that $f(n)<an+b$, and player B has a winning strategy so long as $f(n) \geq an+b$ for all $n$.

Answer 3

The search term here is "Maker-Breaker arithmetic progression" or "Maker-Breaker van der Waerden". Maker is trying to build arithmetic progressions and Breaker is trying to stop them, without caring about building arithmetic progressions themself.

For every $n \in \mathbb N$ and every $0 < \delta \leq 1$ there is a finite $N = N(n,\delta)$ such that every subset of $[N]$ of size $\delta N$ contains an arithmetic progression of length $n$. Hence for question 2 the "take least unoccupied" strategy should be a win for Maker in at most $N(n,1/(k+1))$ steps.

Maker-Breaker games are often studied from the point of view of what bias (your $k$) allows Breaker to win. In view of Szemerédi's theorem that means "when played on a finite interval", but the literature on that problem might shed some light on questions 3 and 4.

By factorising each integer, question 5 is equivalent to looking at arithmetic progressions in the direct sum of countably many copies of $\mathbb N$. Only finitely many of the copies will be useful in an optimal (game length minimising) strategy for Maker.