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 (above). 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.
Muse, February 2005, p. 35.
No comments:
Post a Comment