Comptes Rendus MATh.en.JEANS 98-10

Enseignants : Hervé HAMON, Michel ENJALBERT (lycée Fustel de Coulanges, 91300 Massy)

Chercheur : Jean-Pierre RESSAYRE (Université Paris 7).

Atelier MATh.en.JEANS du lycée Fustel de Coulanges, 11 rue des Migneaux, 91300 Massy. Atelier de Pratique Scientifique, année scolaire 1997-1998.

---

[ Article préparé d'après l'exposé des élèves au congrès 1998, vérifié et annoté ; les passages entre crochets sont des éditeurs.]
[La typographie plus large, en "Comic sans MS", indique des citations du texte original des élèves.]

L'icone renvoie au Glossaire MATh.en.JEANS , à un document ]

1. Le sujet

Des mots infinis comme résultats d'un jeu.

Dans un jeu infini, deux joueurs, et , choisissent à tour de rôle un chiffre " 0 " ou " 1 " , indéfiniment. Le résultat du jeu est le "mot infini" X formé par les chiffres choisis.

X= X₁X₂X₃ X₄...

Le défi posé au premier joueur, est d'éviter, ou au contraire de faire apparaître, certains motifs, décidés à l'avance par les joueurs. Le but du second joueur, , est d'empêcher de parvenir à ses fins.

Pour chaque défi donné, deux questions seront étudiées :

• ou  a-t-il une stratégie gagnante ?
• Cette stratégie peut-elle être obtenue d'une manière "automatique", c'est à dire sans qu'il soit nécessaire d'analyser tous les coups précédents pour prendre une décision ?

Exemple de défi défini au début du jeu.

Défi n°1. Le joueur gagne si le nombre de " 1 " apparaissant dans X est infini.
a une stratégie gagnante simple et automatique : « Il lui suffit de jouer toujours des " 1 " pour gagner ».

1. Les graphes et les automates.

Une manière automatique de jouer, pour un joueur donné, va pouvoir être représentée par un graphe orienté, c'est à dire un système de points [appelés sommets] dont certains sont reliés par des flèches.
Chaque point va indiquer un type de position possible pour le joueur, appelé l'état du joueur. Intuitivement, un état correspond à une manière particulière de jouer le coup suivant. Ces états sont repérés par des lettres. [Par convention, la lettre A désignera toujours l'état du joueur au début du jeu.]
A chaque flèche du graphe va être attaché une étiquette qui indique au joueur comment répondre au coup précédent de son adversaire. Ainsi dans le graphe dessiné ci-contre pour le joueur , la présence de l'étiquette 0/1 sur la flèche allant de l'état D à l'état C traduit la règle suivante : « Lorsque je suis dans l'état D et si a joué 0, alors je joue 1 et je passe à l'état C »		exemple d'automate

Un tel graphe, orienté et étiqueté, s'appelle un automate [note 1].

3. Défis simples.

Défi n°2. gagne si le mot X comporte un nombre fini de " 1 ".

a une stratégie gagnante simple et automatique : Il lui suffit de jouer toujours des " 1 " pour gagner. Cette stratégie est dictée par l'automate dessiné ci-contre.

automate n°2

Défi n°3. gagne si le mot X ne comporte pas la séquence « 011 ».

Là, c'est qui dispose d'une stratégie gagnante : ne jouant que des " 0 ", la séquence " 011 "ne peut apparaître.

automate n°3

Défi n°4. gagne si le mot X comporte un nombre fini de « 01 ».

va gagner en jouant 1 quand joue "0", et "0" quand joue "1". [Théorème 1]. Si applique l'automate n°4, perd le défi n°4, car une infinité de 01 apparaît.		automate n°4
Démonstration Soit joue « 0 ». Alors, joue un « 1 », et I perd [une fois], Soit joue un « 1 », alors joue un « 0 ». Ensuite, si joue « 0 », alors joue « 1 » et a perdu [une fois], sinon joue « 1 » et perd [une fois] car la séquence 01 apparaît. Donc, au moins tous les deux coups, la séquence 01 va apparaître.

3. Défis plus compliqués.

Défi n°5. gagne si

• le mot X comporte un nombre infini de " 1 ".
• et un nombre fini de " 0110 "
• et un nombre fini de " 01110 "

