Three-pile Sharing Nim and the quadratic time winning strategy

DOI10.1016/J.TCS.2016.07.015MaRDI QIDQ306276zbMATH OpenOpenAlexFDO

Authors Nhan Bao Ho

Publication date 31 August 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial gamesperiodicityNimNim-sequencequadratic timeSharing Nim

Mathematics Subject Classification ID

Combinatorial games (91A46)

Abstract: We study a variant of 3-pile Nim in which a move consists of taking tokens from one pile and, instead of removing then, topping up on a smaller pile provided that the destination pile does not have more tokens then the source pile after the move. We discover a situation in which each column of two-dimensional array of Sprague-Grundy values is a palindrome. We establish a formula for P-positions by which winning moves can be computed in quadratic time. We prove a formula for positions whose Sprague-Grundy values are 1 and estimate the distribution of those positions whose nim-values are g. We discuss the periodicity of nim-sequences that seem to be bounded.

Recommendations

• Square, rectangular and triangular Nim games
• Amalgamation Nim
• On restricted Wythoff's nim
• scientific article; zbMATH DE number 2159657
• Slow \(K\)-\textsc{Nim}

Cites work

• scientific article; zbMATH DE number 1944411 (Why is no real title available?)
• scientific article; zbMATH DE number 1568491 (Why is no real title available?)
• scientific article; zbMATH DE number 2115805 (Why is no real title available?)
• scientific article; zbMATH DE number 3020856 (Why is no real title available?)
• The Sprague-Grundy function for Wythoff's game
• The game of End-Nim

Cited in

(2)

• A variant of Nim
• Nim fractals

This page was built for publication: Three-pile Sharing Nim and the quadratic time winning strategy

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