mathematics - Greedy Chocolate Eaters

Alicia and Bobby play a game with a rectangular chocolate bar, scored into an $m$ by $n$ grid of squares.

The children alternate turns, with Alicia going first. On a child's turn, they must break the chocolate bar into two smaller rectangles along one of the grid lines, then eat the larger of two pieces. If they make two equal pieces, they arbitrarily eat one of them. The game ends once the chocolate bar is a single $1\times 1$ square, in which case the person who just ate wins.

Below is an example of a game fully played out, starting with a $5\times 6$ bar. The letters indicate which player took each bite. Since Bobby took the last bite, he won this game.

For which values of $m$ and $n$ can Alicia force a win?

Answer

A crucial observation to this problem is as follows:

The game, played on an $n\times m$ bar is equivalent to the nim-sum of the game on a $n\times 1$ bar by the game on a $1\times m$ bar.

In layman's terms, the "nim-sum" of two games is just what happens when, at each turn, the player has the option to make a move in either (but not both) of the games and where a player loses when they cannot make any move in either game (which happens only for a $1\times 1$ bar). So, the above just means that, when we decreasing the width of the bar, we're really making an equivalent move in the $n\times 1$ bar and when decreasing the height of the bar, we're making an equivalent move in the $m\times 1$ bar. An, of course, the loss at $1\times 1$ is because both $n\times 1$ and $1\times m$ are equal to $1\times 1$, which is a loss. In short, the two dimensions are independent of each other and interact with the winning condition in a simple way.

Next, we notice that the position $n\times 1$ is equivalent to a game of nim - in particular, choosing $m$ to be such that $2^{m} \leq n < 2^{m+1}$ (that is $m=\lfloor \log_2(n)\rfloor$) we can show that a block of $n\times 1$ chocolates is the same as a game of nim with $m$ stones. This is really easy to prove - we simply can show that any move in the chocolates corresponds to a legal nim move and vice versa. For instance, any legal move of chocolates divides the number $n$ of chocolates at least by $2$, equivalent to decreasing $m$ by at least one. However, for any $m'

Then, this is easy: The game as a whole is equivalent to two-pile nim, with one pile of $\lfloor \log_2(n)\rfloor$ and one pile of $\lfloor\log_2(m)\rfloor$ (being the nim-sum of those two piles). Noticing that, in two pile nim, the "mirroring" strategy is optimal (where if you receive piles of two different heights, you shrink the larger one to match the smaller one), we conclude that Alicia wins whenever $\lfloor \log_2(n)\rfloor \neq \lfloor\log_2(m)\rfloor$.

---

Some More Words For Mathematicians Less Interested in the Particular Solution and More Interested in General Technique:

One may notice that, as this is an impartial game, we may always apply the Sprague-Grundy theorem to assign a nimber to each game - that is, show it to be "equivalent" $n$ pile nim for some $n$ (though this is a weaker notion of equivalence than proved above). The nimber of the nim-sum of two games happens to be the exclusive or (the binary operation) of their respective nimbers (where a $0$ is a loss, happening only when the nimbers are equal) - so we can easily generalize the above solution to handle $3$ dimensional chocolate bars (or $4$ dimensional and so on, but those are harder to eat).

Moreover, we may regard the nimber of a game as the mex (minimum excluded value) of the nimbers of the positions to which it can move - this is a powerful technique, letting us prove generalizations like:

Suppose we have a game where we start with $n$ stones and may move to any position with $f(n)$ or less stones, where $f(n)$ is strictly increasing and $f(n)0$. Having $0$ stones is a loss. The nimber of this game is the smallest $k$ such that $f^k(n)=0$.

This may be proven by induction, or otherwise by noting that as the game is "transitive" in some sense (if a position can be obtained by two moves, it can be obtained by one), we are merely counting the longest possible sequence of moves (since the mex ends up incrementing once per step in the path). We can also prove it as we did before - i.e. a game of $k$ pile nim has the moves in correspondence with the given game.