Tushar and Gaurav once won a competition and were given a single Dairy Milk Chocolate Bar as the first prize. Little kids as they were, they started fighting over sharing it. Finally they decided to play a game:

They lay down the Bar (which is a grid of squares) on the table. Gaurav said, "Since I am older than you, I shall have the first portion out." Tushar replied, "Then I give out the rule: you choose any square out of the grid, and all the chocolate that is above and to the right to it is yours. Then I'll choose another square and we'll carry on."

Both agreed that whoever ends up eating the last square (the bottom-left one) is a loser.

The question is, given a standard large Dairy Milk Bar (dimensions $5\times12$) can any of the kids devise a strategy to beat the other? Alternatively, can this be generalized for any $m\times n$ grid?

  • 1
    $\begingroup$ Perhaps if you divide your text into paragraphs, it would be more readable. $\endgroup$ – Martin Sleziak Dec 19 '11 at 7:01
  • 1
    $\begingroup$ @MartinSleziak In a moment :) $\endgroup$ – Green Noob Dec 19 '11 at 7:05
  • $\begingroup$ This is the game "chomp" $\endgroup$ – Henno Brandsma Dec 19 '11 at 7:08
  • $\begingroup$ To explore such games and their generalisations you could track down a copy of "Winning Ways for your Mathematical Plays" by Berlekamp, Conway & Guy - Volume 2 of the first edition/Volume 3 (I believe) of the latest edition. $\endgroup$ – Mark Bennet Dec 19 '11 at 7:09
  • 3
    $\begingroup$ @Henno Brandsma: Not quite chomp, there the last square is poisoned. In this game, first player can eat the whole bar, and say with a smile "I am the loser." $\endgroup$ – André Nicolas Dec 19 '11 at 7:19

Gaurav has a winning strategy, though it may be hard to find. Suppose, to get a contradiction, that Tushar has a winning strategy. Let Gaurav begin by taking the single square in the upper righthand corner. Then Tushar plays whatever move his winning strategy dictates. Whatever that move is, Gaurav could have made it in the first place and then continued with Tushar’s winning strategy. Thus, Tushar cannot possibly have a winning strategy, and therefore Gaurav must have one. (This reasoning is known as the strategy-stealing argument.)

For more information about the game and some references see this page.

  • $\begingroup$ Interesting idea Brian.. But my question was not about who the winner is.. I'm more interested in the winning strategy $\endgroup$ – Green Noob Dec 20 '11 at 5:22
  • $\begingroup$ I think we will only manage to get this argument to work if the Tushars move is not dependent on the first move by Gaurav. If it becomes the best move out of provocation from the first move, maybe it would not have been the best move before the first move was made. $\endgroup$ – mathreadler Jul 1 '16 at 5:43
  • $\begingroup$ @mathreadler: It doesn’t matter. Read the material at the strategy-stealing link. $\endgroup$ – Brian M. Scott Jul 1 '16 at 19:29
  • 1
    $\begingroup$ I now realize we weren't really talking about the same thing. $\endgroup$ – mathreadler Jul 1 '16 at 23:41

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.