On Remoteness Functions of k -NIM with k + 1 Piles in Normal and in Misère Versions

Vladimir Gurvich, Vladislav Maximchuk, Georgy Miheenkov and Mariya Naumova ()
Additional contact information
Vladimir Gurvich: Higher School of Economics, National Research University, 101978 Moscow, Russia
Vladislav Maximchuk: Higher School of Economics, National Research University, 101978 Moscow, Russia
Georgy Miheenkov: Higher School of Economics, National Research University, 101978 Moscow, Russia
Mariya Naumova: Rutgers Business School, Rutgers University, Piscataway, NJ 08854, USA

Games, 2024, vol. 15, issue 6, 1-9

Abstract: Given integer n and k such that 0 < k ≤ n 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 k = 1 and k = n are trivial. For k = 2 , the game was solved for n ≤ 6 . For n ≤ 4 , the Sprague–Grundy function was efficiently computed (for both versions). For n = 5 , 6 , a polynomial algorithm computing P-positions was obtained for the normal version. Then, for the case k = n − 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 n − 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 x = ( x 1 , … , x n ) . Due to symmetry, we can assume wlog that x 1 ≤ … ≤ x n . Our computations partition all exceptions into the following three families: x 1 is even, x 1 = 1 , and odd x 1 ≥ 3 . In all three cases, we suggest formulas covering all found exceptions, but it is not proven that there are no others.

Keywords: impartial game theory; Sprague–Grundy and remoteness functions; exact slow NIM (search for similar items in EconPapers)
JEL-codes: C C7 C70 C71 C72 C73 (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2073-4336/15/6/37/pdf (application/pdf)
https://www.mdpi.com/2073-4336/15/6/37/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jgames:v:15:y:2024:i:6:p:37-:d:1519817

Access Statistics for this article

Games is currently edited by Ms. Susie Huang

More articles in Games from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().