Welcome to NRICH.

 
Chocolate Bar Game
By Louise (P4118) on Thursday, March 29, 2001 - 07:13 pm:

Take a chocolate bar, nxm in size. One of the blocks has poison in it. Each of the 2 players has to take it in turn to break off at least one complete row or column of the chocolate. The player left with the poison block obviously dies therefore loses.
Can anyone think of a strategy for winning each time for all nxm or nxn size chocolate bars?
Does the position of the poison affect the winning strategy?

Any suggestions much appreciated.
Louise x

By Brad Rodgers (P1930) on Thursday, March 29, 2001 - 11:41 pm:

Do the players know where the poison is?

By Michael Doré (Md285) on Friday, March 30, 2001 - 12:17 am:

I'm guessing yes - otherwise there wouldn't be any chance of finding a "strategy for winning each time" no matter what m,n were.

If the position was unknown, the best strategy probabilistically would pretty clearly be to break off a row if and only if the rows are smaller than the columns, each time. I think I can prove this, but it probably isn't relevant anyway.

OK, so let's take the case in which the position is known to both players. Assume m + n is odd. I claim that the player going first can always escape death.

First of all note that no player is ever forced to choose the poisoned chocolate unless m = n = 1. So if both players play properly, the poisoned chocolate will be the last chocolate piece left. With each turn, m + n decreases by 1, so it will have decreased to 2 after an odd number of turns, so it will be the second player's turn when m = n = 1.

On the other hand if m + n is odd then no matter what the first player does (and I'm assuming he doesn't choose the poisoned chocolate) he will reduce m + n by 1, so after his turn, m + n will be odd and it will be the second players turn. So we know from above that the second player can survive. So the 1st player dies.

Therefore the 1st player wins if m + n is odd and the 2nd player wins if m + n is even.

By Mark Adams (Maa25) on Friday, March 30, 2001 - 05:33 pm:

Michael,

If the players can remove more than one row/column at a time that won't work. Lets say that a player can remove any number (>0) of rows or any number of columns, but not both. Then I claim that the first player can win, unless n=m. For, if the piece of chocolate is square at the start of a players (lets say player 2) turn, he is bound to lose. He must remove some rows, reducing the chocolate to a rectangle, so on the next turn player 1 can remove some columns to reduce the chocolate to a square again. This is smaller than the initial square, so eventually player 2 ends up with a 1x1 square and bites the dust. So the first player to move just has to reduce the chocolate to a square, which he can always do unless it is square to start with.

By Michael Doré (Md285) on Friday, March 30, 2001 - 07:04 pm:

Ah yes sorry; I missed the phrase "at least". Thanks.