• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

On the Sprague-Grundyfunction of Exact k- Nim

Discrete Applied Mathematics. 2018. Vol. 239. P. 1-14.
Gurvich V., Boros E., Kazuhisa M., Mursic P., Nhan Bao H.

Moore's generalization of the game of Nim is played as follows. Given two integer parameters $n, k$ such that $1 \leq k \leq n$, and $n$ piles of tokens. Two players take turns. By one move a player reduces at least one and at most $k$ piles. The player who makes the last move wins. The P-positions of this game were characterized by Moore in 1910 and an explicit formula for its Sprague-Grundy function was given by Jenkyns and Mayberry in 1980, for the case $n = k+1$ only. We modify Moore's game and introduce Exact $k$-Nim in which each move reduces exactly $k$ piles. We give a simple polynomial algorithm computing the Sprague-Grundy function of Exact $k$-Nim in case $2k > n$ and an explicit formula for it in case $2k = n$. The last case shows a surprising similarity to Jenkyns and Mayberry's solution even though the meaning of some of the expressions are quite different. On the Sprague-Grundy function of Exact $k$-Nim. Available from: https://www.researchgate.net/publication/281144667_On_the_Sprague-Grundy_function_of_Exact_k-Nim [accessed Oct 26 2017].