|
MatheMUSEments
Chomping to Victory
By Ivars Peterson
Muse, February 2005, p. 35.
It's often tough to figure out how to win even a really
simple game.
Consider the two-player game called Chomp. A move
consists of picking one checker anywhere in a rectangular array of
checkers, then removing that checker along with all the checkers above
and to the right of it. It's like taking a big, neat bite out of a
chocolate bar divided into easy-to-break-off sections.
You and your opponent take turns "chomping"
on the checkers. The loser is the player forced to take the last "poisoned"
checker in the lower left corner.
 |
Chomp on a 5-by-6 field. The first player selects a counter (green, top left) and removes a block of six counters (top right). The second player selects one of the remaining counters (yellow, top right) and removes a block of two counters (bottom left). The first player responds, leaving the L-shaped array shown at bottom right. Who will be forced to take the last, poisoned counter (red)? |
When you start with a square of checkers, the first
player can automatically win. Can you see how?
Here's the strategy. If you go first, pick the checker
that's diagonally up and to the right of the poisoned checker. Such
a bite leaves one row and one column, with the poisoned piece at the
corner. From that point on, simply take from one line whatever your
opponent takes from the other line. Eventually, your opponent is forced
to take the poisoned piece.
If the checkers are in a narrow rectangle that's two
checkers wide and any number of checkers long, the first player also
wins automatically. If you go first, take one checker from the end
of one line so that one column or row is one checker longer than the
other. Depending on what your opponent does in his or her turn, pick
a checker that again makes one column or row one checker longer than
the other. Again, your opponent gets stuck with the poisoned piece.
Here's the frustrating thing. Mathematicians have
proved that the first player always wins—whether the checkers
are in a square or in any sort of rectangle. The trouble is that no
one has been able to figure out a foolproof winning strategy that
works every time if the initial rectangle of checkers has more columns
than it has rows (except when there are only two rows).
Maybe you can help. Can you figure out a strategy
for chomping to victory when you have checkers in a pattern that is
three rows long and any number of columns wide? Start with a small
pattern, such as 12 checkers arranged in four columns and three rows,
then go from there.
Happy chomping!
You can play Chomp online at lpcs.math.msu.su/~pentus/abacus.htm
or www.duke.edu/~ljw6/ooga/chompgame.html. You can download the game
from www.zillions-of-games.com/games/chomp.html.
|
SNK RSS Feed 
