SCIENCE NEWS ONLINE

Ivars MathLand






space April 5, 1997Rule

Sprouts for Spring

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

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 below: A typical three-dot sprouts game.

For a small number of dots, one can diagram all possible moves and determine which player is guaranteed to win. The second player can always win a game starting with one, two, or six dots. The first player is guaranteed a win in games involving three, four, or five dots.

In 1990, 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 and 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 it 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 by Michael S. Paterson, when both 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.

Copyright 1997 by Ivars Peterson.

References:

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

Applegate, D., G. Jacobsen, and D. Sleator. Computer analysis of sprouts. Carnegie Mellon University Computer Science Technical Report No. CMU-CS-91-144, May 1991.

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

Gardner, M. 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.

John Conway describes a strategy for playing sprouts at http://www.forum.swarthmore.edu/news.archives/geometry.research/article399.html.


RedTriRule


Comments are welcome. Please send messages to Ivars Peterson at ip@scisvc.org.

Ivars Peterson is the mathematics and physics writer at Science News. He is the author of The Mathematical Tourist, Islands of Truth, Newton's Clock, and *Fatal Defect. His latest book, The Jungles of Randomness: A Mathematical Safari, is to be published in October 1997 by Wiley.

*NOW AVAILABLE in paperback: Fatal Defect: Chasing Killer Computer Bugs by Ivars Peterson. Vintage Books, 1996. ISBN 0-679-74027-9. U.S. $13.00.


RedTriRule


spaceMathLand Archives!


Rule

SEARCH!
SCIENCE NEWS

copyright 1997 Science Service

Gray Rule