Alice and Bob make all numbers to zero game

Question

Alice and Bob are playing a number game in which they write $N$ positive integers. Then the players take turns, Alice took first turn.

In a turn :

• A player selects one of the integers, divides it by $2, 3, 4, 5$ or $6$, and then takes the floor to make it an integer again.
• If the integer becomes 0, it is erased from the board.
• The player who makes the last move wins.

Assuming both play optimally, we need to predict who wins the game.

Example : Let N=2 and numbers are [3,4] then alice is going to win this one.

Explanation :

Alice can win by selecting 4 and then dividing it by 2. The integers on the board are now [3,2]. Bob can make any choice, but Alice will always win.

• Bob can divide 2 by 3, 4, 5 or 6, making it 0 and removing it. Now only one integer remains on the board, 3, and Alice can just divide it by 6 to finish, and win, the game.
• Bob can divide 3 by 4, 5 or 6, making it 0 and removing it. Now only one integer remains on the board, 2, and Alice can just divide it by 6 to finish, and win, the game.
• Bob can divide 2 by 2. Now the integers are [1,3]. Alice can respond by dividing 3 by 3. The integers are now [1,1]. Now Bob has no choice but to divide 1 by 2, 3, 4, 5 or 6 and remove it (because it becomes 0). Alice can respond by dividing the remaining 1 by 2 to finish, and win, the game.
• Bob can divide 3 by 2 or 3. Now the integers are [1,2]. Alice can respond by dividing 2 by 2. The integers are now [1,1]. This leads to a situation as in the previous case and Alice wins.

Answer 1

Background

If you're unfamiliar with Sprague-Grundy theory or the strategy for Nim, check out this community wiki collection of tutorials about them, because they're necessary for getting the answer for large $N$, and I'll be assuming familiarity with them.

---

Since there are two players and the player who makes the last move wins, the Sprague-Grundy theorem applies, and these sorts of games combine as if they were Nim in disguise. But since players only divide a single number on their turn, a game is a disjunctive sum of games where $N=1$, and we can use the strategy for Nim to analyze all $N>1$ if we know the nimbers/Grundy values for $N=1$.

Grundy Values for $N=1$

Claim:

Suppose there is a single number $n\ge1$. Then the Grundy value of the game is:

• $1$ if the first base-12 digit of $n$ is $1$ (that is, if $n\in[12^k,2*12^k)$ for some $k\ge0$)
• $2$ if the first base-12 digit of $n$ is $2$ or $3$ (if $n\in[2*12^k,4*12^k)$ for some $k$)
• $3$ if the first base-12 digit of $n$ is $4$ or $5$ (if $n\in[4*12^k,6*12^k)$ for some $k$)
• $0$ if the first base-12 digit of $n$ is $6$ or higher (if $n\in[6*12^k,12^{k+1})$ for some $k$)

Alternatively, if you prefer an ugly formula using floor, the Grundy values are given by: $$G\left(n\right)=\begin{cases} 1 & \text{if }n*12^{-\left\lfloor \log_{12}n\right\rfloor }<2\\ 2 & \text{if }2\le n*12^{-\left\lfloor \log_{12}n\right\rfloor }<4\\ 3 & \text{if }4\le n*12^{-\left\lfloor \log_{12}n\right\rfloor }<6\\ 0 & \text{otherwise} \end{cases}$$

Proof:

We will prove this by induction. First, as base cases, calculate the Grundy values for $n$ from $1$ through $24$ by hand or computer (to get $1, 2, 2, 3, 3, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2$). Then we may assume $n\ge 25$, so that the five moves "divide by $2$","divide by $3$",... all yield different results.

Now, assume that the claim holds for all lower $n$. We just need to verify the four cases.

Case 1

If $n$ begins with $1$ in base-12, then $n$ is in the range $[12^k,2*12^k)$. So the five moves are to numbers in the following ranges:

• $[6*12^{k-1},12^{k})$, so Grundy value $0$
• $[4*12^{k-1},8*12^{k-1})$, so Grundy value $3$ or $0$
• $[3*12^{k-1},6*12^{k-1})$, so Grundy value $2$ or $3$
• $[2.4*12^{k-1},4.8*12^{k-1})$, so Grundy value $2$ or $3$
• $[2*12^{k-1},4*12^{k-1})$, so Grundy value $2$

By the mex rule for the Grundy values, since there is a move to a position of value $0$ and not a move to a position of value $1$, the Grundy value for $n$ is indeed $1$.

Case 2

If $n$ begins with $2$ or $3$ in base-12, then $n$ is in the range $[2*12^k,4*12^k)$. So the five moves are to numbers in the following ranges:

