A game based on cutting rectangles from paper

Question

You are given a piece of paper that consists of $w \times h$ squares. You can cut the sheet in a vertical or horizontal axis at the positions with integer coordinates so that the paper becomes two separate sheets. $A$ and $B$ play the game as follows: If you cut out the $1 \times 1$ sheet you will be the winner. $A$ is the first to cut.

For example:

• $w=2,h=2$. The result is $B$, because firstly, $A$ has to cut $2 \times 2$ paper into $2$ sheets have size $1 \times 2$. Then $B$ chooses the $1 \times 2$ sheet to cut it into $2$ sheets have size $1 \times 1$. So $B$ is the winner.

• $w=4,h=2$. The result is $A$, because $A$ can cut into $2$ sheets have size $2 \times 2$. Next, $B$ is forced to cut $2 \times 2$ sheets into $2$ sheets have size $2 \times 1$. We have $2$ sheets have size $2 \times 1$ and $1$ sheet have size $2 \times 2$. A just needs to select $2 \times 1$ sheet and cut it to win.

My problem is how to determine which of $A$ or $B$ will win in the general case.

This is my try: First of all, I think this problem relevant to parity of $w$ and $h$.

• If $h=1$ or $w=1$. A is always win.

• If $h>1$ and $w>1$. We will consider the parity of $w$ and h. Firstly, if $h=2$ or $w=2$, soppose that $h=2$.

• If $w=2$. We will have $B$ is the winner.

• If $w>2$ and $w\equiv 1(\text{ mod }2)$. I will get some examples for this case:

• With $w=3$ we will have $A$ win.

• With $w=5$ we will have $A$ win.

• With $w=7$ we will have $B$ win. Because A will separate the sheet $2x7$ into 2 sheets $2x3$ and $2x4$, then B will seperate the sheet $2x4$ into 2 sheets $2x2$ and $2x2$. Finally, B is the winner.

• With $w=9$, similarly ,we will have $A$ win.

• With $w=11$, similarly, we will have $A$ win. So I can't see the pattern in this case!!!

Ps: I see that with any case $w>1$ and $h>1$, every turn, cutting is relevant to 2 sheets are $2x2$ and $2x3$. And I want to build recursive from that.

Answer 1

I know the answer when we restrict the shorter side to be $2$ or $3$. In these cases, no one will ever want to divide the cake lengthwise, for that leaves a $1xn$ strip, so we can just consider a game where we divide a $1\times n$ strip. (Note that $2\times 2$ is a winning position if and only if $3\times n$ is a winning position.)

In this new game, you lose if you make a $1\times 1$ square (since in the "real" game that corresponds to leaving a $2\times 1$ or $3\times 1$) so in the new game we will say that you must leave at least $2$ squares in each of the rectangles, and you lose if you cannot make a move. At this point, the rectangular structure becomes unimportant, and we can just think of dividing a pile of counters into two piles of at least two counters each.

This is a nim-like game that can be analyzed by the Sprague-Grundy theory.

I wrote a python script to do this for $n\leq100.$

'''
Divide a pile into two piles, 
each of size at least two'''

def mex(n):
    values = set()
    for k in range(2, n//2 + 1):
        values.add(M[k]^M[n-k])  # nim sum
    for k in range(0,n):
        if k not in values:
            return k

M= { }
M[1]=M[2]=M[3]=0
for n in range(4,101):
    M[n] = mex(n)

print([k for k in range(1,101) if M[k]==0])

The script prints a list of all the losing values for $n\leq100,$ and it doesn't look promising.

[1, 2, 3, 7, 11, 17, 23, 27, 31, 37, 41, 45, 57, 61, 65, 75, 79, 91, 95, 99]

This coincides with A274161 (for $n>1$) for which the formula "The sequence consists of $\{2,3,17,37\}$ along with all positive integers congruent to $7, 11, 23, 27,$ and $31$ modulo $34$" is given.

It's easy to see that the edge-delete game on $P_n$ described in A274161 is the same as the "new game" I described above. I didn't think of checking OEIS until I was about to press the "Post your answer" button, but I decided to leave my analysis in because it seems clear that the general game can be reduced to a nim-like game in a similar fashion.