The Chocolate Game

Please comment your solutions, questions and remarks..

I heard this from Lauri Hella, but he doesn’t remember from whom he heard this.

The game is played between two players as follows. There is an [tex]n\times m[/tex] bar of chocolate on the table. See the picture below. First Player 1 chooses a chocolate piece and then removes (eats!) all the pieces that lie up-right from that piece. For instance if he picks the piece (4,2), then he removes all the pieces [tex](x,y)[/tex] such that [tex]x\geqslant 4[/tex] and [tex]y\geqslant 2[/tex]. This move is illustrated in the picture. Then Player 2 does the same: she chooses a piece, say (5,1), and removes all pieces up-right from it (in this case only one, since (5,2) and (5,3) are already removed by Player 1). This move is not illustrated. At each move a player has to remove some chocolate in this way. The player who takes the last piece [tex](0,0)[/tex], loses.

Show that Player 1 (the beginner) has a winning strategy. (Assume nm>1)

Level 3/5

The picture is taken from here, is made by Kifer and is edited by me (using gimp..). It is licensed under a Creative Commons license

Hint after Read More

.
.
.
.
.
.
.
.
.
WARNING, a hint below.
.
.
.
.
.
.
.
.
.
.
.
Use similar reasoning as in the proof of Theorem 2 in the post about tic-tac-toe