Photo:
THE MIRROR
The rules are simple: there are n dots on a sheet of paper.
Two players take turns connecting them with lines.
The lines must not cross.
And there is always a new point added with every move.
»Sprouts« is the name of the game that the mathematician John Conway and the computer scientist Michael Paterson came up with at the beginning of 1967.
The puzzle collector Martin Gardner soon became aware of this and introduced »Sprouts to a larger audience with his column in »Scientific American«.
In a simple variant you start the game with only two points - see drawing below.
A move consists of either connecting a point to itself (A) - or connecting two points to each other (B).
In both cases,
a new point is placed in the middle of the newly drawn connection
, which is highlighted in blue in the drawing.
The two players take turns adding a new line each time.
Lines must
not cross
each other .
And very important: no more
than three lines
may start from one point .
The winner is whoever can draw a line last.
Apparently a round of »Sprouts« doesn't last forever.
Otherwise there would be no winner.
The question is: what is the maximum number of moves in an n-point game?
A round of Sprouts with n points is over after at most
3n-1 moves
.
At first glance, the game appears confusing: a new point is added with each move.
The specific lines should also influence how quickly a game is over.
However, the solution is amazingly simple: a maximum of three lines can start from one point.
If the number of three lines is reached, the point is dead - it can no longer be used in the game.
The maximum number of moves is reached when as many n points as possible are dead, because three lines start there.
There is not a single line before the first turn.
Three lines could start at each point of the n points - that's a total of 3n outgoing lines.
In a move, the number of possible outgoing lines decreases by 2, because a line is drawn connecting two points or one point to itself.
However, a new point is also added with a move.
This is in the middle of the new line - so only one new line can branch off from it.
Therefore, the number of possible lines leaving points decreases by 2-1 = 1 per move.
At the start there are 3n possible line beginnings.
After 3n-1 moves there can be at most one single point from which a line can start.
Then no further move is possible.
So the game ends after
at most 3n-1 moves
.
In fact, it can also end earlier, because two points that each have at most two lines going off cannot be connected to each other.
This happens when one or both points are completely enclosed by lines and the other point is outside.
But who can win at »Sprouts« – player 1 or player 2?
Is there a general strategy?
Mathematicians have examined »Sprouts« in detail – also with the help of computers.
So player 2 can always win for 1, 2, 6, 7, 8 and 12 starting points.
Player 1, on the other hand, has a safe chance of winning with 3, 4, 5, 9, 10 and 11 starting points.
The guess is that the remainder left by the starting score when divided by 6 will decide who can win the game.
With a remainder of 3, 4 or 5, player 1 has a winning strategy.
In the other cases, player 2 can win.
Mathematicians have apparently not yet found proof of this.
There are only computer analyzes that confirm the conjecture for all numbers up to 44, as well as for n = 46, n = 47 and n = 53. The simple pen and paper game of Conway and Paterson is not so simple after all.
In case you missed a mystery from the past few weeks, here are the most recent episodes:
The split cube
The missing tile
A bridge, four people and a flashlight
All A's
A card makes the difference
The domino duel
Fairness at the coffee table
Magical 45
Perfectly arranged
Can these calculations add up?
