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.

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$$$
$$$n = 6, m = 3 \implies Bob$$$
$$$n = 9, m = 10 \implies Bob$$$
$$$n = 5, m = 3 \implies Alice$$$

"If $$$(n - \lceil \frac{n}{m} \rceil)$$$ is an odd integer, then Alice wins. Otherwise Bob wins."

Here $$$\lceil . \rceil$$$ is the ceiling function.

For the given test cases,
$$$(6 - \lceil \frac{6}{2} \rceil) = 6 - 3 = 3, odd \implies Alice$$$
$$$(6 - \lceil \frac{6}{3} \rceil) = 6 - 2 = 4, even \implies Bob$$$
$$$(9 - \lceil \frac{9}{10} \rceil) = 9 - 1 = 8, even \implies Bob$$$
$$$(5 - \lceil \frac{5}{3} \rceil) = 5 - 2 = 3, odd \implies Alice$$$

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 —

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 —

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 here $$$(n - m - 1)$$$ cannot be zero.

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 —

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.

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.