Principe des tiroirs

Définition intuitive

Le principe des tiroirs stipule que si l’on range $k$ chaussettes dans $n$ tiroirs, avec $k > n$, alors il existe un tiroir qui contient au moins deux chaussettes.

Définition formelle

Le principe équivaut à dire qu’il n’existe pas d’injection de $A$ dans $B$ si $|A| > |B|$.

De manière plus générale, si $k$ chaussettes sont rangées dans $n$ tiroirs, alors il existe un tiroir qui en contient au moins $\lceil\frac{n}{k}\rceil$ .