The Reverse Pigeonhole Principle

Everybody (I hope) knows the pigeonhole principle.

In short it states that:

If \(f: N \to M\) and \(n:= \left | N \right | \geq \left | M \right | =: m\), then there exists at least one \(m_0\) with \(\left | f^{-1}\left ( m_0 \right ) \right | \geq \left \lceil \frac {n} {m} \right \rceil\).

For example, if we have n + 1 pigeons in only n pigeonholes, there is (at least) one pigeonhole that has at least two pigeons inside (thus the name).

One thing I haven’t seen mentioned anywhere yet (at least not with this name) is the reverse pigeonhole principle:

If \(f: N \to M\) and \(n := \left | N \right | \geq \left | M \right | =: m\), then there exists at least one \(m_0 \in M\) with \(\left | f^{-1}\left ( m_0 \right ) \right | \leq \left \lfloor \frac {n} {m} \right \rfloor\).

Again an example: if we have n + 1 pigeons (it’s valid up to 2n - 1) and n pigeonholes, then there exists (at least one) pigeonhole with at most one pigeon in it.

The proof for the reverse principle is simple:

Assume that for all \(m_0 \in M\): \(\left | f^{-1}\left ( m_0 \right ) \right | > \left \lfloor \frac {n} {m} \right \rfloor\), that is each such set contains at least \(\left \lfloor \frac {n} {m} \right \rfloor + 1\) elements, then from \(\frac n m - 1 < \left \lfloor \frac {n} {m} \right \rfloor\) it follows that:

\[ n = \sum_{m_0 \in M} { \left | f^{-1} \left ( m_0 \right ) \right | \geq m \left ( \left \lfloor \frac {n} {m} \right \rfloor + 1 \right ) > m \cdot \frac n m = n } \].

This clearly is a contradiction, so the original assumption must have been wrong, which proves the reverse pigeonhole principle.

I haven’t seen this written down anywhere before and it’s useful to keep it in my mind on its own because it shortens some arguments, so I hope this might help someone :-)

Cheers,
 Andreas