Sprouts game
Sprouts is a pencil-and-paper game with interesting mathematical properties.It was invented by mathematicians John Conway and Michael S. Paterson at Cambridge University in 1967.
The game is played by two players, starting with a few dots (called spots) drawn on a sheet of paper. To make a move, a player draws a curve between two spots or a loop from a spot to itself. The curve may not cross any other curve. The player makes a new spot on the curve, dividing it in two. Each spot can have at most three curves connected to it. The player who makes the last move wins.
Sprouts has been studied from the perspectives of graph theory and topology.
It can be proven that a game started with n spots will last at least 2n moves and at most 3n - 1 moves.
By enumerating all possible moves, one can show that the first player is guaranteed a win in games involving three,
four, or five spots.
The second player can always win a game started with one, two, or six spots.
At Bell Labs in 1990, David Applegate, Guy Jacobson, and Daniel Sleator used a lot of computer power to push the analysis out to eleven spots. They conjectured that the first player has a winning strategy when the number of spots divided by six leaves a remainder of three, four, or five.
The game of sprouts played an important role in the first part of the Piers Anthony book Macroscope.
