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 
Emailsopena@labri.fr 



Aucun document lié à cet événement.

Retour
Retour à l'index