Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/330106 
Year of Publication: 
2024
Citation: 
[Journal:] Games [ISSN:] 2073-4336 [Volume:] 15 [Issue:] 6 [Article No.:] 37 [Year:] 2024 [Pages:] 1-9
Publisher: 
MDPI, Basel
Abstract: 
Given integer n and k such that 0<π‘˜β‰€π‘› and n piles of stones, two players alternate turns. On each move, a player is allowed to choose any k piles and remove exactly one stone from each. The player who has to move but cannot is the loser in the normal version of the game and (s)he is the winner in the misΓ¨re version. Cases π‘˜=1 and π‘˜=𝑛 are trivial. For π‘˜=2, the game was solved for 𝑛≀6. For 𝑛≀4, the Sprague-Grundy function was efficiently computed (for both versions). For 𝑛=5,6, a polynomial algorithm computing P-positions was obtained for the normal version. Then, for the case π‘˜=𝑛-1, a very simple explicit rule that determines the Smith remoteness function was found for the normal version of the game: the player who has to move keeps a pile with the minimum even number of stones; if all piles have an odd number of stones, then (s)he keeps a maximum one, while the 𝑛-1 remaining piles are reduced by one stone each in accordance with the rules of the game. Computations show that the same rule works efficiently for the misΓ¨re version too. The exceptions are sparse. We list some. Denote a position by π‘₯=(π‘₯1,…,π‘₯𝑛). Due to symmetry, we can assume wlog that π‘₯1≀…≀π‘₯𝑛. Our computations partition all exceptions into the following three families: π‘₯1 is even, π‘₯1=1, and odd π‘₯1β‰₯3. In all three cases, we suggest formulas covering all found exceptions, but it is not proven that there are no others.
Subjects: 
impartial game theory
Sprague-Grundy and remoteness functions
exact slow NIM
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Appears in Collections:

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.