The game of Brussels Sprouts

Question

I read once about a variant of the game Sprouts called Brussels Sprouts. Instead of placing dots on a plane, one places $n$ $+$ signs instead. Each player, in turn, connects any two free legs, either on the same $+$ sign or on different signs, but moves that would cross a pre-existing line (or $+$ sign) are not permitted. A new hash mark is drawn normal to the newly drawn line, providing two new free legs. The game ends when a player cannot move -- the other player is then declared the winner.

The name is a deliberate joke. That's because, according to the article I read, no matter what moves are made, each game will always have exactly $5n-2$ moves. I have no idea how to prove this but it seems to be correct for the examples I checked.

Does anyone know how to prove this claim?

Answer 1

As mentioned in the comments by David, the proof for this particular problem can be found on the Wikipedia page for the game Sprouts. For completeness, I have included their proof below:

Let $m$ denote the number of moves and $v$, $e$, $f$ denote the number of vertices, edges, and faces of the planar graph obtained at the end of the game, respectively. We have:

• $e = 2m$ since at each move, the player adds two edges.
• $v = n + m$ since at each move, the player adds one vertex and the game starts with $n$ vertices.
• $f = 4n$ since there is exactly one free end in each face at the end of the game, and the number of free ends does not change during the game.

The Euler characteristic for planar graphs is $2$, so: $$ 2 = f+v-e = 5n - m \space \iff m = 5n - 2$$

Thus, proving the hypothesis.