Principe du pigeonnier

Principe du pigeonnier illustré avec quatre pigeons et trois trous

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$.