Questions involving the pigeonhole principle in Combinatorial Analysis.

The pigeonhole principle states that if $n$ items are placed in $m$ containers and $n>m,$ then one at least one container has more than one item.

A more mathematical definition is that there does not exist an injective function whose codomain is smaller than its domain.

It can be extended to infinite sets by re-writing it in terms of cardinal numbers.

For example, it can be used to show that for any $5$ points on a sphere, some hemisphere must contain $4$ of the points.

history | excerpt history