Le principe des tiroirs est un principe fondamental en combinatoire. Il traite du problème de la distribution d’objets (les « pigeons ») dans des boîtes (les « tiroirs »).
Son idée de base est si évidente qu’elle peut sembler triviale, mais elle permet de prouver des résultats très puissants et parfois contre-intuitifs. Il s’agit d’un argument d’existence : il garantit qu’une certaine situation se produit, sans forcément nous dire où ni comment.
Version simple : Si l’on range $n+1$ objets dans $n$ tiroirs, alors au moins un tiroir contient au moins deux objets.
Version généralisée : Si l’on range $N$ objets dans $k$ tiroirs, alors au moins un tiroir contient au moins $\lceil N/k \rceil$ objets (où $\lceil x \rceil$ est l’entier immédiatement supérieur ou égal à $x$).
Exemples d’application
La clé est toujours d’identifier correctement les « objets » et les « tiroirs ».
-
Anniversaires : Dans un groupe de 367 personnes, il est certain qu’au moins deux personnes partagent le même jour d’anniversaire.
- Objets : Les 367 personnes.
- Tiroirs : Les 366 jours possibles de l’année (29 février inclus).
-
Chaussettes : Vous avez un tiroir avec des chaussettes noires, blanches et bleues. Combien de chaussettes devez-vous prendre au minimum, sans regarder, pour être certain d’avoir une paire de la même couleur ? La réponse est 4.
- Objets : Les chaussettes que vous piochez.
- Tiroirs : Les 3 couleurs possibles.
- Avec 4 chaussettes (objets) et 3 couleurs (tiroirs), l’une des couleurs doit forcément avoir été piochée au moins deux fois.
- Sommes de nombres : Prenez n’importe quel ensemble de 10 nombres entiers distincts entre 1 et 100. Il existe forcément deux sous-ensembles disjoints dont la somme des éléments est la même. La démonstration est plus complexe, mais repose sur le principe des tiroirs en considérant les sommes possibles comme les objets et le nombre de sous-ensembles comme les tiroirs.
Importance
Ce principe est un outil de base dans de nombreuses preuves mathématiques, notamment en :
- Théorie des nombres et Combinatoire.
- Informatique théorique, pour prouver des bornes inférieures sur la complexité d’algorithmes ou l’existence de collisions dans les fonctions de hachage.