pigeonhole principle

The pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item.

For example, with 367 people, at least one pair must share a birthday (leap year considered).

Implication in Computing

The pigeonhole principle implies that all lossless compression algorithm will make some input larger. Otherwise the set of input will map to a smaller set of output.

It also implies that any hash functions with more input than outputs will necessarily have collisions.