Posted in Science & Nature

Pigeonhole Principle

If I have three gloves, there must be at least either two left gloves or two right gloves. It is impossible to have one left glove, one right glove and a third glove that is neither left nor right (usually). This logic is called the pigeonhole principle. It is named because of the logic that if you have n pigeons and m pigeonholes where n > m (e.g. 10 pigeons in 9 holes), then at least one pigeonhole must contain more than one pigeon. This is because the biggest spread of the pigeons is putting at least one in each box, but as n > m, there is a pigeon left over and it must go in a box with another pigeon. The pigeonhole principle seems like a basic counting principle, but its implications are quite interesting.

For example, let’s say that your sock drawer is very unorganised and has a mix of black and white socks. What is the minimum number of socks you need to pick out before you get two of the same colour? The pigeonhole principle dictates that when n > m, each “slot” must be filled with more than one item. Here, the slot is colour. As there are two colours (m = 2), you only have to pick three socks out to have a matching pair (n = 3, 3 > 2).

The pigeonhole principle allows us to make seemingly impossible conjectures, such as the fact that a person living in London will have the exact number of hairs on their head as at least one other person living in London. An average human head has about 150,000 hairs and it would be a safe assumption to say that no one would have more than a million hairs on their head (m = 1,000,000). The population of London far exceeds a million (n > 1,000,000), therefore, there must at least two people living in London with the exact same amount of hair on their head. Similarly, if you are in a room with 366 other people, you are guaranteed to share a birthday with at least one person.