On Remoteness Functions of Exact Slow k-NIM with k+1 Piles

Integers. Electronic Journal of Combinatorial Number Theory. 2024. Vol. 24. Article #G1.

Гурвич В. А., Martynov D., Максимчук В. Д., Вялый М. Н.

Given integers n and k such that 0 < k ≤ n and n piles of tokens, two players alternate turns. In each move they are allowed to choose any k non-empty piles and remove exactly one token from each pile. The player who has to move but cannot is the loser. Cases k = 1 and k = n are trivial. For k = 2 the game was solved for n ≤ 6. For n ≤ 4 the Sprague-Grundy (SG) function was efficiently computed, for both the normal and mis`ere versions. For n = 5, 6 a polynomial algorithm computing P-positions for the normal version was obtained. Here we consider case 1 < k = n − 1 in the normal version and compute the Smith remoteness function, whose even values are taken in the P-positions. An optimal move is always defined by the following simple rule: • if all piles are odd, keep a largest one and reduce all others; • if there exist even piles, keep a smallest one of them and reduce all others. This strategy is optimal for both players, moreover, it allows a player to win as fast as possible from an N-position and to resist as long as possible from a P-position.

Ключевые слова: strategy, Remoteness function, k-NIM

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Математические методы и алгоритмы в теориях информации, сложности вычислений, формальных языков и комбинаторной теории матриц (2024)