Brussels Sprouts

Brussels sprouts is a two-player impartial game played with nonintersecting curves in the plane. Play starts with disjoint crosses, each having four free arms. A move joins two free arms by a curve and places a transverse stroke across that curve, creating two new free arms. The joining curve must not cross itself or the existing drawing. In the normal-form game, the player making the last legal move wins (Gardner 1967).

Every completed game has exactly moves, regardless of the choices made (Cairns and Chartarrayawadee 2007). To see this, regard the centers of crosses and the added strokes as vertices, omit the free arms, and regard each joining curve as two edges. After moves, this planar graph has vertices and edges. The number of free arms stays . Every boundary component of each graph face has a free arm. This holds initially, and a move either merges two boundary components or splits one into two, with the new free arms preserving the property. In a completed game each graph face has exactly one free arm, since two could still be joined. The resulting planar graph must be a connected graph, since different connected components would border a common graph face with at least two free arms. The Euler characteristic relation therefore gives

so . Consequently the first player wins when is an odd number, and the second player wins when is an even number.