The Pigeonhole Principle

Pigeons in holes.

Pigeonhole Principle, or known as Dirichlet's Box Principle states that, given m numbers of pigeon in n numbers of pigeonholes, for m = n, then each pigeonhole must be occupied. If any one of the holes is empty, then at least one hole is occupied with more than 1 pigeons.

Although the Pigeonhole Principle seems to be intuitive, it can be used to demonstrate possibly unexpected results, such as this:

Given at any time, there must be at least 2 people in London with the same, exact number of hairs on their heads.

Explanation: A typical head of hair has around 150,000 hairs. It's reasonable to assume that no one has more than 1,000,000 hairs on their head (m = 1 million). There are more than 1,000,000 people in London (n > m), thus there must be at least two people with the same number of hairs on their heads in London.

The probabilistic general formula of the Pigeonhole's Principle:

No comments:

Post a Comment