One of my friends [user:VS-Codes,2023-10-01] recently introduced me to an Alice-Bob game problem (Newton School CodeRush September '23 — Problem C) which goes as follows —↵
↵
<spoiler summary="The Problem">↵
Alice and Bob are playing a game. They start with $n$ piles of $1$ stone each. Alice always makes the first move. At any turn, a player can choose any *two* non-empty piles and merge them into one large pile, _provided that the total number of stones in the new composite pile does not exceed $m$_. If at any point, a player is unable to make a move, he/she loses the game and the opponent is declared the winner. Find out who wins the game if both Alice and Bob play optimally.↵
↵
The game continues until a player can no longer make a move. When a player cannot make a move, they lose. Both Alice and Bob are very smart and will always choose the most beneficial strategy to win the game.↵
↵
Now, Alice wants to know, given n stone piles and the maximum allowed size of a pile m, who can win this game?↵
↵
For example, let $n = 6$ and $m = 2$. The game may proceed as follows:↵
↵
- Initially there are $6$ piles of $1$ stone each $[1, 1, 1, 1, 1, 1]$.↵
- Alice merges the $3^{rd}$ and $4^{th}$ piles to get $[1, 1, 2, 0, 1, 1]$.↵
- Bob merges the $1^{st}$ and $5^{th}$ piles to get $[2, 1, 2, 0, 0, 1]$.↵
- Alice merges the $6^{th}$ and $2^{nd}$ piles to get $[2, 0, 2, 0, 0, 2]$↵
- Bob cannot make any other move without making the size of the pile exceed $m = 2$, so Alice wins.↵
↵
It can be proved that Alice always has a winning strategy in the above case.↵
↵
##### Test Cases↵
$n = 6, m = 2 \implies Alice$ <br />↵
$n = 6, m = 3 \implies Bob$ <br />↵
$n = 9, m = 10 \implies Bob$ <br />↵
$n = 5, m = 3 \implies Alice$ <br />↵
</spoiler>↵
↵
The solution to this is a pretty straightforward result which I arrived at after making a few lucky guesses as to how the game would proceed.↵
↵
<spoiler summary="The Solution">↵
"If $(n - \lceil \frac{n}{m} \rceil)$ is an **odd** integer, then Alice wins. Otherwise Bob wins."↵
↵
Here $\lceil . \rceil$ is the [**ceiling**](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions) function.↵
↵
For the given test cases, <br />↵
$(6 - \lceil \frac{6}{2} \rceil) = 6 - 3 = 3, odd \implies Alice$ <br />↵
$(6 - \lceil \frac{6}{3} \rceil) = 6 - 2 = 4, even \implies Bob$ <br />↵
$(9 - \lceil \frac{9}{10} \rceil) = 9 - 1 = 8, even \implies Bob$ <br />↵
$(5 - \lceil \frac{5}{3} \rceil) = 5 - 2 = 3, odd \implies Alice$ <br />↵
</spoiler>↵
↵
However, the real challenge was to prove that this solution works. After many trials and revisions, I came up with a proof that looked reasonably complete. Would love to hear the community's suggestions on it, and if I could have made it shorter somehow (I tried my best).↵
↵
<spoiler summary="Proof">↵
For a given $n$ and $m$ as defined in the problem statement, we start from the game state $\lbrace \underbrace{1, 1, ...}_{n \rm\ times} \rbrace^A$, where every integer in the multi-set represents the size of a non-empty pile of stones, and the superscript $A$ indicates that it is Alice's turn to move.↵
↵
We call a certain game state the **sink** state, defined as —↵
$$↵
\lbrace \underbrace{m, m, ...}_{(\lceil \frac{n}{m} \rceil - 1) \rm\ times}, 1 + (n - 1) \mod m\rbrace^{A \ or \ B}↵
$$↵
↵
In other words, the sink state is a state of the game in which **at most one** of the non-empty piles of stones has $\leq m$ stones, and the rest have exactly $m$ stones. It is clear that **no further moves** can be made from the sink state.↵
↵
For example, let $n = 17, m = 5$. The sink state for this case would be $\lbrace 5, 5, 5, 2 \rbrace^B$.↵
↵
Notice that the sink state is **not** the only possible terminal state of the game. For example, $\lbrace 5, 3, 3, 3, 3\rbrace^A$ is a terminal game state, since no further move can be made from this state.↵
↵
> _The sink state is a terminal state, but it is not the only one._↵
↵
We can see that the total number of non-empty piles in the sink state is $\lceil \frac{n}{m} \rceil$. Now, since every valid move reduces the total number of non-empty piles by **exactly one**, the total number of moves required to go from the start state to the sink state is $moves = n - \lceil \frac{n}{m} \rceil$.↵
↵
Clearly, the winner of any game that ends in the sink state depends on the **parity** of $moves$. If $moves$ is odd, Alice wins. Otherwise, Bob wins.↵
↵
We define the **attacker** to be the player (Alice or Bob) who wins the game if it ends in the sink state. The other player is the **defender**.↵
↵
#### Claim:↵
↵
_It is **always** possible for the attacker to play a sequence of moves such that the game ends in the sink state, irrespective of the moves played by the defender._↵
↵
#### Proof:↵
↵
The game starts at $S_0 = \lbrace \underbrace{1, 1, ...}_{n \rm\ times} \rbrace^A$. If $n = 1$ or $m = 1$, then this is a trivial sink state.↵
↵
Otherwise if $n, m > 1$, Alice only has one move, after which we go to $S_1 = \lbrace 2, \underbrace{1, 1, ...}_{(n - 2) \rm\ times} \rbrace^B$. If $n = 2$, then we end up at another trivial sink state.↵
↵
Otherwise if $n > 2$, Bob can choose between two different moves:↵
↵
- If $m \geq 3$, merge a $1$ with $2$ to go to $S_{21} = \lbrace 3, \underbrace{1, 1, ...}_{(n - 3) \rm\ times} \rbrace^A$↵
↵
- If $n \geq 4$, merge two $1$'s to go to $S_{22} = \lbrace 2, 2, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace^A$↵
↵
If $n = 3$, then Bob is compelled to play the first move, which leads us to a sink state, too.↵
↵
If $m = 2$, then the players are forced to play the same move of merging two $1$'s, which will end in the sink state after a finite number of moves.↵
↵
So henceforth, we discuss the case where $n \geq 4$ and $m \geq 3$.↵
↵
We now make the following observation — ↵
>A pile that has exactly $m$ stones is **unmodifiable**, irrespective of the number of stones in other piles. Hence, a state $\lbrace m, x_1, x_2, x_3 ...\rbrace^P$ is equivalent to the state $\lbrace x_1, x_2, x_3 ...\rbrace^P$.↵
↵
#### Alice's attack strategy↵
↵
On the third move, Bob can move to one of two states, as shown earlier:↵
↵
- If Bob moves to $\lbrace 3, \underbrace{1, 1, ...}_{(n - 3) \rm\ times} \rbrace^A$, Alice merges $3$ and $1$.↵
↵
- If Bob moves to $\lbrace 2, 2, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace^A$, Alice merges $2$ and $2$.↵
↵
Notice that both these moves bring us to the same game state $\lbrace 4, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace^B$.↵
↵
Comparing this to the game state $S_1$, we find that effectively, the largest pile of stones increased by two stones, and the total number of piles decreased by two.↵
↵
Using the same idea Alice can keep moving along the following sequence of game states —↵
↵
$$↵
\lbrace 2, \underbrace{1, 1, ...}_{(n - 2) \rm\ times} \rbrace^B \longrightarrow↵
\lbrace 4, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace^B ↵
\longrightarrow↵
\lbrace 6, \underbrace{1, 1, ...}_{(n - 6) \rm\ times} \rbrace^B↵
\longrightarrow ...↵
\lbrace 2k, \underbrace{1, 1, ...}_{(n - 2k) \rm\ times} \rbrace^B↵
$$↵
↵
Alice continues this until either —↵
↵
$n - 2k = 0$, in which case we have a trivial sink state.↵
↵
$2k = m$ or $2k + 1 = m$.↵
↵
- When $2k = m$, we have the state $\lbrace m, \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^B \equiv \lbrace \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^B$. Alice proceeds further using **Bob's attack strategy**, since this is like playing a new game with $(n - m)$ stones where Bob plays the first move instead of Alice.↵
↵
- When $2k + 1 = m$↵
↵
- If Bob merges $2k$ with $1$, we go to the state $\lbrace m, \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^A \equiv \lbrace \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^A$. Alice proceeds further using the same attack strategy since this is like playing a new game with $(n - m)$ stones.↵
↵
- If Bob merges two $1$'s to go to the state $\lbrace m - 1, 2, \underbrace{1, 1, ...}_{(n - m - 1) \rm\ times} \rbrace^A$, Alice merges $2k$ with $1$ to get to $\lbrace m, 2, \underbrace{1, 1, ...}_{(n - m - 2) \rm\ times} \rbrace^B \equiv \lbrace 2, \underbrace{1, 1, ...}_{(n - m - 2) \rm\ times} \rbrace^B$. Here too, Alice proceeds using the same attack strategy, since this is equivalent to the state $S_1$ in a game with $(n - m)$ stones. Note that in the state $\lbrace m - 1, 2, \underbrace{1, 1, ...}_{(n - m - 1) \rm\ times} \rbrace^A$, $(n - m - 1)$ cannot be zero.↵
↵
<spoiler summary="proof">↵
Since this is _Alice's turn_, the total number of moves made till now (equal to the difference in number of non-empty piles) must be even. Thus, $n - (n - m - 1 + 2) = m - 1$ is **even**. Now, let us assume $n - m - 1 = 0 \implies n = m + 1$. Since _Alice is the attacker_, $moves = n - \lceil \frac{n}{m} \rceil$ must be odd. Thus $n - \lceil \frac{m + 1}{m} \rceil = n - 2 = m - 1$ must be **odd**, which is a contradiction.↵
</spoiler>↵
↵
#### Bob's attack strategy↵
↵
On the third move, from state $S_1$, Bob moves to $S_{21} = \lbrace 3, \underbrace{1, 1, ...}_{(n - 3) \rm\ times} \rbrace^A$ by merging $2$ and $1$.↵
↵
Next, Alice can move to one of two states:↵
↵
- If Alice merges $3$ and $1$ to get to $\lbrace 4, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace^B$, Bob merges $4$ and $1$.↵
↵
- If Alice merges two $1$'s to $\lbrace 3, 2, \underbrace{1, 1, ...}_{(n - 5) \rm\ times} \rbrace^B$, Bob merges $3$ and $2$.↵
↵
Notice that both these moves bring us to the same game state $\lbrace 5, \underbrace{1, 1, ...}_{(n - 5) \rm\ times} \rbrace^A$.↵
↵
Comparing this to the game state $S_{21}$, we find that once again, the largest pile of stones increased by two stones, and the total number of piles decreased by two.↵
↵
Using the same idea Bob can keep moving along the following sequence of game states —↵
↵
$$↵
\lbrace 3, \underbrace{1, 1, ...}_{(n - 3) \rm\ times} \rbrace^A \longrightarrow↵
\lbrace 5, \underbrace{1, 1, ...}_{(n - 5) \rm\ times} \rbrace^A ↵
\longrightarrow↵
\lbrace 7, \underbrace{1, 1, ...}_{(n - 7) \rm\ times} \rbrace^A↵
\longrightarrow ...↵
\lbrace 2k + 1, \underbrace{1, 1, ...}_{(n - 2k - 1) \rm\ times} \rbrace^A↵
$$↵
↵
Bob continues this until either —↵
↵
$n - 2k - 1 = 0$, in which case we have a trivial sink state.↵
↵
$2k + 1 = m$ or $2k + 2 = m$.↵
↵
- When $2k + 1= m$, we have the state $\lbrace m, \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^A \equiv \lbrace \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^A$. Bob proceeds further using the same attack strategy, since this is like playing a new game with $(n - m)$ stones.↵
↵
- When $2k + 2 = m$↵
↵
- If Alice merges $2k + 1$ with $1$, we go to the state $\lbrace m, \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^B \equiv \lbrace \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^B$. Bob proceeds further using **Alice's attack strategy** since this is like playing a new game with $(n - m)$ stones where Bob plays the first move instead of Alice.↵
↵
- If Alice merges two $1$'s to go to the state $\lbrace m - 1, 2, \underbrace{1, 1, ...}_{(n - m - 1) \rm\ times} \rbrace^B$, Bob merges $2k + 1$ with $1$ to get to $\lbrace m, 2, \underbrace{1, 1, ...}_{(n - m - 2) \rm\ times} \rbrace^A \equiv \lbrace 2, \underbrace{1, 1, ...}_{(n - m - 2) \rm\ times} \rbrace^A$. Here too, Bob proceeds using **Alice's attack strategy**, since this is equivalent to the state $S_1$ in a game with $(n - m)$ stones where Bob plays the first move instead of Alice. Notice that again, $(n - m - 1)$ cannot be zero, using a similar strategy for proof as in the case for Alice.↵
↵
This completes the proof.↵
</spoiler>↵
↵
<spoiler summary="Less mathy (proof?)">↵
First of all, let's begin by understanding what would happen if we could _somehow_ make every pile of stones as large as possible. This would mean that at the end of the game, we would have some piles with $m$ stones, and one pile with $n \mod m$ stones. Clearly, the total number of non-empty piles would be $\lceil \frac{n}{m} \rceil$.↵
↵
How many moves were made to get there? Well, notice that every move decreases the number of piles of stones by **exactly one**, since two piles are merged to form a bigger pile. We had $n$ piles initially. Thus the total number of moves that were made must be $moves = (n - \lceil \frac{n}{m} \rceil)$.↵
↵
Since Alice starts the game and both of them play alternately, if $moves$ is odd, then Bob will be unable to make a move after Alice makes the last move, and will lose the game. So Alice wins. Similarly, if $moves$ is even, Bob wins.↵
↵
Now, suppose $moves$ is odd. So Alice, understandably, wants to make each pile as big as possible, in order to win. Bob, however, does **not** want that. Can he do anything about it? No. Here's why.↵
↵
- We start off with $n$ piles of $1$ stone each: $\lbrace \underbrace{1, 1, ...}_{n \rm\ times} \rbrace$↵
↵
- Alice merges two piles of $1$ stone: $\lbrace 2, \underbrace{1, 1, ...}_{(n - 2) \rm\ times} \rbrace$↵
↵
- Bob does not want to make the biggest pile bigger, so he merges two more $1$'s to make a $2$: $\lbrace 2, 2, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace$↵
↵
- Alice smugly merges the $2$ with the biggest pile, and laughs in Bob's face: $\lbrace 4, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace$↵
↵
Alice can keep doing this, until either — ↵
↵
- The largest pile has $m$ stones, in which case, she just moves on to another pile and starts making it bigger.↵
↵
- The largest pile has $m - 1$ stones, in which case she cannot merge $2$ with it. In this case, the situation looks like $\lbrace m - 1, 2, \underbrace{1, 1, ...}_{(n - m - 1) \rm\ times} \rbrace$. However, here Alice herself merges $1$ with the biggest pile to complete it. Irrespective of what Bob plays next, Alice can again continue making the next pile bigger.↵
↵
Hang on, how are we sure that in the last case, Alice can always merge a $1$ with the pile having $m - 1$ stones? What if, after Bob merges two $1$'s, there are no more $1$'s left! The proof of why this cannot happen is provided in a small spoiler window in the longer proof, go check it out.↵
↵
Similarly, if $moves$ is even, then Bob is the one laughing, since now he can keep making the biggest pile bigger as that leads to his victory, and there is nothing Alice can do about it.↵
↵
Thus, the parity of $moves$ determines the winner.↵
</spoiler>↵
↵
↵
<spoiler summary="The Problem">↵
Alice and Bob are playing a game. They start with $n$ piles of $1$ stone each. Alice always makes the first move. At any turn, a player can choose any *two* non-empty piles and merge them into one large pile, _provided that the total number of stones in the new composite pile does not exceed $m$_. If at any point, a player is unable to make a move, he/she loses the game and the opponent is declared the winner. Find out who wins the game if both Alice and Bob play optimally.↵
↵
The game continues until a player can no longer make a move. When a player cannot make a move, they lose. Both Alice and Bob are very smart and will always choose the most beneficial strategy to win the game.↵
↵
Now, Alice wants to know, given n stone piles and the maximum allowed size of a pile m, who can win this game?↵
↵
For example, let $n = 6$ and $m = 2$. The game may proceed as follows:↵
↵
- Initially there are $6$ piles of $1$ stone each $[1, 1, 1, 1, 1, 1]$.↵
- Alice merges the $3^{rd}$ and $4^{th}$ piles to get $[1, 1, 2, 0, 1, 1]$.↵
- Bob merges the $1^{st}$ and $5^{th}$ piles to get $[2, 1, 2, 0, 0, 1]$.↵
- Alice merges the $6^{th}$ and $2^{nd}$ piles to get $[2, 0, 2, 0, 0, 2]$↵
- Bob cannot make any other move without making the size of the pile exceed $m = 2$, so Alice wins.↵
↵
It can be proved that Alice always has a winning strategy in the above case.↵
↵
##### Test Cases↵
$n = 6, m = 2 \implies Alice$ <br />↵
$n = 6, m = 3 \implies Bob$ <br />↵
$n = 9, m = 10 \implies Bob$ <br />↵
$n = 5, m = 3 \implies Alice$ <br />↵
</spoiler>↵
↵
The solution to this is a pretty straightforward result which I arrived at after making a few lucky guesses as to how the game would proceed.↵
↵
<spoiler summary="The Solution">↵
"If $(n - \lceil \frac{n}{m} \rceil)$ is an **odd** integer, then Alice wins. Otherwise Bob wins."↵
↵
Here $\lceil . \rceil$ is the [**ceiling**](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions) function.↵
↵
For the given test cases, <br />↵
$(6 - \lceil \frac{6}{2} \rceil) = 6 - 3 = 3, odd \implies Alice$ <br />↵
$(6 - \lceil \frac{6}{3} \rceil) = 6 - 2 = 4, even \implies Bob$ <br />↵
$(9 - \lceil \frac{9}{10} \rceil) = 9 - 1 = 8, even \implies Bob$ <br />↵
$(5 - \lceil \frac{5}{3} \rceil) = 5 - 2 = 3, odd \implies Alice$ <br />↵
</spoiler>↵
↵
However, the real challenge was to prove that this solution works. After many trials and revisions, I came up with a proof that looked reasonably complete. Would love to hear the community's suggestions on it, and if I could have made it shorter somehow (I tried my best).↵
↵
<spoiler summary="Proof">↵
For a given $n$ and $m$ as defined in the problem statement, we start from the game state $\lbrace \underbrace{1, 1, ...}_{n \rm\ times} \rbrace^A$, where every integer in the multi-set represents the size of a non-empty pile of stones, and the superscript $A$ indicates that it is Alice's turn to move.↵
↵
We call a certain game state the **sink** state, defined as —↵
$$↵
\lbrace \underbrace{m, m, ...}_{(\lceil \frac{n}{m} \rceil - 1) \rm\ times}, 1 + (n - 1) \mod m\rbrace^{A \ or \ B}↵
$$↵
↵
In other words, the sink state is a state of the game in which **at most one** of the non-empty piles of stones has $\leq m$ stones, and the rest have exactly $m$ stones. It is clear that **no further moves** can be made from the sink state.↵
↵
For example, let $n = 17, m = 5$. The sink state for this case would be $\lbrace 5, 5, 5, 2 \rbrace^B$.↵
↵
Notice that the sink state is **not** the only possible terminal state of the game. For example, $\lbrace 5, 3, 3, 3, 3\rbrace^A$ is a terminal game state, since no further move can be made from this state.↵
↵
> _The sink state is a terminal state, but it is not the only one._↵
↵
We can see that the total number of non-empty piles in the sink state is $\lceil \frac{n}{m} \rceil$. Now, since every valid move reduces the total number of non-empty piles by **exactly one**, the total number of moves required to go from the start state to the sink state is $moves = n - \lceil \frac{n}{m} \rceil$.↵
↵
Clearly, the winner of any game that ends in the sink state depends on the **parity** of $moves$. If $moves$ is odd, Alice wins. Otherwise, Bob wins.↵
↵
We define the **attacker** to be the player (Alice or Bob) who wins the game if it ends in the sink state. The other player is the **defender**.↵
↵
#### Claim:↵
↵
_It is **always** possible for the attacker to play a sequence of moves such that the game ends in the sink state, irrespective of the moves played by the defender._↵
↵
#### Proof:↵
↵
The game starts at $S_0 = \lbrace \underbrace{1, 1, ...}_{n \rm\ times} \rbrace^A$. If $n = 1$ or $m = 1$, then this is a trivial sink state.↵
↵
Otherwise if $n, m > 1$, Alice only has one move, after which we go to $S_1 = \lbrace 2, \underbrace{1, 1, ...}_{(n - 2) \rm\ times} \rbrace^B$. If $n = 2$, then we end up at another trivial sink state.↵
↵
Otherwise if $n > 2$, Bob can choose between two different moves:↵
↵
- If $m \geq 3$, merge a $1$ with $2$ to go to $S_{21} = \lbrace 3, \underbrace{1, 1, ...}_{(n - 3) \rm\ times} \rbrace^A$↵
↵
- If $n \geq 4$, merge two $1$'s to go to $S_{22} = \lbrace 2, 2, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace^A$↵
↵
If $n = 3$, then Bob is compelled to play the first move, which leads us to a sink state, too.↵
↵
If $m = 2$, then the players are forced to play the same move of merging two $1$'s, which will end in the sink state after a finite number of moves.↵
↵
So henceforth, we discuss the case where $n \geq 4$ and $m \geq 3$.↵
↵
We now make the following observation — ↵
>A pile that has exactly $m$ stones is **unmodifiable**, irrespective of the number of stones in other piles. Hence, a state $\lbrace m, x_1, x_2, x_3 ...\rbrace^P$ is equivalent to the state $\lbrace x_1, x_2, x_3 ...\rbrace^P$.↵
↵
#### Alice's attack strategy↵
↵
On the third move, Bob can move to one of two states, as shown earlier:↵
↵
- If Bob moves to $\lbrace 3, \underbrace{1, 1, ...}_{(n - 3) \rm\ times} \rbrace^A$, Alice merges $3$ and $1$.↵
↵
- If Bob moves to $\lbrace 2, 2, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace^A$, Alice merges $2$ and $2$.↵
↵
Notice that both these moves bring us to the same game state $\lbrace 4, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace^B$.↵
↵
Comparing this to the game state $S_1$, we find that effectively, the largest pile of stones increased by two stones, and the total number of piles decreased by two.↵
↵
Using the same idea Alice can keep moving along the following sequence of game states —↵
↵
$$↵
\lbrace 2, \underbrace{1, 1, ...}_{(n - 2) \rm\ times} \rbrace^B \longrightarrow↵
\lbrace 4, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace^B ↵
\longrightarrow↵
\lbrace 6, \underbrace{1, 1, ...}_{(n - 6) \rm\ times} \rbrace^B↵
\longrightarrow ...↵
\lbrace 2k, \underbrace{1, 1, ...}_{(n - 2k) \rm\ times} \rbrace^B↵
$$↵
↵
Alice continues this until either —↵
↵
$n - 2k = 0$, in which case we have a trivial sink state.↵
↵
$2k = m$ or $2k + 1 = m$.↵
↵
- When $2k = m$, we have the state $\lbrace m, \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^B \equiv \lbrace \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^B$. Alice proceeds further using **Bob's attack strategy**, since this is like playing a new game with $(n - m)$ stones where Bob plays the first move instead of Alice.↵
↵
- When $2k + 1 = m$↵
↵
- If Bob merges $2k$ with $1$, we go to the state $\lbrace m, \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^A \equiv \lbrace \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^A$. Alice proceeds further using the same attack strategy since this is like playing a new game with $(n - m)$ stones.↵
↵
- If Bob merges two $1$'s to go to the state $\lbrace m - 1, 2, \underbrace{1, 1, ...}_{(n - m - 1) \rm\ times} \rbrace^A$, Alice merges $2k$ with $1$ to get to $\lbrace m, 2, \underbrace{1, 1, ...}_{(n - m - 2) \rm\ times} \rbrace^B \equiv \lbrace 2, \underbrace{1, 1, ...}_{(n - m - 2) \rm\ times} \rbrace^B$. Here too, Alice proceeds using the same attack strategy, since this is equivalent to the state $S_1$ in a game with $(n - m)$ stones. Note that in the state $\lbrace m - 1, 2, \underbrace{1, 1, ...}_{(n - m - 1) \rm\ times} \rbrace^A$, $(n - m - 1)$ cannot be zero.↵
↵
<spoiler summary="proof">↵
Since this is _Alice's turn_, the total number of moves made till now (equal to the difference in number of non-empty piles) must be even. Thus, $n - (n - m - 1 + 2) = m - 1$ is **even**. Now, let us assume $n - m - 1 = 0 \implies n = m + 1$. Since _Alice is the attacker_, $moves = n - \lceil \frac{n}{m} \rceil$ must be odd. Thus $n - \lceil \frac{m + 1}{m} \rceil = n - 2 = m - 1$ must be **odd**, which is a contradiction.↵
</spoiler>↵
↵
#### Bob's attack strategy↵
↵
On the third move, from state $S_1$, Bob moves to $S_{21} = \lbrace 3, \underbrace{1, 1, ...}_{(n - 3) \rm\ times} \rbrace^A$ by merging $2$ and $1$.↵
↵
Next, Alice can move to one of two states:↵
↵
- If Alice merges $3$ and $1$ to get to $\lbrace 4, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace^B$, Bob merges $4$ and $1$.↵
↵
- If Alice merges two $1$'s to $\lbrace 3, 2, \underbrace{1, 1, ...}_{(n - 5) \rm\ times} \rbrace^B$, Bob merges $3$ and $2$.↵
↵
Notice that both these moves bring us to the same game state $\lbrace 5, \underbrace{1, 1, ...}_{(n - 5) \rm\ times} \rbrace^A$.↵
↵
Comparing this to the game state $S_{21}$, we find that once again, the largest pile of stones increased by two stones, and the total number of piles decreased by two.↵
↵
Using the same idea Bob can keep moving along the following sequence of game states —↵
↵
$$↵
\lbrace 3, \underbrace{1, 1, ...}_{(n - 3) \rm\ times} \rbrace^A \longrightarrow↵
\lbrace 5, \underbrace{1, 1, ...}_{(n - 5) \rm\ times} \rbrace^A ↵
\longrightarrow↵
\lbrace 7, \underbrace{1, 1, ...}_{(n - 7) \rm\ times} \rbrace^A↵
\longrightarrow ...↵
\lbrace 2k + 1, \underbrace{1, 1, ...}_{(n - 2k - 1) \rm\ times} \rbrace^A↵
$$↵
↵
Bob continues this until either —↵
↵
$n - 2k - 1 = 0$, in which case we have a trivial sink state.↵
↵
$2k + 1 = m$ or $2k + 2 = m$.↵
↵
- When $2k + 1= m$, we have the state $\lbrace m, \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^A \equiv \lbrace \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^A$. Bob proceeds further using the same attack strategy, since this is like playing a new game with $(n - m)$ stones.↵
↵
- When $2k + 2 = m$↵
↵
- If Alice merges $2k + 1$ with $1$, we go to the state $\lbrace m, \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^B \equiv \lbrace \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^B$. Bob proceeds further using **Alice's attack strategy** since this is like playing a new game with $(n - m)$ stones where Bob plays the first move instead of Alice.↵
↵
- If Alice merges two $1$'s to go to the state $\lbrace m - 1, 2, \underbrace{1, 1, ...}_{(n - m - 1) \rm\ times} \rbrace^B$, Bob merges $2k + 1$ with $1$ to get to $\lbrace m, 2, \underbrace{1, 1, ...}_{(n - m - 2) \rm\ times} \rbrace^A \equiv \lbrace 2, \underbrace{1, 1, ...}_{(n - m - 2) \rm\ times} \rbrace^A$. Here too, Bob proceeds using **Alice's attack strategy**, since this is equivalent to the state $S_1$ in a game with $(n - m)$ stones where Bob plays the first move instead of Alice. Notice that again, $(n - m - 1)$ cannot be zero, using a similar strategy for proof as in the case for Alice.↵
↵
This completes the proof.↵
</spoiler>↵
↵
<spoiler summary="Less mathy (proof?)">↵
First of all, let's begin by understanding what would happen if we could _somehow_ make every pile of stones as large as possible. This would mean that at the end of the game, we would have some piles with $m$ stones, and one pile with $n \mod m$ stones. Clearly, the total number of non-empty piles would be $\lceil \frac{n}{m} \rceil$.↵
↵
How many moves were made to get there? Well, notice that every move decreases the number of piles of stones by **exactly one**, since two piles are merged to form a bigger pile. We had $n$ piles initially. Thus the total number of moves that were made must be $moves = (n - \lceil \frac{n}{m} \rceil)$.↵
↵
Since Alice starts the game and both of them play alternately, if $moves$ is odd, then Bob will be unable to make a move after Alice makes the last move, and will lose the game. So Alice wins. Similarly, if $moves$ is even, Bob wins.↵
↵
Now, suppose $moves$ is odd. So Alice, understandably, wants to make each pile as big as possible, in order to win. Bob, however, does **not** want that. Can he do anything about it? No. Here's why.↵
↵
- We start off with $n$ piles of $1$ stone each: $\lbrace \underbrace{1, 1, ...}_{n \rm\ times} \rbrace$↵
↵
- Alice merges two piles of $1$ stone: $\lbrace 2, \underbrace{1, 1, ...}_{(n - 2) \rm\ times} \rbrace$↵
↵
- Bob does not want to make the biggest pile bigger, so he merges two more $1$'s to make a $2$: $\lbrace 2, 2, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace$↵
↵
- Alice smugly merges the $2$ with the biggest pile, and laughs in Bob's face: $\lbrace 4, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace$↵
↵
Alice can keep doing this, until either — ↵
↵
- The largest pile has $m$ stones, in which case, she just moves on to another pile and starts making it bigger.↵
↵
- The largest pile has $m - 1$ stones, in which case she cannot merge $2$ with it. In this case, the situation looks like $\lbrace m - 1, 2, \underbrace{1, 1, ...}_{(n - m - 1) \rm\ times} \rbrace$. However, here Alice herself merges $1$ with the biggest pile to complete it. Irrespective of what Bob plays next, Alice can again continue making the next pile bigger.↵
↵
Hang on, how are we sure that in the last case, Alice can always merge a $1$ with the pile having $m - 1$ stones? What if, after Bob merges two $1$'s, there are no more $1$'s left! The proof of why this cannot happen is provided in a small spoiler window in the longer proof, go check it out.↵
↵
Similarly, if $moves$ is even, then Bob is the one laughing, since now he can keep making the biggest pile bigger as that leads to his victory, and there is nothing Alice can do about it.↵
↵
Thus, the parity of $moves$ determines the winner.↵
</spoiler>↵
↵
