Non-Greedy Chocolate Eaters

Question

A variant of Greedy Chocolate Eaters (created by my significant other, who doesn't like chocolate all that much)

---

Alice and Bob are playing a game with a rectangular bar of chocolate scored into $m \times n$ squares along gridlines. They alternate turns, with Alice going first. On a turn, the player breaks the chocolate bar along a grid line, eating the strictly smaller piece. Players may not break the chocolate bar in half. The person who reduces the chocolate bar to a $2 \times 2$ square wins, since it is impossible to reduce it further. Both players know and use the optimal strategy.

For instance, with possibly non-optimal play, Alice could take a $4 \times 6$ bar and reduce it to $3 \times 6$. Bob could reduce that to $3 \times 4$. Alice could reduce to $3 \times 3$. Bob could then reduce to $2 \times 3$, and Alice would win by reducing to $2 \times 2$.

Given $m$ and $n$, find a simple test Alice can apply to determine if she will lose. Then explain the optimal strategy.

Answer 1

Alice will lose if

one of the numbers $m$ and $n$ is a power of $2$ times the other. She can win otherwise.

Call a piece of chocolate balanced if one of the dimensions is a power of $2$ times the other. First, we see that any move made to a blanced piece will result in an unbalanced piece, because the dimension that is reduced must be reduced to more than half its original size. Next, we see that if the piece is unbalanced, then there is a move resulting in a balanced piece. If the unbalanced piece has size $m\times n$ with $m>n$, then we can choose the largest integer $k$ such that $2^k n \leq m$, and break the chocolate into pieces of size $(2^k n)\times n$ and $(m-2^k n)\times n$. Now $m-2^k n< 2^k n$ because we chose $k$ to be maximal, so the smaller piece of size $(m-2^k n)\times n$ is eaten, and the remaining piece of size $(2^k n)\times n$ is balanced.

So, the winning strategy: given an unbalanced piece of chocolate is to make the piece balanced.

Answer 2

Define a function $f(n)$ on the positive integers recursively by $$ f(n)=\begin{cases} f(n/2) & \text{when } n \text{ is even}\\ \frac{n-1}2 & \text{when } n \text{ is odd} \end{cases} $$

Explicitly, to compute $f(n)$, write $n$ in binary, then remove the rightmost one, along with all of the zeroes after it. For example, $f(104)=f(1101000_2)=110_2=6$.

An $m\times n$ bar is losing for Alice if and only if $f(m)=f(n)$.

The winning strategy is this. If you are given an $m\times n$ bar, where $f(n)>f(m)$, then reduce the value of $n$ to some $n'$ so that $f(n')=f(m)$. If $f(m)>f(n)$, reduce $m$ to $m'$ similarly.

Why is all of that true? We first must prove the following fact:

Lemma: For any $k\ge1$, let $L_k$ be the following list of $k$ numbers: $$L_k=f(k+1),f(k+2),\dots,f(2k).$$ The list $L_k$ will be some rearrangement of the list $0,1,2,\dots,(k-1)$.

Proof: We prove this by induction. You can directly check that $L_1=0$, and $L_2=1,0$.

Assume that $L_{k-1}$ is a rearrangement of $0,1,\dots,k-2$. Notice that the list $L_{k}$ is just the list $L_{k-1}$ with the entry $f(k)$ removed from the front and the entries $f(2k-1),f(2k)$ added to the end. Since $f(k)=f(2k)$, we are really just adding $f(2k-1)=k-1$. Since we aded $k-1$ to a rearrangement of $0,1,\dots,k-2$, it follows $L_{k}$ is a rearrangement of $0,1,\dots,k-2,k-1$. $\square$

With this Lemma under out belts, let's return to the game. Cutting a chocolate bar means reducing one of its dimensions. I claim that if you reduce the dimension $n$ to $n'$, then it must be true that $f(n')\neq f(n)$. Furthermore, it is possible to choose $n'$ so $f(n')$ is any number less than $f(n)$. This follows from the Lemma:

• If $n=2k+1$ is odd, then your options are $n'\in\{k+1,k+2\dots,2k\}$. By the Lemma, $f(n')$ can be any number in $L_k$, so any number less than $k=f(n)$, agreeing with the claim.
• If $n=2k$ is even, your options are $n'\in\{k+1,k+2,\dots,2k-1\}$. By the Lemma, $f(n')$ can be any number in the list $0,1,\dots,k-1$, except for $f(2k)=f(n)$. Since your options for $f(n')$ form an interval of integers with $f(n)$ missing, the claim holds.

This shows that when if $f(n)\neq f(m)$ you can always restore equality in one move, while when $f(n)=f(m)$, every move destroys this equality. This proves that the strategy of equalizing the bar until a $2\times2$ bar remains is winning.