A very simple game which has its origins in the field of Discrete Mathematics is a game called Sprouts. You play Sprouts according to the following rules:

1. Begin with a given number of dots.
2. An arc can be drawn connecting any two dots.
3. An arc can be drawn connecting a dot to itself.
4. On each new arc, a new dot is placed at its midpoint.
5. No dot can have more than three arcs coming from it.
6. No arc can cross any other arc.
7. The winner is the player who makes the last valid move.

Start	1st Move	2nd Move	3rd Move	4th Move	5th move
	Player 1 connects point A to point B and puts in midpoint C.	Player 2 connects point B to point C and puts in midpoint D.	Player 1 connects point B to point D and puts in midpoint E.	Player 2 connects point A to itself and puts in midpoint F.	Player 1 wins by connecting point E to point F and putting in point G.

Player 2 can begin an arc at point G, but there is no point available for its other endpoint. Every dot, except G, already has 3 arcs joining it. The game ends with Player 1 the winner.

Replay the game starting with Player 1 connecting point A to itself.

• How many moves does the game have?
• Who wins?
• Can you see that there would be another (virtually identical) game if you begin by connecting point B to itself?

For every 2-dot game, three initial moves are possible. Try to play out all unique possible 2-dot games. Now, play a few games starting with 3 dots. How many initial moves are possible for a 3-dot games? For each game, count the number of moves it takes to determine a winner. Record who wins each game.

Do you understand the game well enough to analyze it? If so, complete the following table:

Having trouble? You might think about what happens as you add a dot (C) to the 2-dot game. Three initial possible moves are added, one which connects point C to itself and two additional moves each of which connects point C to one of the other two points.

When a fourth dot is added, again it can be connected to itself and also to the three pre-existing dots adding four more initial possible moves. When you add the nth dot, how many more initial possible moves are added?

This kind of thinking is called recursive thinking.

• We know the number of initial possible moves for a 1-dot game.
• As long as we know the number of initial possible moves for a k-dot game and we know how many more initial moves are added when one more dot is added, we can figure out the number of initial possible moves for any game which begins with more than k dots.

You may recognize the number of initial possible moves as the triangular numbers (see Hamberg, IMSAMJ, Fall 1992, page 7). The nth triangular number is usually represented by the expression n(n + 1)/2. Why would (n - 1)n/2 represent the (n-1)st triangular number?

A second way to obtain the same result is to immediately consider the n-dot game. For the n-dot game, each dot may initially be connected to itself (n initial possible moves), and one additional initial move is possible for each pair of dots which can be chosen from the set.

In mathematical notation this method of determining the number of initial possible moves can be represented as

To complete the original table, we need to find the maximum number of moves for a winner to be determined. Consider that when we begin with 2 dots, there are initially 6 arcs possible which will have one of the first two dots as an endpoint. (Remember, each dot may have at most 3 arcs coming from it.)

Consider what happens on the first move of the game:

• One dot is added, but it has two arcs already coming from it, so only one additional arc endpoint is added.
• Each of the two original dots loses one available arc.

There is a net loss of one arc from the initial 6. Since one arc is lost for each move, the maximum number of moves in a 2-dot game is 5. Now, you should be able to complete the original table.

What if the game is changed so that each arc may have at most 4 arcs coming from it? Does the number of initial moves change? Does the number of moves to determine a winner change?

What if the game is changed so that each dot may have at most 3 arcs coming from it, however, two new dots are placed on each new arc? Does the number of initial moves change? Does the number of moves to determine a winner change?

To be certain that you understand the game, determine in each of the following cases whether the game situation could occur. If it is not a possible scenario, explain why not.

A	B	C	D
E	F	G	H

Answers.

The following table summarizes results for games that start with two, three, four, and five dots and generalizes the number pattern for n dots.

Download this article | Report an error | Table of Contents | Back to IMSA Math