The pigeonhole principle

The pigeonhole principle is one of those which people believe one of the most faltoo principles in Combinatories.

Imagine that 3 pigeons need to be placed into 2 pigeonholes. Can it be done? The answer is yes, but there is one catch. The catch is that no matter how the pigeons are placed, one of the pigeonholes must contain more than one pigeon.

The logic can be generalized for larger numbers. The pigeonhole principle states that if more than n pigeons are placed into n pigeonholes, some pigeonhole must contain more than one pigeon. While the principle is evident, its implications are astounding. The reason is that the principle proves the existence (or impossibility) of a particular phenomenon.

The pigeonhole principle (more generalized)

There is another version of the pigeonhole principle that comes in handy. This version is “the maximum value is at least the average value, for any non-empty finite bag of real numbers” (thanks Professor Dijkstra)

Do not let the math jargon intimidate you. The idea is intuitive. For typical data sets, the average is the “middle” value, so clearly the maximum should be at least as big. While this version sounds different, it is mathematically the same as the one stated with pigeons and pigeonholes. Let’s see how the two are connected.

Consider again the problem of stuffing pigeons into pigeonholes and consider the average. If we have more than n pigeons and n pigeonholes, then the average value of (pigeons / pigeonholes) is greater than one. This means the maximum value should also be larger than one. In other words, there has to be some value of more than one pigeons per pigeonhole. Indeed, the two versions are about the same idea.

Now see the power of idea

1 .If you pick five numbers from the integers 1 to 8, then two of them must add up to nine.

Every number can be paired with another to sum to nine. In all, there are four such pairs: the numbers 1 and 8, 2 and 7, 3 and 6, and lastly 4 and 5.

Each of the five numbers belongs to one of those four pairs. By the pigeonhole principle, two of the numbers must be from the same pair–which by construction sums to 9

2. On New Years at New York’s Time Square, over 820 people will have the same birthday.

It will now be useful to use the second version “the maximum must at least be the average.”

There are roughly 300,000 attendees on New Years split over a possible 366 birthdays. The average is 300,000 / 366 = 819.7 people per birthday. The maximum must at least be the average, so there must be a birthday that at least 820 people share.

3. Imagine a certain college has 6,000 Indian students, at least one from each of the 30 states/UT. Then there must be a group of 200 students coming from same state.

Again, we invoke the second version that “the maximum must at least be the average.”

The average is 6,000 / 30 = 200 students per state. The maximum must at least be the average, so there must be a state where 200 students share in common.