Billy and Bob start with two rectangular grid which can be modeled as a chocolate

Question

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.

Answer 1

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$.