Return to Answer

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.

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.$

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.$

If $B$ knows for sure that $A$ will blindly follow the strategy of "don't think, just pick the smallest unchosen non-negative integer!”, then 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.

Before going on let me note that it would be possible to consider rational or real $k$ that aren't integers. This would perhaps allow $B$ to make $\lfloor kt \rfloor -\lfloor k(t-1) \rfloor$ moves on turn $t.$ That might be nicer if one was to look more carefully at the next claims.

How big must $k$ be so that $A$ chooses $5^{j}$ without having won previously? That is rather a hurdle. On that move $A$ has chosen the $4^j$ smaller non-negative integers without a $4$ (the largest of which is $\frac34(5^j-1)$ ) and $B$ has chosen the other $5^j-4^j.$ So it requires $k \geq \frac{5^j-4^j}{4^j}.$ (This is where a non-integer $k$ could be easier.) That, with some not totally correct reasoning, suggests that If $B$ gets $k$ moves then she can make it to $5^{\log_{5/4}(k+1)}.$ More precisely, she can't make it past there but might fail somewhat earlier. I won't look at that further because the strategy requires $A$ to ignore a winning move if anything smaller can be chosen. And $A$ will sometimes chose numbers which can't be in a progression with anything smaller.

Here are some small steps toward a possible simple winning strategy for $A$ which is the opposite of Joel's : Always play the LARGEST available number (for a while, then go in for the kill). Of course that doesn't make literal sense but I will explain.

I will assume that the game is played on $\mathbb{Z}.$ If my approach works then it could likely be transferred to $\mathbb{N}.$

First I'll note that wlog player $A$ gets to pick two integers on the very first move: Suppose that A plays $a_1=0$ and then $B$ plays her $k$ integers $b_1,b_2,\cdots,b_k$. Then A can choose on the second round an integer $a_2=n$ which is larger than $\max|b_i|$ and announce "From now on I will only play multiples of $n.$" This makes all of B's first moves irrelevant.

Actually, it would be better to play $a_2=12n$. Then there are $10$ five term progressions using $0$ and $12n$ including

$[-36,-24,-12,0,12]n,[0,12,24,36,48]n,[0,4,8,12,16]n,[0,3,6,9,12]n$

so to block them all on the next turn would take at least $4$ of the next moves by $B$.

Furthermore, $A$ could say "I will probably only play multiples of $n$" allowing for a deviation if it is helpful.

For integers $x \lt y$ let $P(x,y)$ denote the $10$ five term rational arithmetic progressions using $x$ and $y$. We will require $x,y \in 12 \mathbb{Z}$ hence these are all integer arithmetic progressions. Also, let $Q(x,y)$ be $x+\frac{y-x}{12}\mathbb{Z}$

I haven't pushed this much further, but once $A$ has chosen $a_1,a_2,\cdots,a_{t-1} \in 12\mathbb{Z}$ and $B$ has chosen $b_1,\cdots,b_{kt-k}$ it is possible to pick $a_{t}\in 12\mathbb{Z}$ so large that

• None of the members of any $P(a_i,a_{t})$ are blocked by a previously chosen $b$. Indeed, we may as well require that none of the $b_i$ are in any of the $Q(a_i,a_t).$

• Every member of $P(a_i,a_t)$ is disjoint from every member of $P(a_j,a_t)$ except for their shared member $a_t.$

Perhaps renumber for clarity sending $x$ to $x'=a_t-x.$ Then $Q(a_i,a_t)$ becomes $m_i\mathbb{Z}$

This means that wlog $A$ gets to pick three numbers on the first term: Just continue as above until $t \gt k+1.$ Then there is an $i$ so that $Q(a_i,a_t)$ is untouched after the next move by $B.$ With the renumbering this is just some $m\mathbb{Z}$ where $A$ has chosen $0$ and $12m$ with everything else untouched. So only look at its members.

I can think of nice choices for a third thing, such as $24m,$ but the way forward is unclear. We could certainly jump to a far far distant region of the integers and come up with a second three term progression. Perhaps instead of $12\mathbb{Z}$ we should use $12^2\mathbb{Z}$ to allow for multiple scales.

Let an open $4$ be $a-d,a,a+d,a+2d$ owned by $A$ with $a-d$ and $a+3d$ currently un-chosen. Then $A$ wins on the next move if he has more than $\frac{k}2$ open $4$'s. Also, let an open $3$ be a sequence $a-d,a,a+d$ owned by $A$ with $a\pm 2d$ and $a\pm 3d$ currently un-chosen.The having $k+1$ open $3$'s allows an open 4 on the next move..

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.

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.$

If $B$ knows for sure that $A$ will blindly follow the strategy of "don't think, just pick the smallest unchosen non-negative integer, then 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.

How big must $k$ be so that $A$ chooses $5^{j}$ without having won previously? That is rather a hurdle. On that move $A$ has chosen the $4^j$ smaller non-negative integers without a $4$ (the largest of which is $\frac34(5^j-1)$ ) and $B$ has chosen the other $5^j-4^j.$ So it requires $k \geq \frac{5^j-4^j}{4^j}.$ (this is where a non-integer $k$ could be easier.) That, with some not totally correct reasoning, suggests that If $B$ gets $k$ moves then she can make it to $5^{\log_{5/4}(k+1)}.$ More precisely, she can't make it past there but might fail somewhat earlier. I won't look at that further because the strategy requires $A$ to ignore a winning move if anything smaller can be chosen. And $A$ will sometimes chose numbers which can't be in a progression with anything smaller.

so to block them all on the next move would take at least $4$ of the next moves by $B$.

I can think of nice choices such as $24m,$ but the way forward is unclear. We could certainly jump to a far far distant region of the integers and come up with a second three term progression. Perhaps instead of $12\mathbb{Z}$ we should use $12^2\mathbb{Z}$ to allow for multiple scales.

If $B$ knows for sure that $A$ will blindly follow the strategy of "don't think, just pick the smallest unchosen non-negative integer!”, then 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.

How big must $k$ be so that $A$ chooses $5^{j}$ without having won previously? That is rather a hurdle. On that move $A$ has chosen the $4^j$ smaller non-negative integers without a $4$ (the largest of which is $\frac34(5^j-1)$ ) and $B$ has chosen the other $5^j-4^j.$ So it requires $k \geq \frac{5^j-4^j}{4^j}.$ (This is where a non-integer $k$ could be easier.) That, with some not totally correct reasoning, suggests that If $B$ gets $k$ moves then she can make it to $5^{\log_{5/4}(k+1)}.$ More precisely, she can't make it past there but might fail somewhat earlier. I won't look at that further because the strategy requires $A$ to ignore a winning move if anything smaller can be chosen. And $A$ will sometimes chose numbers which can't be in a progression with anything smaller.

so to block them all on the next turn would take at least $4$ of the next moves by $B$.

I can think of nice choices for a third thing, such as $24m,$ but the way forward is unclear. We could certainly jump to a far far distant region of the integers and come up with a second three term progression. Perhaps instead of $12\mathbb{Z}$ we should use $12^2\mathbb{Z}$ to allow for multiple scales.