Question transversaleMathsNSIArbres et structures de données

Comment deviner un personnage parmi un million en vingt questions seulement ?

Q: Combien de questions pour deviner un nombre entre 1 et 1 000 ?

$⌈log₂1000⌉=10$, car $2¹⁰=1024$.

Q: Calculez I(0,1).

$-0,1log₂0,1-0,9log₂0,9≈0,33+0,14=0,47$.

Chaque question à réponse oui ou non sépare les possibilités en deux. Un arbre de décision de hauteur 20 a 2²⁰ = 1 048 576 feuilles : 20 questions suffisent pour un million de personnages, à condition que chacune coupe l'ensemble en deux moitiés. Il en faudrait 33 pour toute l'humanité.

Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

J'ai joué au jeu en ligne qui devine un personnage auquel on pense, et il trouvait presque toujours en une vingtaine de questions. Je me suis demandé comment c'était possible avec des millions de personnages célèbres. En NSI, j'ai compris que chaque question est un nœud d'un arbre binaire, et que tout se joue sur la qualité des questions.

L'enjeu et les notions du programme

Relier le nombre de questions à la hauteur d'un arbre binaire et au logarithme, et montrer qu'une bonne question coupe l'ensemble en deux.

Mathématiques

Puissances de 2, logarithme en base 2 (terminale)
Probabilités, équiprobabilité (première)
Dénombrement (terminale)

Numérique et sciences informatiques

Arbres binaires, hauteur et feuilles (terminale)
Arbres de décision, algorithmes d'apprentissage (première)

Le plan de l'exposé en 9,5 min

1. Introduction
1 min
Dans le jeu des vingt questions, on devine un objet en posant des questions à réponse oui ou non. Problématique : combien d'objets peut-on distinguer en vingt questions, et comment choisir les questions ?
2. Mathématiques : un arbre de hauteur 20
4 min
Chaque question a deux réponses. Une stratégie se représente par un arbre binaire : chaque nœud est une question, chaque feuille une réponse finale. Avec $k$ k questions, l'arbre a au plus $2^{k}$ 2^(k) feuilles. Pour $k = 20$ k=20 : $2^{20} = 1048576$ 2²⁰=1 048 576, un peu plus d'un million.
Inversement, pour distinguer $N$ N objets, il faut au moins $lo g_{2} N$ log₂N questions dans le pire cas. Pour la population mondiale (environ $8, 1 \times 1 0^{9}$ 8,1×10⁹), $lo g_{2} (8, 1 \times 1 0^{9}) \approx 32, 9$ log₂(8,1×10⁹)≈32,9 : 33 questions suffiraient à identifier n'importe quel humain.
Mais cette borne n'est atteinte que si chaque question coupe l'ensemble en deux parties égales. Une question qui n'élimine qu'un dixième des possibilités apporte beaucoup moins : avec une probabilité $p$ p de « oui », l'information moyenne est $- p lo g_{2} p - (1 - p) lo g_{2} (1 - p)$ -plog₂p-(1-p)log₂(1-p) bit, maximale (1 bit) pour $p = \frac{1}{2}$ p=1/2. Pour $p = 0, 1$ p=0,1, seulement 0,47 bit.
3. NSI : les arbres de décision
3 min
Les algorithmes d'apprentissage construisent des arbres de décision à partir de données : à chaque nœud, ils choisissent la question qui sépare le mieux les exemples, c'est-à-dire celle qui apporte le plus d'information. C'est exactement la stratégie du bon joueur.
La recherche dichotomique dans une liste triée en est un cas particulier : la question « est-ce avant le milieu ? » coupe toujours en deux, d'où les $lo g_{2} n$ log₂n étapes. Une mauvaise stratégie (« est-ce Napoléon ? », « est-ce Molière ? ») revient à une recherche séquentielle : jusqu'à $N$ N questions.
4. Conclusion
1,5 min
Vingt questions suffisent pour un million de possibilités parce qu'un arbre binaire de hauteur 20 a plus d'un million de feuilles. Encore faut-il que chaque question coupe en deux : une question équilibrée apporte un bit d'information. J'ouvre sur l'entropie de Shannon, qui mesure cette information.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

2^{20} = 1048576 k \geq lo g_{2} N lo g_{2} (8, 1 \times 1 0^{9}) \approx 32, 9 2²⁰=1 048 576 k\geqlog₂N log₂(8,1\times10⁹)\approx32,9 I (p) = - p lo g_{2} p - (1 - p) lo g_{2} (1 - p) I (0, 5) = 1 I (0, 1) \approx 0, 47 I(p)=-plog₂p-(1-p)log₂(1-p) I(0,5)=1 I(0,1)\approx0,47

Conclusion : la réponse à la question

Le nombre de questions nécessaire est le logarithme en base 2 du nombre de possibilités. Une bonne question est une question équilibrée : c'est la même idée que la dichotomie et que les arbres de décision.

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Combien de questions pour deviner un nombre entre 1 et 1 000 ?

$⌈ lo g_{2} 1000 ⌉ = 10$ ⌈log₂1000⌉=10, car $2^{10} = 1024$ 2¹⁰=1024.

Pourquoi une question « est-ce Napoléon ? » est-elle mauvaise ?

Elle n'élimine presque rien quand la réponse est non : elle apporte très peu d'information.

Calculez I(0,1).

$- 0, 1 lo g_{2} 0, 1 - 0, 9 lo g_{2} 0, 9 \approx 0, 33 + 0, 14 = 0, 47$ -0,1log₂0,1-0,9log₂0,9≈0,33+0,14=0,47.

Que se passe-t-il si le joueur ment une fois ?

L'arbre mène à une mauvaise feuille ; il faut des questions supplémentaires de vérification, comme dans les codes correcteurs.

Combien de feuilles a un arbre binaire de hauteur h ?

Au plus $2^{h}$ 2^(h).

Les pièges qui coûtent des points

Croire que 20 questions suffisent quelles que soient les questions.
Confondre log₂ et log₁₀.
Oublier l'arrondi à l'entier supérieur.

Revoir les notions

Autres questions : arbres et structures de données

Toutes les questions maths-nsi →

Préparer l'oral, pas seulement le contenu

Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.

Méthode : traiter une question de Grand oral →

Continuer la préparation

Le Grand oral 2027 →Méthode : traiter une question →Toutes les questions, par combinaison →Questions de maths seules →Questions maths-physique-chimie →Questions maths-SES →Questions maths-SVT →Questions maths-SI →Questions maths-HGGSP →Questions maths-anglais →