1
$\begingroup$

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?

  • 0
    [This page](http://www.win.tue.nl/~aeb/games/chomp.html) has quite a bit of information and a fairly substantial set of references for Chomp.2011-12-19

1 Answers 1

4

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.

  • 1
    I now realize we weren't really talking about the same thing.2016-07-01