Evènement pour le groupe GT Graphes et Applications

Date 2015-10-16  14:00-15:00
Titrei-Mark: A new subtraction division game 
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.  
LieuSalle 178 
OrateurEric Sopena 

Aucun document lié à cet événement.

Retour à l'index