Help understanding proof that a winning strategy exists for Chomp

[Nick O]

Homework Statement

Chomp is a game played by two players. In this game, cookies are laid out on a rectangular grid. The cookie in the top left position is poisoned, as shown in Figure 1(a). The two players take turns making moves; at each move, a player is required to eat a remaining cookie, together with all cookies to the right and/or below it (see Figure 1(b), for example). The loser is the player who has no choice but to eat the poisoned cookie. We ask whether one of the two players has a winning strategy. That is, can one of the players always make moves that are guaranteed to lead to a win?

Solution: We will give a nonconstructive existence proof of a winning strategy for the first player. That is, we will show that the first player always has a winning strategy without explicitly describing the moves this player must follow.

First, note that the game ends and cannot finish in a draw because with each move at least one cookie is eaten, so after no more than m × n moves the game ends, where the initial grid is m × n. Now, suppose that the first player begins the game by eating just the cookie in the bottom right corner. There are two possibilities, this is the first move of a winning strategy for the first player, or the second player can make a move that is the first move of a winning strategy for the second player. In this second case, instead of eating just the cookie in the bottom right corner, the first player could have made the same move that the second player made as the first move of a winning strategy (and then continued to follow that winning strategy). This would guarantee a win for the first player.

2. My question

Sorry, but my problem doesn't fit in the default template, because this is simply a question about the explanation of the solution.

How are we justified in assuming that there are only two possibilities after eating the bottom right cookie, namely that it is either the first move in a winning strategy, or that there exists a move that the second player can make that is the first move in a winning strategy? How can we dismiss the possibility that neither side can possibly guarantee the ability to win after the first round? Unless we have proven otherwise, is it not possible that a guarantee to win does not appear until, say, the second round?

Thanks.

 

[haruspex]

How are we justified in assuming that there are only two possibilities after eating the bottom right cookie, namely that it is either the first move in a winning strategy, or that there exists a move that the second player can make that is the first move in a winning strategy?

This is a general theorem about games in which there is an upper bound on the number of moves and no draw is possible. (There may be some other criteria I've forgotten.) You can prove it inductively on the maximum number of remaining moves. Try it as an exercise.

 

[Nick O]

Thanks, I will do that! I wish the author had not omitted that fact.