Pigeonhole Principle
Despite being called the Pigeonhole Principle, the principle itself is the farthest thing from avian. This principle may well be the most intuitive and useful concept I have encountered in this subject. I found it to be so straightforward and obvious that I immediately searched for its applications in my surroundings. I have found it in language, logistics, economics, ecology but most importantly in computer science.
The Pigeonhole Principle simply says that if there are four pigeonholes and five pigeons each of which needs to be put into one of those holes, then after we've put each pigeon into a pigeonhole there must be at least one pigeonhole that has multiple pigeons in it. Generally, the principle can be expressed with the formula below with n as our number of pidgeons and m as our number of pigeonholes.
With the formula above, we can solve problems of varying complexity. It just now depended on distinguishing the pigeons from the pigeonholes.
I remember during the first exam, I was thrilled when I was able to integrate the Pigeonhole Principle and the Product Rule to solve the problem below.
How many people are needed to guarantee that at least 6 were born on the same day of the week (e.g. Monday, Tuesday) and in the same month (perhaps in different years)?
In the problem, the number of pigeonholes can be found using the Product Rule. Since there are 7 days in
a week and 12 months in a year, we have 84 pigeonholes. To get the number of pigeons we can use the formula
above with 6 as our ceil(n/m)
. Therefore, we now have 421 pigeons needed to have at least 6 people
born on the same
day of the week and in the same month.
This just goes to show how each concept, regardless of its complexity can be used to solve problems in elegant fashion.