Number of Moves
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.
Read more about this topic: Sprouts (game)
Famous quotes containing the words number of, number and/or moves:
“He is the richest man who knows how to draw a benefit from the labors of the greatest number of men, of men in distant countries, and in past times.”
—Ralph Waldo Emerson (1803–1882)
“... in every State there are more women who can read and write than the whole number of illiterate male voters; more white women who can read and write than all Negro voters; more American women who can read and write than all foreign voters.”
—National Woman Suffrage Association. As quoted in History of Woman Suffrage, vol. 4, ch. 13, by Susan B. Anthony and Ida Husted Harper (1902)
“They wait, each like a wooden decoy
or soft like a pigeon or
a sweet snug duck:
until one moves, moves that dart-beak
breaking over.”
—Anne Sexton (1928–1974)