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

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=(x1,…,xn). Due to symmetry, we can assume wlog that x1≤…≤xn. Our computations partition all exceptions into the following three families: x1 is even, x1=1, and odd x1≥3. In all three cases, we suggest formulas covering all found exceptions, but it is not proven that there are no others.