Research in Scientific Computing in Undergraduate Education

Sprouts

Sprouts is a two-person game invented by mathematicians John Horton Conway and Michael S. Paterson at Cambridge University in 1967.

The game begins with a number of spots:

Players take turns drawing a line -straight or curved – between existing spots, and adding a new spot in the middle of the new line:

The rules are:

• Lines must not touch or cross any line except at a designated spot.
• No spot may have more than three lines attached to it. A line from a spot to itself counts as two attached lines and new spots are counted as having two lines already attached to them.
• The player who makes the last move wins.

The problem, for a given number of spots is to determine when the first player has a winning strategy, and when the second player has a winning strategy.

It is conjectured that that the first player has a winning strategy when the number of spots is congruent to 3, 4, or 5, modulo 6.

The complexity of analysis grows very rapidly with the initial number of spots.

The misère form of the game is when the last player to move loses.

References and readings

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: