Given integer
n and
k such that
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
[...] Read more.
Given integer
n and
k such that
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
and
are trivial. For
, the game was solved for
. For
, the Sprague–Grundy function was efficiently computed (for both versions). For
, a polynomial algorithm computing P-positions was obtained for the normal version. Then, for the case
, 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
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
. Due to symmetry, we can assume wlog that
. Our computations partition all exceptions into the following three families:
is even,
, and odd
. In all three cases, we suggest formulas covering all found exceptions, but it is not proven that there are no others.
Full article
