2
$\begingroup$

A chocolate bar with rectangular grid has size 4 × 11. Two players make moves in turns. In each step a player breaks one of the current chocolate pieces along a grid line. The player who cannot make a step loses the game. Who wins - the player who starts the game or his opponent?

We consider a two-player game. The players are given an x × y rectangle (where x and y are positive integers). The players take turns moving. A move consists of dividing a rectangle into two rectangles with a single vertical or horizontal cut. The resulting rectangles must have positive integer dimensions.

$\endgroup$
3
  • $\begingroup$ When you write "the grid line" in the third sentence do you mean "a grid line"? $\endgroup$ – Qiaochu Yuan Jan 17 at 0:36
  • 1
    $\begingroup$ You can solve this problem algorithmically for any $n$ and $m$ using the theory of Grundy numbers en.m.wikipedia.org/wiki/Nimber. $\endgroup$ – vujazzman Jan 17 at 0:46
  • $\begingroup$ @QiaochuYuan exactly. That's what I meant. $\endgroup$ – Muhammed Abdulkabir Jan 17 at 0:47
8
$\begingroup$

When you break along a grid line, you increase the number of separate pieces of chocolate by $1$. You start off with one piece of chocolate, and at the end of the game there are $xy$ separate pieces.

So player $1$ wins when $xy$ is even, and player $2$ wins when $xy$ is odd.

$\endgroup$
1
  • $\begingroup$ +1 And like the Brussels Sprouts game, players cannot affect the result or length of the game $\endgroup$ – Henry Jan 17 at 1:50

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