Principe des tiroirs
Le principe des tiroirs est une technique de comptage classique en mathématiques et en combinatoire. Il affirme que si l’on a plus d’éléments que de cases pour les placer, alors au moins une case doit contenir plus d’un élément.
Le principe est étonnamment simple, mais très puissant. Il est utilisé pour démontrer que certaines situations sont inévitables, quelle que soit la façon dont les éléments sont répartis. Il existe une version simple et une version générale.
Principe simple des tiroirs
Si l’on a k + 1 éléments à répartir dans k cases, alors au moins une case contiendra plus d’un élément.
Exemple 1 : Anniversaires
Dans un groupe de 13 personnes, au moins deux doivent avoir leur anniversaire le même mois, puisqu’il n’y a que 12 mois.
Exemple 2 : Chaussettes
Si vous avez 3 chaussettes mais seulement 2 couleurs (par exemple noir et blanc), alors au moins deux chaussettes auront la même couleur.
Démonstration (simple)
Supposons le contraire : qu’aucune case ne contienne plus d’un élément. Alors il peut y avoir au maximum k éléments dans k cases. Mais nous avons k + 1 éléments. C’est une contradiction, donc au moins une case doit contenir plus d’un élément.
Principe général des tiroirs
Si l’on distribue N éléments dans k cases, alors au moins une case contiendra au moins :
$$ \large \left\lceil \frac{N}{k} \right\rceil $$
Cela signifie qu’on peut toujours garantir une certaine répartition minimale, quelle que soit la manière dont les éléments sont placés.
Exemple 1 : Match de football
Il y a 40 000 spectateurs à un match et 365 anniversaires possibles. Au moins un anniversaire est partagé par :
$$ \large \left\lceil \frac{40000}{365} \right\rceil = 110 $$
Cela signifie qu’au moins 110 personnes partagent un anniversaire.
Exemple 2 : Jeu de cartes
Dans un jeu de 52 cartes sans jokers, les cartes sont réparties en 4 couleurs. Si l’on tire 21 cartes, alors au moins une couleur aura :
$$ \large \left\lceil \frac{21}{4} \right\rceil = 6 $$
On est donc sûr d’avoir au moins 6 cartes de la même couleur.
Démonstration (générale)
Si toutes les cases avaient au maximum \( \large \left\lfloor \frac{N}{k} \right\rfloor \) éléments, alors le nombre total d’éléments serait au maximum \( \large k \cdot \left\lfloor \frac{N}{k} \right\rfloor \leq N \). Mais si c’était le cas, il manquerait de la place pour certains éléments. Donc au moins une case doit contenir \( \large \left\lceil \frac{N}{k} \right\rceil \) éléments.
Applications
Le principe des tiroirs paraît simple, mais il est utilisé dans de nombreux contextes avancés :
- Combinatoire : Démonstrations sur les permutations et les combinaisons.
- Probabilité : Montrer que certains résultats sont inévitables.
- Théorie des graphes : Garantir qu’un graphe ait des nœuds avec des connexions spécifiques.
- Informatique : Fonctions de hachage et stockage de données – s’il y a plus d’éléments que de places, des collisions doivent se produire.
Résumé
Le principe des tiroirs dit que si l’on a plus d’éléments que de cases, alors au moins une case doit contenir plus d’un élément. La version générale nous donne la formule :
$$ \large \left\lceil \frac{N}{k} \right\rceil $$
Le principe peut être démontré simplement, mais il a des applications profondes en mathématiques et en informatique. Il garantit que nous pouvons comprendre quand quelque chose est inévitable, et c’est un outil important en combinatoire et en probabilité.