This week’s Mathematics topic is - Pigeonhole Principle.
The Pigeonhole principle states that if you have
n boxes and more than
n pigeons then when you put the pigeons into the holes, there must be one hole that contains more than one pigeon.
Seems obvious, but it has a tremendous impact on Mathematics. Many results can be proved using this principle and some of them are frankly pretty cool. Here’s one of my favorites -
In a party of n people, some of them shake hands with others. Prove that there are at least two people with the same number of handshakes
Answer: The minimum number of handshakes is 0 and the maximum is n-1 for an individual. The number of handshakes of any person must be between these two numbers. So if you imagine the numbers are holes and the people are pigeons, then can you apply the Pigeonhole principle? Not quite, because there are n people and n possible numbers.
But observe that if 0 is the number of handshakes for someone, then they have not shaken hands with anyone else. Then there can be no one with n-1 handshakes. Similarly, if someone has n-1 handshakes then there can be no one with 0 handshakes. So, you actually have less than n possible numbers. Fewer holes, more pigeons!! You are done!
This slide by Stanford University - a huge collection of important implications.
Challenge and Thrill of pre-college Mathematics - One of my favorite books that I used to learn the Pigeonhole principle. Has some other interesting topics too.
An Excursion in Mathematics - Again, one of the books I used to learn. Contains many interesting topics.
The page in Brilliant.
In a party of 6 people, every pair is either mutual friends or mutual enemies. (i. e. everyone knows everyone else and is either friend or enemy). Prove that there exist 3 people who are all friends or there exist 3 people who are all enemies. Also, prove that this is not true for 5 people.
This is an interesting problem which I will talk about more in the next week.
Submit your answer by replying to this email.