The Reverse Pigeonhole Principle

Everybody (I hope) knows about the pigeonhole principle.

In short it states that:

If and , then there exists at least one with .

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 and , then there exists at least one with .

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 : , that is each such set contains at least elements, then from it follows that:

.

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

On other news my LaTeX script is severly broken and I don’t know why
For some reason it sometimes merges two LaTeX pieces into one because it forgets to echo the last ” after the title (which is impossible, of course..).
Cheers,
Andreas