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  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  and the number of vertices is: V(m) = n + m  where n is the number of initial crosses. In particular, we always have: E = 2V - 2n  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  and , we find: C + 1 = F - E + V <= 4n - 2V + 2n + V = 6n - V V <= 6n - C - 1 <= 6n - 2 since C >= 1. Using , we find that, afer m moves, we have: m + n <= 6n - 2 m <= 5n - 2  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  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 , 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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.