Reply to comment

Mathematical mysteries: Chomp

March 2001

Chomp is a simple two-dimensional game, played as follows.

Cookies are set out on a rectangular grid. The bottom left cookie is poisoned.

Two players take it in turn to "chomp" - that is, to eat one of the remaining cookies, plus all the cookies above and to the right of that cookie.

The loser is the player who has to eat the poisoned cookie.

We can ask if either player has a winning strategy, that is, can one player, before starting play, be sure of winning?

The answer to this question is yes. One of the players is sure to have a winning strategy. This is easy to see, because the game must finish in finitely many moves, and can't be drawn. In fact, the person who plays first can be certain of winning, if they make the right moves. To see this, suppose the first player (Player A) makes the first move by chomping just the top right-hand cookie. Then either this is the first move of a winning strategy for Player A, or there is a reply which is the first move of a winning strategy for Player B. If the latter is the case, then Player A could have opened with that very move and been guaranteed a win.

So what is the winning strategy for Player A? Well, that is the mystery - nobody knows! The proof that there is a winning strategy for the first player was very simple - but didn't describe the strategy. No one has ever been able to do that. Maybe you can!

There are some simple cases where a winning strategy can be described - Square Chomp and Thin Chomp. Square Chomp is Chomp played on a square grid, and Thin Chomp is Chomp played on a grid that is only two squares wide. See if you can find the winning strategies in these special cases - or find out how if you get stuck.


About the author

Helen Joyce is an assistant editor of Plus.

Thanks to John Webb of the University of Cape Town in South Africa for telling me about Chomp.

Reply

  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.

More information about formatting options

To prevent automated spam submissions leave this field empty.
By submitting this form, you accept the Mollom privacy policy.