• $[12^{k},2*12^{k})$, so Grundy value $1$
• $[8*12^{k-1},1.33\ldots*12^{k})$, so Grundy value $0$ or $1$
• $[6*12^{k-1},12^{k})$, so Grundy value $0$
• $[4.8*12^{k-1},9.6*12^{k-1})$, so Grundy value $3$ or $0$
• $[4*12^{k-1},8*12^{k-1})$, so Grundy value $3$ or $0$

Since there are moves to positions of value $0$ and $1$ and no move to a position of value $2$, the Grundy value for $n$ is indeed $2$.

Case 3

If $n$ begins with $4$ or $5$, then $n\in[4*12^k,6*12^k)$. So the moves are to:

• $[2*12^{k},3*12^{k})$, so $2$
• $[1.33\ldots*12^k,2*12^{k})$, so $1$
• $[12^k,1.5*12^k)$, so $1$
• $[9.6*12^{k-1},1.2*12^k)$, so $0$ or $1$
• $[8*12^{k-1},12^k)$, so $0$

Since there are moves to $0,1,2$ but not $3$, the value of $n$ is $3$.

Case 0

If $n$ begins with $6$ or more, then $n\in[6*12^k,12^{k+1})$:

• $[3*12^{k},6*12^k)$, so $2$ or $3$
• $[2*12^{k},4*12^k)$, so $2$
• $[1.5*12^k,3*12^k)$, so $1$ or $2$
• $[1.2*12^k,2.4*12^k)$, so $1$ or $2$
• $[12^k,6*12^k)$, so $1$ or $2$ or $3$

Since there are no winning moves to $0$, this is a losing position, and the value of $n$ is $0$.

Winner for $N\ge1$

By the strategy for Nim, we can use bitwise XOR (aka "adding in base 2 without carrying") to quickly find out the Grundy value for $N>1$ from the Grundy values of the individual numbers. A Grundy value of $0$ corresponds to a loss for the first player (so a win for Bob), and a positive result corresponds to a win for the first player, Alice.

Example and Winning Strategy

To show how this works in practice (and how the above proof yields the strategy), let's walk through the following example: Suppose $N=3$ and the numbers are $(200,400,800)$. Then in base-12, the numbers would be $142_{12},294_{12},568_{12}$, with leading digits $1,2,5$, corresponding to Grundy values $1,2,3$. To calculate the bitwise XOR, we convert to binary ($01_2,10_2,11_2$) and add without carrying, to get $00_2=0$. Since this is $0$, this must be a win for Bob, that means that Bob has a winning response to all $15$ of Alice's moves.

In ever case, Alice's move will change one of the three values $1,2,3$, and the new bitwise XOR will be nonzero. Bob must move to make the bitwise XOR $0$ again. For these small values, Bob can always do this by making the new three values $0,x,x$ in some order, either by reducing a value to $0$, or matching Grundy values if Alice changes one to $0$. We can find Bob's move not by trial and error, but by looking up the needed move in one of the subcases of the proof above.

1. If Alice divides $200$ by $2$, then the new Grundy value of $100$ is $0$. An easy response is to move the $800$ to $400$ (a number of Grundy value $2$). If Alice moves in $100$, Bob would have a local response (in that same number), and otherwise Bob can mirror moves in the two copies of $400$.
2. If Alice divides $200$ by $3$ to yield $66$, then the new Grundy value is $3$ and Bob can counter by dividing $400$ by $4$ to yield $100$ which has value $0$.
3. If Alice divides $200$ by $4$ to yield $50$, then the new Grundy value is still $3$ and Bob can turn $400$ into $100$.
4. If Alice divides $200$ by $5$ to yield $40$, then the new Grundy value is $2$, and Bob can respond by dividing $800$ by $6$ to yield $133$, which has Grundy value $0$.
5. If Alice divides $200$ by $6$ to yield $33$, then the new Grundy value is still $2$, and Bob still turn $800$ into $133$.
6. If Alice turns $400$ into $200$, then Bob can respond by dividing $800$ by $6$ to yield $133$, which has Grundy value $0$.
7. If Alice turns $400$ into $133$, then Bob can respond by turning $800$ into $200$.
8. If Alice turns $400$ into $100$, then Bob can still respond by turning $800$ into $200$.
9. If Alice turns $400$ into $80$, then the new Grundy value is $0$ and Bob can still respond by turning $800$ into $200$.
10. If Alice turns $400$ into $66$, then Bob can respond by turning $200$ into $100$.
11. $800\to400$? $200\to100$.
12. $800\to266$? $266$ has Grundy value $1$ so Bob can do $400\to100$.
13. $800\to200$? $400\to100$.
14. $800\to160$? $160$ has Grundy value $1$ so Bob can do $400\to100$.
15. $800\to133$? $400\to200$.