# 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?

• There's a similar puzzle out and about I recall seeing where someone proved the game always ends with one person winning. Can't tell at first glance if this is the same or the opposite. – Kingrames Jul 22 '15 at 21:56
• Shouldn't this question have a math tag? – CodeNewbie Jul 23 '15 at 16:28
• Keep n*m a multiple of a common factor between both the original n and m (if there are any), it's a tactic I'd use if applicable. – warspyking Jul 23 '15 at 19:42
• Player 1 breaks off all but 1 row. Player 2 breaks off all but one piece and wins. But player 1 got more chocolate, so who's the real winner? – Chris Cudmore Jan 22 at 21:32

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'<m$ corresponding to a move in nim, we can legally move to a $2^{m'}\times 1$ bar.

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)<n$ for $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.

Reducing to a $$1 \times 1$$ square wins.

If you reduce to an $$n \times n$$ square, your opponent must reduce it to an $$n \times i$$ rectangle, with $$i <= n/2$$. You can then reduce to an $$i \times i$$ square.

Thus, if you reduce the game to a square, and do so on every turn, you are guaranteed to win. Thus, Alice wins anytime $$m \neq n$$.

• It is not always possible to reduce to a square, because one must always eat the larger of the two parts. For example, if you try to cut 2x3 to a square, you must eat the 2x2 square and leave the 2x1 piece. This is a losing position for the first player, even though it is not square. – Jaap Scherphuis Jan 23 at 12:24
• Ah, missed that detail. Editing answer to fix. – user3294068 Jan 23 at 15:42
• You are still claiming that Alice always wins when $m\ne n$. This is not the case, as the $2\times 3$ example shows. Sure, she wins if she can create a square, but in some cases she cannot make a square and will actually lose ($2\times 3$). In other cases she cannot make a square but can still win using some other move (e.g. for $7\times 8$ she could leave $7\times 4$ to win). – Jaap Scherphuis Jan 23 at 16:13
• Yep, you're right. My answer is wrong. – user3294068 Jan 23 at 18:40

Without going deep into the maths,

a 2 x 2 piece will always win with Alice going first?

• You say Alice goes first, then your diagram shows Bob? – CodeNewbie Jul 23 '15 at 3:09
• There I edited it, thx @CodeNewbie – Alex Jul 23 '15 at 15:50
• while that fixes the error in your diagram, it makes your answer completely wrong. Because as per the question, Alicia is expected to force a win, but your solution describes a win for Bobby. – CodeNewbie Jul 23 '15 at 16:24
• ah I am confused; whoever eat the last bit wins? in my answer, Alice will eat half from the 4 squares, leave behind 2 squares for bob. Bob will eat half of it, result in alice eating the last square? – Alex Jul 23 '15 at 17:02
• The game ends once the chocolate bar is a single 1×1 square, in which case the person who just ate wins. In other words, whoever eats and leaves behind a 1x1 square, wins. – CodeNewbie Jul 23 '15 at 17:14