Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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. :)

more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Discrete Math
High School Discrete Mathematics

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search