Qui se répète perd...

Le problème initial

L'ANIMATION pour expérimenter

ANALYSE et résultats



Le problème Sur l'idée du n° E 452 de Diophante.fr

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 ?

 


ANIMATION

Dans cette animation il faut,
- CHOISIR d'emblée la longueur du bloc que l'on ne doit pas reproduire.
- Pour choisir un chiffre, on fait tourner la boule.
  Eventuellement recliquer la boule à la fin de sa rotation.
- Il suffit ensuite de suivre les indications.

 


ANALYSE et résultats

. Lorsque la longueur du bloc à ne pas répéter, est impaire, on trouve aisément une stratégie gagnante pour le second joueur.
. Lorsque n=2, il y une stratégie gagnante pour le second joueur également.
  Bien observer le jeu de l'ordinateur.

- Pour n= 4, le premier joueur a une stratégie gagnante.

Par contre, je n'ai pas trouvé de stratégie systématiquement gagnante lorsque la longueur du bloc est paire.
Le problème reste ouvert d'après son auteur J. Matousek : Problème 1-3-7 Invitation to Discrete Mathematics

On peut "bien" jouer cependant...

Analyser le comportement de l'ordinateur lorsqu'il prend la main.

Pour en savoir plus: voir ICI différentes analyses.

  


Menu trucs  Accueil