Pigeonhole principle

Sei \(f: A \rightarrow B\) eine Abbildung endlicher Mengen und \(k \in \mathbb{N}\), so dass gilt:

\begin{align*} \vert A \vert > k \cdot \vert B\vert \end{align*}

So gilt

\begin{align*} \exists b \in B : \vert f^{-1}[b] \vert > k \end{align*}