The pigeonhole principle

What is the pigeonhole principle?

The pigeonhole principle states that, given two natural numbers n and m with n > m, if n items are put into m pigeonholes, then at least one pigeonhole must contain more than one item.

I was thinking like: why pigeons? Who made up this thing?

This is a photograph I took near Charminar, Hyderabad.

Look how the pigeons are sitting in such a disciplined way!!!

Now I know why the pigeonhole principle chose pigeons for illustrating the principle.

Here are some more interesting facts about the pigeonhole principle:

Although the pigeonhole principle may seem to be intuitive, it can be used to demonstrate possibly unexpected results. For example, there must be at least two people in London with the same number of hairs on their heads. A typical head of hair has around 150,000 hairs; it is reasonable to assume that no one has more than 1,000,000 hairs on his head (m = 1 million holes). There are more than 1,000,000 people in London (n is bigger than 1 million objects). If we assign a pigeonhole for each number of hairs on a head, and assign people to the pigeonhole with their number of hairs on it, there must be at least two people with the same number of hairs on their heads.

Uses and applications

The pigeonhole principle often arises in computer science. For example, collisions are inevitable in a hash table because the number of possible keys exceeds the number of indices in the array. No hashing algorithm, no matter how clever, can avoid these collisions. This principle also proves that any lossless compression algorithm that makes at least one input file smaller will make some other input file larger. (Otherwise, two files would be compressed to the same smaller file and restoring them would be ambiguous.)

Forgive me for the big quote. I thought you might be interested.