On the Sprague-Grundy Function of Tetris Extensions of Proper {\sc Nim}

Abstract

Given a hypergraph $\cH \subseteq 2^I \setminus \{\emptyset\}$ on the ground set $I=\{1,\dots ,n\}$, we assign to each $i\in I$ a nonnegative integer $x_i$, that is a pile of $x_i$ tokens, and consider the following generalization of the classical game of {\sc Nim}: Two players alternate turns. In a move a player chooses an arbitrary edge $H \in \cH$ and reduces all piles $i\in H$. The player who is out of moves loses. We call the obtained game hypergraph {\sc Nim}. Such a game is called proper {\sc Nim}, when $\cH=2^I \setminus\{I,\emptyset\}$ is the family of all proper subsets of $I$. Jenkyns and Mayberry \cite{JM80} described the Sprague-Grundy (or SG in short) function of these games. In this paper we introduce Tetris extensions of hypergraph {\sc Nim}, and obtain a closed formula for the SG functions of the extensions of proper {\sc Nim}, when $n\ge 3$. Surprisingly, the case of $n=2$ is much more complicated. For this case we only suggest several partial results and conjectures.