Editing Sprouts (game) (section)

==Number of moves==
The game of Sprouts always terminates, although this fact is not evident from the game rules, since the number of spots increases at each move.  The approach to understand why the game always terminates is to consider the number of ''lives'' (opportunities to connect a line) instead of the number of spots. Then, it can be shown that if the game starts with ''n'' spots, it will end in no more than 3''n''&nbsp;−&thinsp;1 moves and no fewer than 2''n'' moves.

In the following [[mathematical proof|proofs]], it is assumed that a game starts with ''n'' spots and lasts for exactly ''m'' moves.

===Maximum number of moves===
[[File:Sprouts-max-moves.png|thumb|300px|A game of sprouts with ''n'' initial spots (in blue) that ends in 3''n''&nbsp;−&thinsp;1 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 {{nowrap|3''n'' − ''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 {{nowrap|3''n'' − ''m''}} survivors. There must be at least one survivor, namely the spot added in the final move. So {{nowrap|3''n'' − ''m'' ≥ 1}}; hence a game can last no more than 3''n''&nbsp;−&thinsp;1 moves.

This upper bound is actually the maximum, and it can be attained in many ways by ensuring that there is only one survivor at the end of the game. For instance, the game on the right has one survivor and 3''n''&nbsp;−&thinsp;1 moves.

[[File:Sprouts-analysis.png|right|framed|Live spots (green) and their dead neighbors (black)]]

===Minimum number of moves===
At the end of the game, a dead spot is called the ''neighbor''  of a survivor if it is either adjacent to that survivor or, if the survivor has a loop, it is adjacent to a spot adjacent to the survivor. This is illustrated in the diagram to the right.  Each survivor has exactly two dead neighbors. 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 language|Hebrew]] for "[[Pharisees|separated ones]]"). Suppose there are ''p'' pharisees. Then

:<math>n + m = 3n - m + 2(3n - m) + p</math>

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

:<math> m = 2n + p/4</math>

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

[[File:Game of sprouts with n initial vertices, ending in minimum number of moves.png|thumb|300px|A game of sprouts with ''n'' initial spots that ends in 2''n'' moves]]
This lower bound on the length of a game is actually the minimum. The diagram on the right shows a completed game of 2''n'' moves. It has ''n'' survivors, 2''n'' neighbors and 0 pharisees.

===Importance in real games===
Real games seem to turn into a battle over whether the number of moves will be ''k'' or ''k''&nbsp;+&thinsp;1 with other possibilities being quite unlikely.<ref>{{cite web |url=http://mathforum.org/kb/message.jspa?messageID=1091005&tstart=0 |title=Math Forum Discussions |publisher=Mathforum.org |access-date=2012-09-26 |archive-date=2012-03-16 |archive-url=https://web.archive.org/web/20120316135329/http://mathforum.org/kb/message.jspa?messageID=1091005&tstart=0 |url-status=dead }}</ref> 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).