## Encyclopedia > Sprouts game

Article Content

# Sprouts game

Sprouts is a pencil-and-paper game with interesting mathematical properties.
It was invented by mathematicians John Conway and Michael S. Paterson[?] at Cambridge University in 1967.

The game is played by two players, starting with a few dots (called spots) drawn on a sheet of paper. To make a move, a player draws a curve between two spots or a loop from a spot to itself. The curve may not cross any other curve. The player makes a new spot on the curve, dividing it in two. Each spot can have at most three curves connected to it. The player who makes the last move wins.

Sprouts has been studied from the perspectives of graph theory and topology. It can be proven that a game started with n spots will last at least 2n moves and at most 3n - 1 moves.
By enumerating all possible moves, one can show that the first player is guaranteed a win in games involving three, four, or five spots.
The second player can always win a game started with one, two, or six spots.

At Bell Labs in 1990, David Applegate[?], Guy Jacobson[?], and Daniel Sleator used a lot of computer power to push the analysis out to eleven spots. They conjectured that the first player has a winning strategy when the number of spots divided by six leaves a remainder of three, four, or five.

The game of sprouts played an important role in the first part of the Piers Anthony book Macroscope[?].

• [2] (http://www.sciencenews.org/sn_arc97/4_5_97/mathland.htm) Ivars Peterson, "Sprouts for Spring," Science News Online.

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia
 Search over one million articles, find something about almost anything!

Featured Article
 East Hampton North, New York ... town is \$45,347, and the median income for a family is \$55,357. Males have a median income of \$38,566 versus \$29,750 for females. The per capita income for the town is ...