E452. Qui se répète perd Imprimer
E4. Jeux de NIM et variantes

calculator_edit.png  

Diophante fixe un entier naturel n ≥ 2. Zig et Puce partent d'une ligne vide, le premier joueur écrit "0" ou "1" puis chacun à son tour ajoute "0" ou "1" à la fin de la séquence de "0" et de "1" précédemment écrite. Un joueur perd si le chiffre qu'il ajoute fait apparaître un bloc de n chiffres consécutifs qui se répète pour la deuxième fois. Les deux blocs qui se répètent peuvent se chevaucher
Par exemple:
-  pour n = 3, à partir de la séquence 0011100 le second joueur perd en écrivant "1" car le bloc de 3 chiffres "001" se répète dans la séquence 00111001.
-  pour n = 5, à partir de la séquence 101010 le premier joueur perd en écrivant "1" car le bloc de 5 chiffres "10101" se répète dans la séquence 1010101.
Q1 Démontrer que quel que soit n ≥ 2, la partie se termine toujours en un nombre fini de tours.
Q2 n = 3 et Puce commence la partie.Qui est vainqueur?
Q3 n = 4 et Zig commence la partie.Qui est vainqueur?
Q4 n = 5 et Zig commence la partie.Qui est vainqueur?
Pour les plus courageux: peut-on déterminer qui a une stratégie gagnante en fonction de n?

 Solution


Ce problème a donné lieu à des analyses très fouillées (avec ou sans l'aide d'automates) de la part de nos lecteurs.
Les réponses correctes apportées aux questions Q2,Q3 et Q4 sont respectivement les suivantes:
Q2 n= 3, Puce commence la partie==> Zig est vainqueur
Q3 n= 4, Zig commence la partie==> Zig est vainqueur
Q4 n= 5, Zig commence la partie==> Puce est vainqueur
Questions pour les plus courageux: quand n est impair, le deuxième joueur a une stratégie gagnante qui consiste à écrire le chiffre distinct de celui écrit précédemment par le premier joueur. En d'autres termes, si le premier joueur écrit "1", le second joueur écrit systématiquement "0" et vice versa si le premier joueur écrit "0", le second joueur écrit systématiquement "1".
Quand n = 6, Fabien Gigante a trouvé – avec l’aide d’un automate – que le premier joueur a une stratégie gagnante.
Pour n pair > 6, le problème reste ouvert.
pdfFabien Gigante,pdfJean Moreau de Saint-Martin,pdfClaudio Baiocchi,pdfThérèse Eveilleau,pdfJean-Louis Legrand,pdfDavid Draï,pdfAntoine Verroken et pdfDaniel Collignon ont traité correctement tout ou partie du problème.
Par ailleurs Thérèse Eveilleau sur son site Bienvenue en Mathématiques Magiques a réalisé une animation qui permet d'affornter l'ordinateur dans un duel sans pitié!