Le jeu de est décrit par l'automate n°5. [Théorème 2]. Si applique l'automate n°5, perd le défi n°5.		automate n°5
Démonstration Deux cas sont considérés, selon le choix de . 1er cas. commence à jouer " 0 ". joue " 0 ", passe à l'état B et on a la séquence 0-0. Si maintenant joue " 0 ", joue " 0 ", revient à l'état A et on a la séquence 0-0-0-0. Si au contraire joue " 1 ", joue " 1 ", passe à l'état C et on a la séquence 0-0-1-1. Ensuite : Si joue " 0 ", joue " 1 ", passe à l'étatB et on a la séquence 0-0-1-1-0-1. Si joue " 1 ", joue " 0 ", passe à l'étatA et on a la séquence 0-0-1-1-1-0. Les mêmes séquences seraient obtenues si au départse trouvait dans l'état B au lieu de l'état A. Mieux, les mêmes séquences seraient obtenues à n'importe quel moment du jeu ; on peut donc retenir les propriétés générales suivantes : Propriété 1.1 : Si est dans l'un des états A ou B, se trouve encore dans l'un des états A ou B. tant que joue " 0 ", Propriété 1.2 : Dès que joue " 1 ", lorsque se trouve dans l'un des états A ou B, alors l'un des motifs " 0110 " ou " 01110 " apparaît et revient ensuite à l'un des états A ou B. 2ème cas. commence à jouer " 1 ". joue 1, passe à l'état C et on a la séquence 1-1. Puis : Si maintenant joue " 1 ", joue " 0 ", passe à l'état A et on a la séquence 1-1-1-0 Si au contraire joue " 0 ", joue " 1 ", passe à l'état B et on a la séquence 1-1-0-1. Ensuite : Si joue " 0 ", joue " 0 ", passe à l'état A et on a la séquence 1-1-0-1-0-0. Si joue " 1 ", joue " 1 ", passe à l'état C et on a la séquence 1-1-0-1-1-1. De même que dans le premier cas, on remarque que les mêmes séquences seraient obtenues si au départse trouvait dans l'état B au lieu de l'état A, et ceci à n'importe quel moment du jeu. On retiendra : Propriété 2.1 : Si joue " 1 " lorsque se trouve dans l'un des états A ou B, l'une des séquences 1-1-1-0 ou 1-1-0-1 apparait. [...] [note 2]

5. Applications et utilisation des automates

Note 1. Les automates sont des ordinateurs simplifiés dédiés à une tâche particulière. Ils sont couramment utilisés dans la pratique sous diverses formes (circuits logiques, cartes à puces, robots, systèmes experts, réseaux neuronaux, etc.) pour simuler des comportements "intelligents". L'étude et la construction des automates relève de l'Informatique Théorique et de l'Intelligence Artificielle. Elle a également un grand intérêt mathématique, notamment pour la classification des nombres "réels", vus comme suite illimités de chiffres. Pour cet aspect et pour une présentation, par le chercheur, de la problématique générale des automates en informatique, voir :
les automates finis en mathématiques , conférence de M. Jean-Paul Allouche, suivie d'une présentation des automates par M. Jean-Pierre Ressayre, Actes MATh.en.JEANS 1995, MATh.en.JEANS éd., 1996, Paris, pp. 159-168 [Format pdf]

retour à l'appel de cette note

Note 2.  La démonstration fournie à l'exposé du congrès s'arrêtait là . Voici un moyen de la compléter.

On considére deux options pour le joueur, suivant qu'il joue ou non une infinité de fois "1 ".

automate n°5

Option I : ne joue qu'un nombre fini de " 1 ". Au bout d'un certain temps, joue constamment " 0 " ce qui fait que reste aux états A ou B, en jouant lui aussi constamment " 0 ". perd puisque le mot X obtenu n'a qu'un nombre fini de " 1 ".

Option II joue " 1 " une infinité de fois. Si se trouve dans l'état A une infinité de fois. reste alors aux états A ou B tant que joue " 0 " (propriété 1.1), puis jouera " 1 " et un motif 0110 ou 01110 apparaîtra (propriété 1.2). Puisque ceci se produit une infinité de fois, perd.   Si se se trouve dans l'état A qu'un nombre fini de fois. Au bout d'une certain temps, ne se trouve donc plus jamais dans l'état A. D'après l'automate, ceci n'est possible que si joue " 1 " quand est dans l'état B, et joue " 0 " quand est dans l'état C, répondant par " 1 " à chaque coup. D'après la propriété 2, la séquence 1-1-0-1 se répète donc périodiquement : 1-1 -0-1-1-1-0-1-1-1-0-1-1-1-0-1-1-1-0-1-1-1-0-1 Donc la séquence 01110 se répète elle aussi une infinité de fois et perd. La démonstration est ainsi complète.

retour à l'appel de cette note

3. Pour une application des automates à la reconnaissance de séquences finies de chiffres (digicodes par exemple), voir :
automates finis, par Audrey Bouchon (1°S), Catherine Enjalbert (1°S), Caroline Hostalery (2^de) et Lucile Toussaert du lycée Fustel de Coulanges de Massy, Actes MATh.en.JEANS 1997, MATh.en.JEANS éd., 1998, Paris, pp. 277-288. [Format pdf]
Pour d'autres utilisations des automates, voir :
les automates finis en mathématiques , conférence de M. Jean-Paul Allouche, suivie d'une présentation par M. Jean-Pierre Ressayre d'un thème de recherche sur les automates, Actes MATh.en.JEANS 1995, MATh.en.JEANS éd., 1996, Paris, pp. 159-168 [Format pdf].

retour à l'appel de cette note

jeu infini mot binaire motif graphes automates nombres chiffres décimales