A little mouse called Delia lives in a hole in the bottom of a
tree.....How many days will it be before Delia has to take the same
Given the nets of 4 cubes with the faces coloured in 4 colours, build a tower so that on each vertical wall no colour is repeated, that is all 4 colours appear.
A connected graph is a graph in which we can get from any vertex to
any other by travelling along the edges. A tree is a connected
graph with no closed circuits (or loops. Prove that every tree has
exactly one more vertex than it has edges.
Published December 2004,July 2004,August 2004,December 2011,February 2011.
The game of Sprouts was invented in 1967 by two mathematicians
John H. Conway and Michael S. Paterson, when they were both at the
University of Cambridge in the UK. The game was popularised by one
of Martin Gardner's "Mathematical Games" columns in Scientific
American. Here is a quote from Conway:
"The day after sprouts sprouted, it seemed that everyone was
playing it, at coffee or tea times, there were little groups of
people peering over ridiculous to fantastic sprout
Sprouts is a game for two players. All you really need is paper
and a pencil.. The game starts by drawing any number of spots. In
this example we are going to look at 3 spots.
The first player has a turn by joining two of the spots and
marking a new spot in the middle of the line. Or the line may start
and end on the same spot.
You are not allowed to draw a line which crosses another line.
This is important to remember!
A spot cannot have more than three lines leading to or from it.
For example, in the game below, spots A and B cannot be used any
more because they already have three lines.
The idea is to make it impossible for the other player to draw a
So the last person to draw a line is the winner.
Find a friend to play the game with. We suggest that you limit
the number of spots to 3. Try playing several games to get the hang
of it. Here are a few questions to focus your mind, but don?t try
to answer them until you have played the game a few times, and feel
confident with the rules.
Does the person who goes first or second tend to win?
Can you explain any winning tactics?
The game must end after a limited number of moves. Explain why.
(Hint: you might find it useful to explain this in terms of
"liberties". The liberties of a spot equals 3 minus the number of
lines drawn from that spot.)
How did you explain the winning tactics? In discussing this
game, several enthusists have found it helpful to adopt a form of
notation to communicate their ideas and strategies. We often use
notation to explain our ideas in mathematics, and you might find it
interesting to learn a little about Conway notation, the official
notation of the WGOSA (The World Game of Sprouts Association). It
began to evolve in 1999 in a discussion in www.mathforum.com. For a full
discussion on the notation see http://www.geocities.com/chessdp/notation.htm.
The strategy becomes more complex as you increase the number of
spots, although WGOSA suggests that live spots at the end of the
game are the key to making the game fun to play. (A "live" spot is
a spot that is not "dead". A "dead" spot has 3 lines attached to it
and is therefore out of the game.) These live spots at game's end
are called "survivors".
Suppose a normal sprouts game begins with an even number of
spots. Which player is likely to win and what can you say about the
number of survivors (1)? If the game started with an odd number of
spots what would you expect to happen and what could you say about
the number of survivors (2)?
There is quite a lot of nice mathematics that can be gleaned
from the game. What follows is a look at a few proofs. Stephan
Duerr has summarised some of these, and added his own at the web
site given below.
Enthusiasts have come up with a terminology that is useful to
the proofs. These are all given below:
The "liberties" of a spot equal three minus the number of lines
emerging from the spot.
A spot is "dead" if it has no liberties.
A "survivor" is a live spot at game's end.
A "guard" is a dead spot that is one of the two nearest
neighbours of a survivor (see more details below).
A "pharisee" is a dead spot that is not a guard.
A "region" is an area of white space on the paper bounded by
lines. The region extending off to the horizon is called "outer
region", all other regions are "inner regions". At game's start,
there is one region.
A "cluster" (or "clump") consists of all spots that are directly
or indirectly connected by lines. An "indirect" connection means
that there are other spots along the connection. The smallest
possible cluster consists of just one unattached spot. At the
beginning of a game with n spots there are n clusters.
The lines emerging from a spot divide the area around the spot
into "sites". Spots have as many sites as lines, except for no
lines, where there is one site.
$n=$ number of spots at the beginning of the game
$d=$ number of dead spots
$m=$ number of moves
$s=$ number of survivors
$p=$ number of pharisees
$c=$ number of clusters
$r=$ number of regions
$L=$ number of liberties
All of these proofs have been taken from work by contributors to
the maths forum.
Each spot has $3$ liberties at the beginning of the game. There
are $n$ spots. Hence at the beginning of the game there are $3n$
Each move reduces the number of liberties by $1$. This is
because the two spots that are joined result in $2$ liberties being
lost, whilst the spot that is added results in $1$ liberty being
At the game's end, each survivor has exactly $1$ liberty
(otherwise you could connect the survivor to itself), hence
$s\geq 1$ hence $3n-m\geq 1$.
Rearranging this gives $3n-1\geq m$ or $m\leq 3n-1$.
At the end of a game, each survivor is surrounded by $2$
These guards are spots that are dead in one of two ways:
If any guard were live, the game could be continued by
connecting the guard to the survivor. Each guard has at least two
of its sites accessing a region that is also accessible to the
survivor. Since no two survivors can access the same region
(otherwise we could connect the survivors), no spot can be a guard
for two different survivors.
A pharisee is a dead spot that is not a guard.
The number of pharisees is the total number of spots minus the
number of survivors and minus the number of guards. Written
$$p=n+m-s-2s$$ $$p=n+m-3s$$ $$p=n+m-3(3n-m)$$
Rearranging this equation gives us $m=p/4 + 2n$.
If the game is played so that there are no Pharisees, that is a
game is played with the minimum number of moves, then $m=2n$.
So we can say that $m\geq 2n$.
There are exactly two types of moves in sprouts. One type merges
two clusters, the other type creates a new region.
Because the number of regions either increases by $1$ or the
number of clusters decreases by $1$, we can deduce that each move
increases $r-c$ by $1$, or that $r-c-m$ must be constant throughout
At the beginning of a game, $r=1$, $c=n$ and $m=0$.
From this we can deduce that $r-c-m=1-n-0$ which can be
rearranged to give: $$r=1-n+c+m$$
At the end of the game, as we have already seen, $s=3n-m$, or
Substituting this equation into the above we have:
$$r=1-n+c+3n-s$$ which simplifies to: $$r=2n+1+c-s$$ Every cluster
must contain at least one live spot, namely the spot of the cluster
that was last to be placed on the paper. From this we can say
As $c\leq s$, then $c-s\leq 0$. We can substitute this into
$r=2n+1+c-s$ to give: $$r\leq 2n+1$$.
These and further proofs can be found at
Sprouts is an intriguing game which contains some interesting
mathematics. Have fun with the game, and may sprouts continue
WGOSA (The World Game of Sprouts Association) -http://www.geocities.com/chessdp/
The first player will win if there is an odd number of
The first player will win if there is an even number of