Ivars Peterson's MathTrek

April 7, 1997

# Sprouts for Spring

The game of sprouts has a way of growing on you.

This two-person, pencil-and-paper game is simple enough that children can play it. Yet its intricacies provide much food for mathematical thought.

The players start with a certain number of dots scattered across a sheet of paper. A move consists of drawing either a line between two dots or a loop starting and ending at the same dot. The player then places an additional dot somewhere along the new line or loop.

The line (or loop) may be of any shape, but it must not cross itself, cross a previously drawn line, or pass through a previously made dot. Furthermore, no dot may have more than three lines emanating from it. Hence, a new dot placed on a line actually has two connections already made.

Players take turns drawing curves. The winner is the last person able to play.

At first glance, it may seem that a game could keep sprouting forever. However, because each turn makes two connections and opens up only one, the number of moves has a definite limit. Indeed, one can prove that a game starting with n dots must end after a maximum of 3n - 1 moves.

Initially, there are no lines, so the dots have a total of 3n possible links. Each move uses up two of those openings, at the beginning and end of the drawn curve, but also adds a new dot with one opening. Thus, each move decreases the number of openings by one. Because a move requires filling two openings, the game can't continue when only one opening remains. Hence, no game can last beyond 3n - 1 moves.

One can also show that every game must go at least 2n moves. Thus, a game starting with three dots must end on or before the eighth move and must last at least six moves.

 [Figure] A typical three-dot sprouts game. For a small number of dots, one can diagram all the possible moves and determine which player is guaranteed a win. The second player can always win a game starting with two or six dots. The first player is guaranteed a win in games involving three, four, or five dots. A few years ago, David Applegate, Guy Jacobson, and Daniel Sleator, then at Bell Labs, used a lot of computer power to push the analysis of sprouts out to eleven dots. They found that the second player wins in games involving seven or eight dots, while the first player wins in games involving nine, ten, or eleven dots. There's an interesting pattern here. The researchers conjectured that the first player has a winning strategy if the number of dots divided by six produces a remainder of three, four, or five. Hence, their prediction for a game involving twelve dots is a win for the second player (remainder is zero after dividing twelve by six).

Games can sprout all sorts of unexpected growth patterns, making formulation of a winning strategy a tricky proposition. No one has yet worked out a complete strategy for perfect play. Toward the end of a game, however, one can often see how to draw closed curves that divide the plane into regions in such a way as to lead to a win.

The game has also attracted the attention of mathematicians, who have investigated the game in terms of graph theory and topology. It's possible to try sprouts, for example, on a doughnut-shaped surface or in higher dimensions.

Sprouts was invented in 1967 by Princeton mathematician John H. Conway and Michael S. Paterson, when both Conway and Paterson were at the University of Cambridge in England. "The day after sprouts sprouted, it seemed that everyone was playing it," Conway once wrote. "At coffee or tea times, there were little groups of people peering over ridiculous to fantastic sprout positions."

Piers Anthony picked up on the sprouts craze in his science-fiction novel Macroscope. "Sprouts is an intellectual game that has had an underground popularity with scientists for a number of years," one character in the novel notes. "The rules are simple. All you do is connect the dots."

Anthony then proceeds to illustrate with a sample three-dot game that runs for six moves, with a win for the first player.

"It's not a game," protests another character in Macroscope. "There's no element of chance or skill."

Nonetheless, the possibilities are sufficiently vast that sprouts and its variants offer a great of deal of enjoyment for both player and mathematician.

### References:

Anthony, Piers. 1969. Macroscope. New York: Avon.

Applegate, David, Guy Jacobson, and Daniel Sleator. 1991. Computer analysis of sprouts. Carnegie Mellon University Computer Science Technical Report No. CMU-CS-91-144, May.

Copper, Mark. 1993. Graph theory and the game of sprouts. American Mathematical Monthly 100(May):478-482..

Gardner, Martin. 1989. Sprouts and Brussels sprouts. In Mathematical Carnival. Washington, D.C.: Mathematical Association of America.

Lam, T.K. 1997. Connected sprouts. American Mathematical Monthly 104(February):116-119.