5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It seems that the answer depends on the size of the chocolate. For a simple example: if the size is $1\times 2$, then the first mover will definitely win. But when the size is $3\times 3$ and the poisoned square is $(2,2)$, then the second mover must win. $\endgroup$ – OnoL Apr 3 '17 at 21:36
  • $\begingroup$ Surely this is finite deterministic game without draw and therefore it is equivalent to game of Nim. However is very hard to compute Sprague–Grundy function for some games. (I don't say anything about this one, I need to think.) $\endgroup$ – Smylic Apr 3 '17 at 22:02
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ As an example, if the poisoned piece is in a corner, then the winning strategy is to make the remaining rectangle into a big square. If this is not possible (the remaining rectangle is already a square) then you are in a losing position $\endgroup$ – Henry Apr 4 '17 at 7:45

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.