Even the simplest of games can pose tough mathematical challenges. One such game is Chomp. It was invented in the early 1970s by David Gale of the University of California, Berkeley, who was also responsible for the board game Bridg-it, and it was later dubbed Chomp by Martin Gardner.
Both Chomp and Bridg-it are examples of combinatorial games, in which nothing is hidden from the players and no chance is involved.
Chomp starts with a rectangular array of counters arranged neatly in rows and columns. A move consists of selecting any counter, then removing that counter along with all the counters above and to the right of it. In effect, the player takes a rectangular or square “bite” out of the array–just as if the array were a rectangular, segmented chocolate bar.
Two players take turns removing counters. The loser is the one forced to take the last “poisoned” counter in the lower left corner.
Winning strategies are known for two cases.
When the array is a square, the first player wins by selecting the counter that is diagonally up and to the right of the poisoned counter. This bite leaves one row and one column, with the poisoned piece at the vertex. From that point on, the first player simply takes from one line whatever his or her opponent takes from the other line. Eventually, the second player must take the poisoned piece.
When the array is two columns or two rows wide (2-by-n or n-by-2), the first player can always win by taking the counter at the top right so that one column or row is one counter longer than the other. From then on, the first player always plays so as to restore this situation.
What makes the game maddeningly intriguing is that you can prove mathematically that the first player can always win, but there is no known general strategy for winning the game on every possible rectangular array. Recent work on 3-by-n arrays has illuminated various patterns associated with winning strategies, but the picture isn’t complete yet. And it’s possible to extend the study of the game to three- and higher-dimensional arrays.
Interestingly, Chomp is equivalent to a game based on an arithmetic problem. Two players start with a positive integer N and a list of all the divisors of N, including N but excluding 1. The players take turns crossing out a divisor and all its multiples. The player forced to take N loses.
Chomp recently figured into a winning project for Steven Byrnes, a senior at Roxbury Latin School in Massachusetts and a finalist in this year’s Intel Science Talent Search.
Chomp belongs to a family of two-player combinatorial games, which are described as poset games. A poset, or partially ordered set, is a set of elements in which some elements are smaller than other elements but not every pair of elements can necessarily be compared.
One example of a poset consists of an integer and all its positive divisors (excluding 1). For instance, the positive divisors of 42 are 2, 3, 6, 7, 14, and 21, and the associated poset is designated {2, 3, 6, 7, 14, 21, 42}.
In a poset game (as in Chomp), two players take turns making moves. On each move, a player picks an element from the given set and removes all elements of the set greater than or equal to the selected element. Then the other player picks an element from the new, smaller poset, and so on.
Byrnes proved a powerful theorem concerning poset games, which had typically been studied individually or in isolation rather than as a group. In essence, his theorem pinpoints patterns associated with winning and losing positions in generic poset games. It’s the first major theorem that applies to all poset games, Byrnes noted in a paper describing his results.
“The Poset Game Periodicity Theorem shows that poset games are connected not only by common rules but also by common structure, turning these seemingly unrelated problems into a unified field,” Byrnes concluded. “Using this theorem as a foundation and starting point, we anticipate further study of the commonalities of poset games, extending the power and reach of this new field of combinatorial game theory.”
One immediate consequence has been new insights into Chomp, particularly in illuminating patterns evident in winning strategies for 3-by-n arrays and in settling some conjectures concerning the game.
A past winner at the U.S.A. Mathematical Olympiad and the U.S. Physics Olympiad, Byrnes has interests that go beyond mathematics. He runs on the varsity cross-country team, enjoys debating, participates in his school’s French club, and sings and plays jazz piano.
