7
$\begingroup$

Billy and Bob start with two rectangular grid which can be modeled as a chocolate. They take turns cutting and eating the chocolate: on their turn, they can cut the chocolate along an edge parallel to the sides (thus resulting in three rectangles) and consume one of the three pieces, so that his partner has two chocolates, and therefore can make an analogous move. A player loses if they cannot make a cut. Assuming optimal play, who wins if:

(a) the starting rectangles are $1\times 2020$ and $2\times 4040$,
(b) the starting rectangles are $100\times100$ and $100\times 500$, and
(c) generalize.

My friend and I tested the first case (a) extensively, and ended up with somewhat of a mirroring thing if there are two $1\times n$ rectangles resultant. However, if $n$ is even one player could theoretically cut the $1\times n$ into two $1\times\frac n2$ rectangles, and discord the other $1\times n$.

I don't know how to continue.

$\endgroup$
16
  • 3
    $\begingroup$ You may need to work out the Sprague-Grundy numbers for small boards to start. $\endgroup$ – saulspatz Feb 21 at 23:56
  • 4
    $\begingroup$ @WillJagy I don't think so. You never have three pieces in chomp, do you? (Although I don't understand how a cut parallel to an edge results in three pieces.) $\endgroup$ – saulspatz Feb 22 at 0:45
  • 2
    $\begingroup$ You're presented with two rectangles. You choose one of them, split it into two rectangular pieces by means of a straight cut all the way across from one edge to the opposite edge; now, you temporarily have three rectangles. You choose one, eat it, and present the remaining two to your opponent. The game proceeds. I guess it should be mentioned that everything is integers. $\endgroup$ – Gerry Myerson Feb 22 at 2:23
  • 2
    $\begingroup$ I've figured out so far that if both pieces have one dimension less than 2, the beginning player can always win unless you have any of the following configurations. $1\times n | 1 \times n$ for $n$ containing an even number of factors of $2$. Or $1\times n | 2 \times 2n$ for $n$ containing an even number of factors of $2$. Or $2\times n| 2 \times n$ for $n$ containing an odd number of factors of $2$. I was able to prove this, but I couldn't figure out the generalization. So the answer to a is the second player can always win. $\endgroup$ – jMdA Feb 22 at 5:36
  • 3
    $\begingroup$ @vepir I have a conjecture for a general rule. Let $(e_0,e_1,\dots)=(1,3,4,5,\dots)$ be the increasing sequence of all integers whose prime factorization has an even number of twos, same for $(d_0,d_1,\dots)=(2,6,8,10,\dots)$. Then the losing positions are those of the form, for nonnegative integers $n,m,k$, $$ (e_n,e_{n\oplus k}),(e_m,e_{m\oplus k})\\ (e_n,e_{n\oplus k}),(d_m,d_{m\oplus k})\\ (d_n,d_{n\oplus k}),(d_m,d_{m\oplus k}) $$where $\oplus$ is nim-sum. The data for all positions with max dimension $24$ confirms this repl.it/@mearnest/Game-with-two-chocolate-bars#main.py $\endgroup$ – Mike Earnest Feb 23 at 6:11
4
$\begingroup$

I will write each game position as an ordered quadruple $(a,b,c,d)$, meaning an $a\times b$ bar and a $c\times d$ bar.

Call a number vile if it has an even number of twos in its prime factorization, and dopey if it has an odd number of twos. This terminology was originally conceived by Fraenkel.

Let $(e_0,e_1,e_2,\dots)=(1,3,4,5,\dots)$ denote the sorted, zero-indexed list of vile numbers, and let $(d_0,d_1,d_2,\dots)=(2,6,8,10,\dots)$ be the sorted list of dopey numbers. Finally, let $f(n)$ denote the index of $n$ in its list, regardless if that list is $e$ or $d$. That is, $f(3)=1$, $f(10)=3$, $f(4)=f(8)=2$.

Let $S$ be the of positions $(a,b,c,d)$ where all of these conditions are satisfied:

  • $a$ and $b$ have the same type (both vile or both dopey).
  • $c$ and $d$ have the same type.
  • $f(a)\oplus f(b)\oplus f(c)\oplus f(d)=0$, where $\oplus$ is the nim-sum.

A position is losing if and only if it is in $S$.

I found this pattern with help of Vepir and a computer program, while Jaap Scherphuis came up with the proof of its correctness.

We need to show that any move from $S$ results in a position outside of $S$, and every position not in $S$ has a legal move to $S$. First, here is the winning strategy to take any position outside $S$ to one in $S$:

  • Suppose $a$ and $b$ have different types, WLOG $a$ is vile and $b$ is dopey. A winning move is to cut the $a\times b$ bar in half perpendicularly to the $b$ side, and eat the other bar, leaving the position $(a,b/2,a,b/2)$. Since $b$ is dopey, it follows that $b/2$ is vile, so it is easy to check the nim-sum condition and verify this position is in $S$.
    The same logic applies when $c$ and $d$ have different types.

  • Otherwise, you will have $f(a)\oplus f(b)\oplus f(c) \oplus f(d)\neq 0$. The idea is to make a move which changes a single index of one of the coordinates, without changing its type, and which reduces the index corresponding to the winning move on the nim game with heap sizes $f(a),f(b),f(c),f(d)$.

Now, suppose $(a,b,c,d)\in S$. Any move where you eat one of the pieces from the bar you broke will change exactly one of the coordinates. This necessarily leaves a position outside of $S$, because for any choice of three coordinates, there is a unique choice of a fourth coordinate for which the position is in $S$. Therefore, we restrict out attention to moves where you eat the bar you did not break, of the form $$ (a,b,c,d)\implies (a',b,a-a',b) $$ where $1\le a' \le a-1$. In order for this new position to be in $S$, $a'$ and $a-a'$ must both have the same type as $b$, and it must be true that $f(a')=f(a-a')$. If $a'$ and $a-a'$ have the same type and index, they must be equal, so the move would have to be $(a/2, b,a/2,b)$. But $a/2$ has the opposite type of $a$, so this is not in $S$.

$\endgroup$
1
  • $\begingroup$ Very nicely done! I had not fleshed out all the details of the proof, but you did it more cleanly than what I was thinking of. $\endgroup$ – Jaap Scherphuis Feb 23 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.