Résumé | Given two finite sets of integers S ? N {0} and D ? N {0, 1}, the impartial combinatorial game i-Mark(S, D) is played on a heap of tokens. From a heap of n tokens, each player can move either to a heap of n ? s tokens for some s ? S, or to a heap of n/d tokens for some d ? D if d divides n. Such games can be considered as an integral variant of Mark-type games, introduced by Elwyn Berlekamp and Joe Buhler and studied by Aviezri Fraenkel and Alan Guo, for which it is allowed to move from a heap of n tokens to a heap of ?n/d? tokens for any d ? D.
Under normal convention, it is observed that the Sprague-Grundy sequence of the game i-Mark(S, D) is aperiodic for any sets S and D. However, we prove that, in many cases, this sequence is almost periodic and that the set of winning positions is periodic. Moreover, in all these cases, the Sprague-Grundy value of a heap of n tokens can be computed in time O(log n).
We also prove that, under misère convention, the outcome sequence of these games is purely periodic. |