Bernard Langer [1]

Résumé de l’article

Après une présentation matérielle du jeu, l’auteur en précise la règle, avec choix du code secret et calcul du score. Puis il étudie les deux scénarios, suivant que l’ordinateur est codeur ou décodeur. Il présente l’algorithme dans chaque cas. Dans le cas du jeu classique (4 trous, 6 couleurs) l’algorithme de Knuth permet de trouver le code secret en au plus 5 tentatives.
Trois annexes donnent, la première, la liste des programmes en langage Python disponibles sur le site de l’APMEP, la deuxième la conversion d’un entier en base b, la troisième l’algorithme de Knuth dans diverses situations.

Plan de l’article

• 1. Introduction : Présentation du jeu.
• 2. Analyse de la situation
  • 2.1. Une première situation : Le codeur est l’ordinateur – le décodeur est humain
  • 2.2. Seconde situation : l’ordinateur décode
• 3. L’algorithme de Knuth : le « five guess »
  • 3.1. Principe dans le cas classique
  • 3.2. Détails dans le cas 3 trous – 3 couleurs
  • 3.3. Preuve du five-guess.
• 4. Épilogue
• ANNEXES

Télécharger l’article en pdf dans son intégralité
Télécharger les programmes Python
<redacteur|auteur=500>