Skip to main content
2 of 4
deleted 1 character in body
HeinrichD
  • 5.5k
  • 22
  • 42

Combinatorial game similar to Sprouts

Is there a name for the following combinatorial game? Is there a solution which player has a winning strategy?

Basically this game is "non-planar sprouts without midpoints". One starts with $n$ points in space. Then a move consists of joining two points (it is also allowed to join a point with itself, i.e. to make loops). The degree of each point is supposed to be $\leq 3$. Thus, points of degree $3$ are "dead". The player with the last move wins.

The game can also be described via multisets of numbers $\leq 3$ (containing the point degrees), starting with $\{0,\dotsc,0\}$. Then it becomes a number-theoretic game. A move replaces some element $a$ by $a+2$ (if $a \leq 1$) or replaces two elements $a,b$ by $a+1,b+1$ (if $a,b \leq 2$). For $n=2$ the games are

$\begin{array}{c} \{0,0\} \to \{2,0\} \to \{3,1\} \to \{3,3\} \\\{0,0\} \to \{2,0\} \to \{2,2\} \to \{3,3\} \\ \{0,0\} \to \{1,1\} \to \{3,1\} \to \{3,3\} \\ \{0,0\} \to \{1,1\} \to \{2,2\} \to \{3,3\}\end{array}$

I have already determined some game outcomes, but wanted to know a reference. On the german Wikipedia it says that the sprouts variant where the players may decide if they add a midpoint is already solved (the first player wins) and "known" as black-and-white sprouts, but I could not find anything about this, and also this game has different game outcomes than the game described above.

HeinrichD
  • 5.5k
  • 22
  • 42