Proof That Brussels Sprouts Game Ends in 5n - 2 Moves

Date: 04/15/2005 at 11:54:08
From: Asela
Subject: prove of brussels sprouts ends in 5n-2 steps

I need to know how I can prove that Brussels Sprouts is a joke because 
the game always ends in 5n - 2 movements.

Every time I make a new arc, I have two new possibilities or only one, 
but I have to prove that always finishes because there are more 
vertices with 1 possibility than vertices with 2.

Date: 04/16/2005 at 05:58:05
From: Doctor Jacques
Subject: Re: prove of brussels sprouts ends in 5n-2 steps

Hi Asela,

I assume you are referring to this game:

  Mathematical Games:  Brussels Sprouts 
    http://www.madras.fife.sch.uk/maths/games/brusselsprouts.html 

This is a very interesting question.  The game is described in the 
book "Winning ways for your mathematical games" (Berlekamp, Conway, 
and Guy), in which the authors write:

"After playing a few games of Brussels Sprouts, the skillful reader 
will be able to suggest a good starting strategy".

This is indeed a joke, since, as we will see, the outcome of the game 
only depends on the initial number of crosses, no matter which 
strategy you use.  Unfortunately, although they give the "5n - 2" 
formula at the end of the chapter, they do not explain where it comes 
from.

I will give you some hints on the general proof--you will have to fill 
in some steps by yourself.

Let us introduce some terminology.

* A vertex is a cross, whether or not this cross is connected to any
  other cross (or itself).

* An edge is a line between two vertices.

* A face is a closed region of the plane, delimited by edges; we also
  consider the outer region as a face.  In the starting position,
  there is only one face (the whole plane).

* A life is a branch of a cross that is not connected to any other
  cross.

* A connected component is a set of vertices and edges such that
  there is a path (a sequence of edges) between any two vertices.

Note that we can have vertices with only two adjacent edges.  In the 
following position:

  +----+-----+

we have three vertices and two edges.

I assume you know about Euler's formula: in any planar graph, we have:

  F - E + V = C + 1              [1]

where F is the number of faces, E is the number of edges, V is the 
number of vertices, and C is the number of connected components.  This 
formula is valid for any planar graph--it is not specific to the game 
of Brussels Sprouts.  The formula can easily be proved by induction 
(write back if you want to discuss this further).

Let us first make some observations which are valid for the whole o
curse of the game.

Fact 1
------
Each move consists in drawing an edge and adding a vertex on that 
edge, which effectively cuts the new edge in two.  This means that 
each move creates two edges and one vertex.  In particular, the number 
of edges after m moves is:

  E(m) = 2m                      [2]

and the number of vertices is:

  V(m) = n + m                   [3]

where n is the number of initial crosses.

In particular, we always have:

  E = 2V - 2n                    [4]

Fact 2
------
Any face has at least one life inside it.  Indeed, a new face is 
created when a new line separates an existing face into two parts, and 
the new cross drawn on that line has a life in each of the two faces.

Fact 3
------
The total number of lives is constant (and equal to 4n, its initial 
value).  Indeed, each move uses two lives and creates two new ones.  
Let us write L = 4n for that number.

We can already draw some conclusions.  Fact 2 implies that F <= L = 
4n.  Using [1] and [4], we find:

  C + 1 = F - E + V
        <= 4n - 2V + 2n + V = 6n - V

  V <= 6n - C - 1 <= 6n - 2

since C >= 1.

Using [3], we find that, afer m moves, we have:

  m + n <= 6n - 2
  m <= 5n - 2                     [5]

which means that the game cannot last longer than 5n - 2 moves; in 
particular, the game cannot last forever.

We want to show that the game always lasts for exactly 5n - 2 moves, 
i.e., we must convert [5] into an equality.

To do that, let us now make a few observations on the final position 
(this is legal, since we showed that the game always ends).

Fact 4
------
In the final position, C = 1.  Assume that there is more than one 
connected component.  If we consider each of these components, its 
outer region has at least one free life (fact 2).  Since the outer 
region of all connected components is the same, we can draw another 
line between these lives, and this contradicts the fact that this is 
the final position.

Fact 5
------
In the final position, each region contains exactly one active life. 
Indeed, we showed (fact 2) that each region contains at least one 
life.  If a region contains two lives, there is nothing to prevent us 
from connecting these lives together, and, once again, this 
contradicts the fact that we are at the end of the game.  This means 
that, in the final position, F = L = 4n.

Now, in deriving [5], we used inequalities in two places: we used the 
fact that F <= L = 4n, and the fact that C >= 1.  Facts 4 and 5 show 
that, in the final position, these inequalities become equalities, and 
we can repeat the argument to show that, at the end of the game, we 
have m = 5n - 2, which is what we wanted to show.

As the outcome of the game only depends on the number of moves played 
(the first player wins if that number is odd), this means that, if n 
is odd, the first player always wins (irrespective of the moves he 
chooses), and the second player wins if n is even.

In some sense, the strategy suggested by the authors of the book could 
be:

* If n is odd, try to raise the stakes.
* If n is even, go play some other game. :)

Does this help?  Write back if you'd like to talk about this some 
more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/