On the Sprague-Grundy function of compound games

Abstract

The classical game of {\sc Nim} can be naturally extended and played on an arbitrary hypergraph $\cH \subseteq 2^V \setminus \{\emptyset\}$ whose vertices $V=\{1,\dots ,n\}$ correspond to piles of stones. By one move a player chooses an edge $H$ of $\cH$ and reduces arbitrarily all piles $i\in H$. In 1901 Bouton solved the classical {\sc Nim} for which $\cH = \{\{1\}, \ldots, \{n\}\}$. In 1910 Moore introduced and solved a more general game $k$-{\sc Nim}, for which $\cH = \{H \subseteq V \mid |H| \leq k\}$, where $1\le k<n$. In 1980 Jenkyns and Mayberry obtained an explicit formula for the Sprague-Grundy function of Moore's {\sc Nim} for the case $k+1=n$. Recently it was shown that the same formula works for a large class of hypergraphs. In this paper we study combinatorial properties of these hypergraphs and obtain explicit formulas for the Sprague-Grundy functions of the conjunctive and selective compounds of the corresponding hypergraph {\sc Nim} games.

20 pages, 1 figure