Principe du pigeonnier

Le principe du pigeonnier (ou principe des tiroirs, ou encore théorème du pigeonnier) est un principe mathématique selon lequel, si $n$ pigeons sont placés dans $m$ trous de sorte que $n>m$, alors au moins un trou contiendra deux pigeons. De manière plus générale , le principe du pigeonnier stipule que si $n=km+1$ objets sont distribués parmi $m$ ensembles, il y aura au minimum un des ensembles qui contiendra au moins $k+1$ objets. Malgré son apparente simplicité, ce principe permet d’établir plusieurs résultats mathématiques importants.

Énoncé

Pour deux ensembles $A$ et $B$ et une fonction $f:A\rightarrow B$, si $|A|>|B|$ alors il existe $x\in B$ tel que $|f^{-1}(x)|\geq 2$. Plus généralement, quels que soient les cardinaux de $A$ et $B$, il existe toujours $x\in B$ tel que $|f^{-1}(x)|\geq \left\lceil {\frac {|B|}{|A|}}\right\rceil$.