Théorie > Combinatoire > Principe des tiroirs

Idée intuitive

Le nom de principe des tiroirs vient de la simple idée de placer des chaussettes dans des tiroirs (ou des pigeons dans des cases de pigeonnier pour le nom anglais : pigeonhole principle).

Supposons que nous avons $5$ tiroirs à notre disposition et que $6$ chaussettes sont rangées dedans. Nous n'avons aucune connaissance de la façon dont sont rangées ces chaussettes, et pourtant nous pouvons affirmer la chose suivante : dans un de ces tiroirs se trouvent au moins $2$ chaussettes.

Nous pouvons le vérifier facilement. En effet, si nous imaginons que ce résultat est faux (raisonnement par l'absurde), alors nous devons avoir au maximum $1$ chaussette par tiroir. Comme il y a $5$ tiroirs, il y a maximum $5$ chaussettes, ce qui contredit le nombre de $6$ chaussettes. Donc le résultat doit être vrai, et il y a au moins un tiroir qui contient au moins $2$ chaussettes.

Si maintenant nous savons qu'il y a $16$ chaussettes dans $5$ tiroirs, nous pouvons pousser le raisonnement un peu plus loin et déclarer qu'il y a au moins un tiroir qui contient au moins $4$ chaussettes.

Attention : nous parlons bien d'au moins un tiroir qui contient au moins $4$ chaussettes. En effet, il est tout à fait possible que plusieurs tiroirs contiennent $4$ chaussettes, ou qu'un tiroir contienne plus que $4$ chaussettes, voire même toutes les chaussettes. De plus, ce type de raisonnement prouve seulement l'existence du tiroir et n'indique lequel en aucune façon. Ce type de raisonnement est donc principalement efficace pour des problèmes du type "Prouver qu'il existe..." demandant seulement la preuve de l'existence d'un élément et non sa construction.