Nombre mystère
Plus grand, plus petit. Le jeu paraît enfantin jusqu'à ce qu'on réalise qu'il illustre l'un des algorithmes les plus utiles de l'informatique.
Entre 1 et 100
La bonne méthode, et pourquoi elle est optimale
La stratégie gagnante consiste à couper l'intervalle en deux à chaque proposition. Sur une étendue de 1 à 100, on commence par 50. Si la réponse est « plus grand », il ne reste que 51 à 100, et on propose 75. Puis 87, puis 93, et ainsi de suite.
Chaque essai divise par deux le nombre de possibilités restantes. C'est pour cela que sept essais suffisent toujours entre 1 et 100 : deux à la puissance sept vaut 128, ce qui couvre largement les cent nombres possibles.
| Étendue | Essais nécessaires au maximum |
|---|---|
| 1 à 20 | 5 |
| 1 à 100 | 7 |
| 1 à 500 | 9 |
| 1 à 1000 | 10 |
Le tableau montre quelque chose de contre-intuitif : multiplier l'étendue par cinquante ne double même pas le nombre d'essais nécessaires. C'est toute la puissance de cette approche.
Le même principe, tous les jours, sans le savoir
Cette méthode s'appelle la recherche dichotomique, et c'est l'un des algorithmes les plus employés en informatique. Chercher un mot dans un dictionnaire papier, c'est elle. Retrouver une panne sur une chaîne en coupant le circuit en deux, c'est encore elle. Un moteur de recherche qui interroge un index trié l'utilise des milliards de fois par jour.
Elle a aussi une limite qu'il est utile de connaître : elle exige que les données soient ordonnées. Sans ordre, aucune coupe en deux n'a de sens, et il faut tout parcourir.
Quand couper en deux n'est pas le mieux
Une nuance que peu de gens connaissent : si vous savez que le nombre est plus probablement dans une zone, le milieu exact n'est plus le meilleur choix. Contre un humain qui choisit lui-même le nombre, cela compte beaucoup, car les gens tirent très rarement au hasard : ils évitent les extrémités, évitent les nombres ronds, et choisissent bien plus souvent que le hasard des nombres se terminant par 3 ou 7. Ici le tirage est réellement aléatoire, donc la coupe en deux reste imbattable.
Le tirage, et la fourchette affichée
Le nombre change-t-il en cours de partie ?
Non, il est tiré au début et ne bouge pas. Certaines versions tricheuses de ce jeu déplacent le nombre pour rallonger la partie, ce n'est pas le cas ici.
À quoi sert l'affichage de la fourchette ?
Il montre l'intervalle encore possible compte tenu de vos propositions. C'est une aide pédagogique : elle rend visible le rétrécissement obtenu à chaque coup.