Winning strategy in game of cutting rectangle

477 Views Asked by At

There is a bar of chocolate of size $N$ x $M$. Little square $(x, y)$ is poisoned. There are 2 players taking turns. In each move they can cut the bar along any of the horizontal or vertical lines, then the part which does not contain $(x, y)$ is being eaten. The player who is left only with square $(x, y)$ loses (beacause it is poisoned). Which player has the winning strategy? I guess that this game is equivalent to game of Nim due to Sprauge-Grundy theorem, but I don't know how.

1

There are 1 best solutions below

1
On

It seems like this game is more obviously (that is, not even for Sprague–Grundy reasons) equivalent to Nim.

More precisely, consider the distances $x-1, y-1, N-x, M-y$ between the poisoned square and the sides of the rectangle. Each move reduces the rectangle to a smaller one, and in doing so reduces one of the distances while keeping the others the same. When all distances are $0$, the poisoned square is the only one left, and the next player to move loses. So the game is equivalent to a game of Nim with four piles of sizes $x-1, y-1, N-x, M-y$.