A variant of the game, called Brussels Sprouts, starts with a number of crosses, i.e. spots with four free ends. Each move involves joining two free ends with a curve (again not crossing any existing line) and then putting a short stroke across the line to create two new free ends.
So each move removes two free ends and introduces two more. Despite this, the game is finite, and indeed the total number of moves is predetermined by the initial number of crosses: the players cannot affect the result by their play. With n initial crosses, the number of moves will be 5n−2, so a game starting with an odd number of crosses will be a first player win, while a game starting with an even number will be a second player win regardless of the moves.
To prove this (assuming that the game ends), 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 2 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-e+v = 4n-2m+n+m = 5n-m, hence m = 5n-2.
Read more about this topic: Sprouts (game)
Famous quotes containing the word sprouts:
“The partridge and the rabbit are still sure to thrive, like true natives of the soil, whatever revolutions occur. If the forest is cut off, the sprouts and bushes which spring up afford them concealment, and they become more numerous than ever. That must be a poor country indeed that does not support a hare. Our woods teem with them both.”
—Henry David Thoreau (1817–1862)