Résumé : Dans la première partie de l'exposé, nous présenterons quelques concepts classiques de la théorie des jeux combinatoires : définition d'un jeu, quelques exemples comme le jeu de Nim, Wythoff ou Chomp!, graphe et noyau d'un jeu, position perdante/gagnante, nim-somme, fonction de Sprague-Grundy et somme de jeux, etc.

Ensuite, nous montrerons à travers le "célèbre" jeu de Wythoff, variante du jeu de Nim, des liens existant avec la combinatoire des mots. En effet, il est assez facile de vérifier que le mot de Fibonacci abaababaab..., unique point fixe du morphisme f(a)=ab et f(b)=a, code exactement les positions perdantes du jeu de Wythoff. En outre, des liens entre les mots substitutifs engendrés par morphisme itéré et les systèmes de numération sont bien connus (la voie a été ouverte par Cobham dans son papier de 1972 sur les suites k-automatiques). Ainsi, on peut aussi caractériser les positions perdantes du jeux de Wythoff à l'aide de la numération de Zeckendorf construite sur la suite de Fibonacci 1,2,3,5,8,... Cette caractérisation repose sur des propriétés syntaxiques (testables par automate fini) des représentations dans ce système.

Partant de ces constatations, nous présenterons, dans la dernière partie de l'exposé, quelques travaux récents montrant les interactions "fructueuses" existant entre jeux combinatoires, mots infinis engendrés par morphisme et systèmes de numération associés. Nous évoquerons les questions suivantes : étant donné un mot infini comme le mot de Tribonacci point fixe du morphisme f(a)=ab, f(b)=ac, f(c)=a, peut-on définir un jeu dont les positions perdantes sont codées par ce mot ? Existe-t-il des variantes du jeu de Wythoff (on change l'ensemble des coups admissibles à jouer) possédant le même ensemble de positions perdantes ? Toute suite de Beatty homogène donne-t-elle naissance à un jeu combinatoire invariant pour lequel l'ensemble des coups disponibles ne dépend pas de la position de jeu ?

Quelques références :

A. Fraenkel, Heap Games, Numeration Systems and Sequences, Annals of Combin.. 2 (1998), 197–210.
A. Fraenkel, How to beat your Wythoff games’ opponent on three fronts, Amer. Math. Monthly 89 (1982), 353–361.
voir aussi les pages de Aviezri Fraenkel http://www.wisdom.weizmann.ac.il/~fraenkel/
E. Duchêne, M. Rigo, A morphic approach to combinatorial games : the Tribonacci case, Theor. Inform. Appl. 42 (2008), 375-393.
E. Duchêne, M. Rigo, Invariant games, Theoret. Comp. Sci. 411 (2010), 3169-3180, http://orbi.ulg.ac.be/handle/2268/35496
E. Duchêne, A. Fraenkel, R. Nowakowski, M. Rigo, Extensions and restrictions of wythoff's game preserving wythoff's sequence as set of P positions, to appear in J. Combinat. Theory Ser. A 117 (2010), 545-567, http://orbi..ulg.ac.be/handle/2268/17591

http://www.discmath.ulg.ac.be/publi.html

pour une référence "grand public" sur les jeux combinatoires, voir par exemple les notes :
Thomas S. Ferguson, UCLA, http://www.math.ucla.edu/~tom/Game_Theory/Contents.html

Enfin, pour un survol sur les numérations (avec quelques remarques sur les jeux combinatoires), cf.

M. Rigo, Numeration Systems: a Link between Number Theory and Formal Language Theory, Proceedings of Developments in Language Theory, London, Ontario, Canada (2010), Lect. Notes in Comput. Sci. 6224, 33-53 Springer-Verlag (2010), http://orbi.ulg.ac.be/handle/2268/35488

 [Slides.pdf]

Dernière modification : Monday 27 May 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr