From: greg@manifold.berkeley.edu (Greg Kuperberg) Newsgroups: sci.math,rec.puzzles Subject: Chomp, a $200 problem Date: 30 Jun 92 19:22:29 GMT Recently I posted a list of $6700 in prizes for math problems, and the problem that generated the most discussion is the following: >David Gale: $200. 3D Chomp. >In the game of Chomp, two players alternate stating triples of >non-negative integers, and once a triple (a,b,c) is named, then for >ever after neither player can name a triple (d,e,f) with d>=a, e>=b, >and f>=c. A player who names (0,0,0) loses. Does the first player >have a winning strategy? The key phrase in this question is "d>=a,e>=b, AND f=>c". That means if you play (2,3,4), then (10,4,5) and (2,3,5) are disallowed for ever after, but (1000,1000,2) is not. There is a fundamental theorem of Chomp: All games end. If you want to know why it is called Chomp, you can think of it this way: Imagine a big cake in the shape of the x>=0, y>=0, z>=0 octant in three dimensions. You take turns eating inset octants by naming the tip of the octant they are going to eat, which always has non-negative integer coordinates. You always have to eat something, and if you eat (0,0,0) you lose. Here is a sample game with play-by-play: ---------------------------------------------------------------- Player 1: (1,1,1) A daring move! Player 1 leaves three perpendicular planes in the playing field. Player 2 is confused. Player 2: (0,0,2) A fatal error! Player 2 leaves a horizontal plane with a rim consisting of two perpendicular lines. Player 1 is briefly pensive. Player 1: (0,1,0) Player 1 leaves an infinite 2 x 1 plank. Player 2 is nervous. Player 2: (10,0,1) Player 2 leaves a row with 10 cubes on top of an infinite row. Player 1: (11,0,0) Player 1 cuts the bottom row to 11 cubes. Player 2 resigns. ---------------------------------------------------------------- If you have a solution to David Gale's problem, write to me at greg@math.berkeley.edu. ============================================================================== From: adridg@sci.kun.nl (Adriaan de Groot) Newsgroups: sci.math Subject: Chomp (a game) Date: 13 Dec 1995 15:23:56 +0100 In the book "Mathematical Problems for Young and Old" by Paul Halmos, I found the game "Chomp". This deceptively simple game is played as follows: Play is on a rectangular board. The lower left square (call it (1,1)) contains a poison-candy (something like toast & vegemite) while all the other squares on the board contain regular candy. Players take turns indicating a piece of candy and removing it along with all pieces of candy in the upper-right-hand quadrant, like this: ******** ******** Begin situation. ******** ******** *** *** ******** After the move (4,3) ******** *** *** Second move is (6,2) ***** ********* The object of the game is to force your opponent to eat the poison-candy. My question is this: has anybody done any serious thinking about this? I've spent a fair amount of time on this, and have come up as good as empty handed. Halmos himself presents a few theorems about when a particular configuration of candies is a winning situation (ie. your opponent can be forced to eat the poisoned candy), but nothing general. I've proved a few more theorems but again, nothing general. I've pestered the computers on campus for days and days calculating winning situations, and there doesn't seem to be any great regularity in them. (Grrr.) So: 1) Have you heard of this game? Under what name(s)? 2) Where does it come from? 3) Got any interesting proofs for a general winning strategy? ============================================================================== From: hwatheod@leland.Stanford.EDU (theodore hwa) Newsgroups: sci.math Subject: Re: Chomp (a game) Date: 14 Dec 1995 00:19:33 GMT : 3) Got any interesting proofs for a general winning strategy? No, although one can prove that the first player always has a winning strategy. However the proof doesn't tell you what that winning strategy is. To see this, first observe that (1) the game ends in a finite number of moves and (2) the game cannot end in a draw, therefore one player or the other has a winning strategy. If it were the second player, then that would mean that whatever the first player played, the second player would have a winning response. In particular, suppose the first player takes only the upper right hand corner. The second player now has a winning response. That is, the resulting position is a winning position for the side that just moved. However, the resulting position is a position that the first player could have obtained for himself on the first move, so now the first player also has a winning strategy (namely, he plays on his first move, the move that the second player made in response to the upper-right-hand corner move.) We have a contradiction; thus the second player has no winning strategy, so the first player does. However, I don't know of any patterns for the general first move. For square boards and 2xn boards the strategy is easy, and winning moves have probably been compiled for small boards.