1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Help understanding proof that a winning strategy exists for Chomp

  1. Dec 17, 2013 #1
    1. The problem statement, all variables and given/known data

    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?

  2. jcsd
  3. Dec 17, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
  4. Dec 17, 2013 #3
    Thanks, I will do that! I wish the author had not omitted that fact.
    Last edited: Dec 17, 2013
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted