Sprouts

Sprouts is a game that two players can play on paper.

Initially, several dots are drawn on the paper, as in figure 1.

Figure 1.  Sprouts initialized with 4 dots.

Thereafter, each player takes a turn connecting dots with a straight or curved path, and then draws a dot on it. The dot divides the new path into two paths, which are not necessarily equal in size. The point at which a path connects to a dot is called a path end. The following restrictions apply: No path may cross another path. No dot may have more than three path ends joined to it. A path may connect a dot to itself as long as the above restrictions are not violated. The last person who is able to draw a path wins the game.

To clarify the rules, several board configurations are illustrated below.

In figure 2, the first player has drawn a path between two dots and placed a new dot on it, dividing it in two.  Now, two of the original dots each have one path end connected to them, while the new dot has two path ends connected to it.

Figure 2. The first player has taken a turn.

Figure 3. The second player has taken a turn.

In figure 3, the second player has taken a turn.  Now, the dot labeled "A" has three path ends joined to it, an no new paths can be drawn to or from that dot.

If figure 4, player 1 has connected the dot labeled "B" to itself.  Now that dot has three path ends joined to it and cannot take any more connections.

Figure 4.  Player 1 has connected a dot to itself.

Figure 5. The game has ended.

Figure 5 shows how the game ended.  The two dots labeled "C" and "D" each have only two path ends joined to them, but they cannot be connected to each other because a new path would have to cross other paths to make the connection.   All the other dots already have three path ends joined to them, so they cannot be used to make any additional moves.

Try the sprouts applet on the University of Utah Department of Mathematics Web site.

Questions:

Which player won the game illustrated above?

If n is the number of dots at the start of the game, what is the maximum number of moves that can occur?

Can a game end with fewer than the maximum number of moves?

Given n, how can we figure out who will win if the maximum number of moves occurred?

What can you do to try to win the game?