E452. Qui se répète perd - E452. Qui se répète perd E4. Jeux de NIM et v... | Les jeux mathématiques de Diophante, plus de

Plus de 3000 récréations et problèmes mathématiques !

Ce site a été créé en souvenir de DIOPHANTE, mathématicien grec, qui nous a laissé de remarquables ouvrages d'arithmétique. L'objectif est de constituer une vaste bibliothèque de problèmes mathématiques avec les énoncés et les solutions classés par thèmes et selon leur niveau de difficulté et de proposer chaque mois plusieurs problèmes à la sagacité des lecteurs qui ont toute latitude pour envoyer leurs réponses.

Accueil

Problèmes par thèmes

E. Logique - Autoréférences

E4. Jeux de stratégie

E452. Qui se répète perd

Avertissement

Tous les problèmes sont identifiés par un niveau de difficulté :

Très facile

Facile

Moyen

Difficile

Très difficile

Variable

D'autre part, les problèmes se traitent généralement à la main et sont alors repérés par l'icône

Pour faciliter leur résolution, l'ordinateur peut être utile. Dans ce cas, vous verrez apparaître aussi cette icône

Quand l'ordinateur est indispensable, l'icône

figure seule.

Pour avoir accès aux solutions de chaque problème, cliquez sur solution.

Les figures et les graphes ont été réalisés grâce au logiciel Declic.

Avertissement

E452. Qui se répète perd

E4. Jeux de NIM et variantes

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.
Q₁ Démontrer que quel que soit n ≥ 2, la partie se termine toujours en un nombre fini de tours.
Q₂ n = 3 et Puce commence la partie.Qui est vainqueur?
Q₃ n = 4 et Zig commence la partie.Qui est vainqueur?
Q₄ 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 Q₂,Q₃ et Q₄ sont respectivement les suivantes:
Q₂ n= 3, Puce commence la partie==> Zig est vainqueur
Q₃ n= 4, Zig commence la partie==> Zig est vainqueur
Q₄ 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.

Fabien Gigante,

Jean Moreau de Saint-Martin,

Daniel 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é!

Crée et hébergé par Kangourouge.com