Sprouts is a pencil-and-paper game with interesting mathematical properties. Paper and pencil games are Games that can be played solely with Paper and Pencil. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and It was invented by mathematicians John Horton Conway and Michael S. A mathematician is a person whose primary area of study and research is the field of Mathematics. John Horton Conway (born December 26, 1937, Liverpool, England) is a prolific mathematician active in the theory of finite groups Paterson at Cambridge University in 1967. The University of Cambridge (often Cambridge University) located in Cambridge, England, is the second-oldest university in the Year 1967 ( MCMLXVII) was a Common year starting on Sunday (link will display full calendar of the 1967 Gregorian calendar.

A 2-spot game of Sprouts

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.

• The line may be straight or curved, but must not touch or cross itself or any other line.
• The new spot cannot be placed on top of one of the endpoints of the new line. Thus the new spot splits the line into two shorter lines.
• No spot may have more than three lines attached to it. For the purposes of this rule, a line from the spot to itself counts as two attached lines and new spots are counted as having two lines already attached to them.

In so-called normal play, the player who makes the last move wins. Misere or Misère (from the French word meaning "poverty" is a bid in various Card games particularly the game 500. In misère play, the player who makes the last move loses. Misere or Misère (from the French word meaning "poverty" is a bid in various Card games particularly the game 500. (Misère Sprouts is perhaps the only misère combinatorial game that is played competitively in an organized forum. [1], p. 21)

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.

Analysis

Suppose that a game starts with n spots and lasts for exactly m moves.

Each spot starts with three lives (opportunities to connect a line) 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.

Live spots (green) and their dead neighbors (black).

At the end of the game each survivor has exactly two dead neighbors, in a technical sense of "neighbor"; see the diagram on the right. No dead spot can be the neighbor of two different survivors, for otherwise there would be a move joining the survivors. All other dead spots (not neighbors of a survivor) are called pharisees (from the Hebrew for "separated ones"). The word Pharisees ( lat. pharisæ|us, - i) comes from the Hebrew פרושים perushim from פרוש parush, meaning "separated" Suppose there are p pharisees. Then

n+m = 3n−m + 2(3n−m) + p

since initial spots + moves = total spots at end of game = survivors + neighbors + pharisees. Rearranging gives:

m = 2n + p/4

So a game lasts for at least 2n moves, and the number of pharisees is divisible by 4.

Real games seem to turn into a battle over whether the number of moves will be m or m+1 with other possibilities being quite unlikely. One player tries to create enclosed regions containing survivors (thus reducing the total number of moves that will be played) and the other tries to create pharisees (thus increasing the number of moves that will be played).

Who has the win?

By enumerating all possible moves, one can show that the first player can always win in normal-play games starting with n = 3, 4, or 5 spots. The second player wins when n = 0, 1, 2, or 6.

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 in normal play and nine spots in misère play. Bell Laboratories (also known as Bell Labs and formerly known as AT&T Bell Laboratories and Bell Telephone Laboratories) is the Research organization Year 1990 ( MCMXC) was a Common year starting on Monday (link displays the 1990 Gregorian calendar) Daniel Dominic Kaplan Sleator is a professor of Computer science at Carnegie Mellon University. A computer is a Machine that manipulates data according to a list of instructions. Josh Purinton and Roman Khorkov have extended this analysis to fifteen spots in misère play. [2] Julien Lemoine and Simon Viennot have calculated normal play outcomes up to thirty-two spots, plus five more games between thirty-four and forty-seven spots. [3]

The normal-play results are all consistent with the pattern observed by Applegate et al. up to eleven spots and conjectured to continue indefinitely, 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 results for misère play do not follow as simple a pattern: up to fifteen spots, the first player wins in misère Sprouts when the remainder is zero or five, or when the number of spots is one or ten.

A 2-cross game of Brussels Sprouts lasting eight moves

Brussels Sprouts

A variant of the game, called Brussels Sprouts, starts with a number of crosses, i. e. spots with four free ends. Each move involves joining two free ends with a curve (again not crossing any existing line) and then putting a short stroke across the line to create two new free ends.

So each move removes two free ends and introduces two more. Despite this, the game is finite, and indeed the total number of moves is predetermined by the initial number of crosses: the players cannot affect the result by their play. With n initial crosses, the number of moves will be 5n−2, so a game starting with an odd number of crosses will be a first player win, while a game starting with an even number will be a second player win regardless of the moves.

References

• Elwyn R. Berlekamp, John Conway and Richard K. Guy, Winning Ways for your Mathematical Plays, 1992. Elwyn Ralph Berlekamp (born September 6, 1940 in Dover, Ohio, United States of America) is a professor emeritus of Mathematics John Horton Conway (born December 26, 1937, Liverpool, England) is a prolific mathematician active in the theory of finite groups Richard Kenneth Guy (born 1916 Nuneaton, Warwickshire) is a British mathematician Professor Emeritus in the Department of Mathematics Winning Ways for your Mathematical Plays (Academic Press 1982 by Elwyn R Year 1992 ( MCMXCII) was a Leap year starting on Wednesday (link will display full 1992 Gregorian calendar)
• Madras College Mathematics Department, "Mathematical Games: Sprouts."
• Ivars Peterson, "Sprouts for Spring," Science News Online.
• Danny Purvis, World Game of Sprouts Association.
• Sprouts played an important role in the first part of Piers Anthony's novel Macroscope. Piers Anthony Dillingham Jacob (born August 6, 1934 in Oxford England) is an English American writer in the Science fiction Macroscope is a novel by Science fiction and Fantasy writer Piers Anthony.
• The Game of Sprouts at University of Utah (with an interactive applet for human-vs-human play). The University of Utah (referred to locally as ' The U' or ' the U of U') is a publicly funded Research university in Salt Lake
• Riccardo Focardi and Flamina Luccio, A new analysis technique for the Sprouts Game, 2001
• David Applegate, Guy Jacobson, and Daniel Sleator, Computer Analysis of Sprouts, 1991