Mathematics and Computing Department
York College (CUNY)
Jamaica, NY 11451
Email: email@example.com (for additions, suggestions, and corrections)
Sprouts is a delightful geometrical game invented by John Horton Conway and Michael
Paterson February 21, 1967! Conway and Paterson were at Cambridge University at the
How does the game work?
Initial position: Start with n dots on a sheet of paper.
1. The players alternate moving.
2. A move consists of drawing a line segment on the paper joining a dot to itself
or joining a pair of distinct dots, and then PLACING A NEW DOT ON THIS SEGMENT so
a. The line segment does not intersect (or touch) itself or any previously made line
segment or dot.
b. No dot can have more than 3 line segments coming out of it.
3. The winner of the game is last person to make a successful move. If you can not
move, you lose!
It might seem at first glance that this game might, in some cases, go for ever. That
is, that for some choice of moves on the part of the players one could follow the
rules forever. It turns out that some simple mathematical thinking shows this is
not true. We can define the value
of a position as the number of segments at each dot at that stage of the game. A dot
is "used up" if it has three line segments at it. At the start of the game the value
of the position is 3n where n is the number of dots. Each move decreases the old
value by 2 and increases the value by 1 with a net decrease in value of 1. Hence, the game
can not last more than 3n moves. If the value of a position is one no move can be
made. Hence, no game can last more than 3n-1 moves. Furthermore, one can show that
the game must last at least 2n moves. Thus, for example, the game with 3 dots lasts at
least 6 moves but no more than 8 moves.
Remarkably, like many other combinatorial geometric games, no strategy is known for
every value of n to guarantee which particular player will win. Computer analysis
of the game with normal play has been pushed to 11 dots. This work, done by D. Applegate,
G. Jacobson, and D. Sleator suggests that the first player has a win in sprouts if
the number of dots leaves the remainder of 3, 4, or 5 when divided by 6.
Conway refers to playing combinatorial games so that the person who can not move loses
as normal play. Historically, playing so that the person who can not move wins is
known as misère play. Surprisingly, in most cases it seems to be harder to analyze
the misère play of games than to analyze normal play.
Conway also invented a game related to Sprouts called Brussel Sprouts. Brussel Sprouts
is similar to sprouts but starts with n small crosses instead of n dots. A move consists
of consists of joining a free line at one cross to a free line at the same or different cross and then picking a point of the joining line and drawing a "bar" through
it. Again one does not allow lines to cross themselves or pass through previous lines
or crosses. The winner of the game is the last person to make a legal move.
Unlike sprouts, Brussel Sprouts is a joke! Can you determine why?
Hint: If one starts with n crosses, the game always ends after exactly 5n-2 moves!
An interesting new question that I am not sure has been studied is the consequence of altering the rules of the (standard) version of Sprouts so that one can not make a move that joins a dot to itself. I know nothing about this variant of Sprouts but I think it would be interesting to study it.
Berlekamp, E., and J. Conway, R. Guy, Winning Ways (Volumes I and II), Academic Press,
Gardner, M., Mathematical Carnival, Knopf, New York, 1975, p. 3-11.
Back to list of tidbits