# Alice and Bob make all numbers to zero game

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.
• May I ask what your question is? Thanks. – awllower May 28 '16 at 12:32
• @awllower Who will win the game , if both play optimally ? Answer will be simply "Alice" or "Bob" – mat7 May 28 '16 at 12:36
• Ok, thanks for the explanation. :) Also, I suggest you can emphasise the question by prepending > in the beginning of that line. – awllower May 28 '16 at 12:37
• The same question was posed on the same day: math.stackexchange.com/questions/1803778. Please enlighten us as to the source of the problem, and please take note of our contest problem policy. – joriki May 30 '16 at 0:50
• seems to be this contest: codechef.com/SNCKQL16/problems/FDIVGAME ... but it closed on 31st May, so we're now good. – Joffan Jun 7 '16 at 18:36

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