Skip to main content
2 of 2
edited tags
YCor
  • 63.9k
  • 5
  • 187
  • 286

Name of a game : Remove two chips from a vertex or one chip from both ends of an edge

Consider a finite graph $\Gamma$ with a positive number $n_v\geq 0$ of chips stacked at each vertex $v$ of $\Gamma$. Two players play in turn with moves consisting either of removing two chips from a unique vertex $v$ such that $n_v\geq 2$ or of removing one chip from both endpoints $v,w$ of an edge $\{v,w\}$ such that $n_v,n_w\geq 1$. The first player with no move left loses (or wins when using the misere convention).

The game is trivial on complete graphs. Winning positions have a nice (not completely trivial) description on the graph $P_3$ (Dynkin graph of type $A_3$) with vertices $1,2,3$ and edges $\{1,2\},\{2,3\}$: Given a position with $(a,b,c)$ chips on vertices $1,2,3$, the existence of a winning strategy for the first player and $a+b+c$ even (the case $a+b+c$ odd is trivial) depends on parities of $a,b,c$ and "coarsened" inequalities (coarsened in order to deal with two numbers of different parities) along edges after taking care of "fattened" boundaries.

A similar phenomenon seems to hold for the $P_4$ graph and perhaps for all trees.

Has somebody a reference/name for this game?

Roland Bacher
  • 17.9k
  • 3
  • 45
  • 113