Sprouts! (10/19/2001)

Prepared by:

Joseph Malkevitch
Mathematics and Computing Department
York College (CUNY)
Jamaica, NY 11451

Email: malkevitch@york.cuny.edu (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 time.

How does the game work?

Initial position: Start with n dots on a sheet of paper.

Rules:

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 that:

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!

Analysis

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!


(8/25/2000)

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.

Reference:

Berlekamp, E., and J. Conway, R. Guy, Winning Ways (Volumes I and II), Academic Press, London, 1982.

Gardner, M., Mathematical Carnival, Knopf, New York, 1975, p. 3-11.


Back to list of tidbits