Sprouts (game)

Sprouts is a paper-and-pencil game with significant mathematical properties. It was invented by mathematicians John Horton Conway and Michael S. Paterson at Cambridge University in the early 1960s.

The game is played by two players, starting with a few spots drawn on a sheet of paper. Players take turns, where each turn consists of drawing a line between two spots (or from a spot to itself) and adding a new spot somewhere along the line. The players are constrained by the following rules.

In so-called normal play, the player who makes the last move wins. In misère play, the player who makes the last move loses. (Misère Sprouts is perhaps the only misère combinatorial game that is played competitively in an organized forum.)

The diagram on the right shows a 2-spot game of normal-play Sprouts. After the fourth move, most of the spots are dead–they have three lines attached to them, so they cannot be used as endpoints for a new line. There are two spots (shown in green) that are still alive, having fewer than three lines attached. However, it is impossible to make another move, because a line from a live spot to itself would make four attachments, and a line from one live spot to the other would cross lines. Therefore, no fifth move is possible, and the first player loses. Live spots at the end of the game are called survivors and play a key role in the analysis of Sprouts.

It is not evident from the rules of Sprouts that the game always terminates, since the number of spots increase at each move. The correct approach is to consider the number of lives (opportunities to connect a line) instead of the number of spots. Then, we can show that if the game starts with n spots, it will end in no more than 3n−1 moves and no fewer than 2n moves.

In the following proofs, we suppose that a game starts with n spots and lasts for exactly m moves.

Each spot starts with three lives and each move reduces the total number of lives in the game by one (two lives are lost at the ends of the line, but the new spot has one life). So at the end of the game there are 3n−m remaining lives. Each surviving spot has only one life (otherwise there would be another move joining that spot to itself), so there are exactly 3n−m survivors. There must be at least one survivor, namely the spot added in the final move. So 3n−m ≥ 1; hence a game can last no more than 3n−1 moves.

...
Wikipedia