Le principe des tiroirs
Objectif : treize personnes, douze mois, une certitude
L’essentiel
Réunissez treize personnes. Sans connaître aucune date, sans poser aucune question, on peut affirmer : au moins deux d'entre elles sont nées le même mois. Ce n'est pas une probabilité, c'est une CERTITUDE — et elle ne coûte aucun renseignement.
À retenir
- Principe des tiroirs : n objets dans p tiroirs avec n STRICTEMENT plus grand que p, alors un tiroir contient au moins deux objets.
- Il se démontre par l'absurde : si chaque tiroir n'avait qu'un objet, on n'en logerait que p.
- Version renforcée : si n dépasse k × p, un tiroir contient au moins k + 1 objets (30 élèves, 12 mois, donc trois en commun).
- Il donne l'EXISTENCE, jamais l'identité : on ne sait pas quel tiroir est chargé.
- Le pire cas se CONSTRUIT : quatre sortes de chaussettes demandent cinq tirages, et l'on vérifie qu'avec quatre un scénario sans paire existe encore.
Le tableau à connaître
| L'Énoncé | Ce qu'il Affirme | Ce qu'il N'affirme PAS | Un Exemple |
|---|---|---|---|
| Version simple | n objets dans p tiroirs, avec n plus grand que p : un tiroir en contient au moins 2 | il ne dit pas LEQUEL | 13 personnes, 12 mois : deux partagent un mois |
| La preuve, par l'absurde | si chaque tiroir avait au plus 1 objet, on en aurait au plus p — contradiction | — | 12 tiroirs ne logent pas 13 objets à raison d'un chacun |
| Version renforcée | n objets, p tiroirs, n plus grand que k × p : un tiroir en contient au moins k + 1 | — | 30 élèves, 12 mois : 30 dépasse 2 × 12, donc trois élèves partagent un mois |
| Le cas limite | n égal à p : aucune conclusion | douze personnes peuvent avoir douze mois différents | il faut STRICTEMENT plus d'objets que de tiroirs |
⚠ Attention, piège
- La faute majeure consiste à répondre à la question du cas FAVORABLE quand on demande le pire.
Exemples
- L'exercice roi du chapitre. Un tiroir contient des chaussettes de QUATRE sortes, en grande quantité, et la chambre est plongée dans le noir.
- La formule générale, et son contrôle. Avec s sortes de chaussettes, il faut s + 1 tirages au pire.
- Deux applications qui impressionnent.
Mots-clés
s + 1
Le plan de la leçon
- Une Certitude Obtenue Sans Rien Savoir
- Le Principe, sa Preuve et sa Version Renforcée
- Les Chaussettes dans le Noir, et l'Analyse du Pire Cas
- Le Piège du Pire Cas Confondu avec le Cas Probable
Je me teste
Combien faut-il réunir de personnes pour être CERTAIN que deux soient nées le même mois ?
- 12, autant que de mois
- 13, car douze mois ne logent que douze personnes à raison d'une chacune
- 24, le double du nombre de mois
Un tiroir contient des chaussettes de trois sortes, en grand nombre, dans l'obscurité totale. Combien en tirer AU PIRE pour avoir une paire assortie ?
- 4, car trois tirages peuvent donner trois sortes différentes
- 6, le double du nombre de sortes
- 2, car deux chaussettes forment une paire
Dans une classe de 30 élèves, que peut-on affirmer à coup sûr sur les mois de naissance ?
- Au plus deux élèves partagent un mois
- Au moins trois élèves sont nés le même mois, car 30 dépasse 2 × 12
- Exactement trois élèves partagent un mois
Le mot d’Oscar — Skelet, treize invités au bal. Que pouvez-vous affirmer sur leurs mois de naissance, sans rien leur demander ?
Réponses : 1. B · 2. A · 3. B