On the Sprague-Grundy function of \textsc{Exact} k-\textsc{Nim}

DOI10.1016/J.DAM.2017.08.007MaRDI QIDQ1706111zbMATH OpenOpenAlexFDO

Authors Endre Boros, Nhan Bao Ho, Kazuhisa Makino, Peter Mursic, Vladimir Gurvich

Publication date 21 March 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.04484

zbMATH Keywords

\(\mathcal P\)-position\textsc{Exact} \textsc{Nim}impartial gamesMoore's \textsc{Nim}Sprague-Grundy function

Mathematics Subject Classification ID

Combinatorial games (91A46)

Abstract: Moore's generalization of the game of {sc Nim} is played as follows. Let $n$ and $k$ be two integers such that $1leqkleqn$. Given $n$ piles of tokens, two players move alternately, removing tokens from at least one and at most $k$ of the piles. The player who makes the last move wins. The game was solved 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 introduce another generalization of {sc Nim}, called {sc Exact $k$-Nim}, in which each move reduces exactly $k$ piles. We give an explicit formula for the Sprague-Grundy function of {sc Exact $k$-Nim} in case $2kgeqn$. In case $n=2k$ our formula is surprisingly similar to Jenkyns and Mayberry's one.

Recommendations

• More about Exact Slow $k$-Nim
• Slow \(K\)-\textsc{Nim}
• Nimhoff games
• On the Sprague-Grundy function of extensions of proper \textsc{nim}
• Sprague-Grundy function of symmetric hypergraphs

Cites work

• scientific article; zbMATH DE number 3159208 (Why is no real title available?)
• scientific article; zbMATH DE number 3521877 (Why is no real title available?)
• scientific article; zbMATH DE number 3027208 (Why is no real title available?)
• The skeleton of an impartial game and the nim-function of Moore's \(\text{Nim}_2\)
• Winning ways for your mathematical plays. Vol. 1.

Cited in

(11)

• On tame, pet, domestic, and miserable impartial games
• On the Sprague-Grundy function of extensions of proper \textsc{nim}
• Bachet's game with lottery moves
• Sprague-Grundy function of matroids and related hypergraphs
• Sprague-Grundy function of symmetric hypergraphs
• More about Exact Slow $k$-Nim
• Computational Hardness of Multidimensional Subtraction Games
• Slow \(K\)-\textsc{Nim}
• On the Sprague-Grundy function of compound games
• Computing remoteness functions of Moore, Wythoff, and Euclid's games
• Impartial games with decreasing Sprague-Grundy function and their hypergraph compound

This page was built for publication: On the Sprague-Grundy function of \textsc{Exact} \(k\)-\textsc{Nim}

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1706111)