The pigeon hole principle

The pigeon hole principle

The pigeon hole principle is a counting argument stating something as simple as “if you have n items which are to be put into m < n boxes then there is at least 2 items in one of the boxes”. My first comment on that was “well duh!”, that is obvious, but it can actually be used to prove some less intuitive things.

So an example if you have 10 balls which are to be put into 9 boxes then at least 1 of the boxes contains at least 2 balls (unless you drop one of them…). But what can we use it for. I will show one of my favourite examples of it which I do not find intuitive at first glance.

Hand shaking at a party

There are N people at a party some of them have been shaking hands, and some haven’t. If two persons shake hands then it counts as both of them have shaken hand with one person. So there is no distinguishing who took the initiative to the greeting. Then we have the following proposition:

Proposition: At least two people have shaken hands with the same number of people.

Proof: A person can shake hands with between 0 and N-1 people since you cannot shake hands with your self. That is N possibilities. If one person has shaken hands with everyone else, then there is no one who hasn’t shook hands with no one. And the other way around. So 0 and N-1 possibilities are mutual exclusive. So we are down to N-1 possibilities of people each person can shake hands with.

So if there are N people and N-1 possibilities to the number of people each person can shake hands with then at least 2 people have shook hands with an equal amount of people

QED

Sums of arbitrary sets

Proposition: Choose a set A of 10 random integers between 0 and 100. Then it will be possible to make two different sums of elements from A which are the same.

Proof: The number of “holes” is the possibilities to make a sum of the 10 numbers is 1001 since we can go from 0 to 10*100=1000.

So if we can show that the number of sums we can make from the 10 numbers is larger than 1001 we have proven that there are two equal sums. We haven’t found the two sums, but we have proven that they exist.

A number can be present in the sum or not, which means we have 2 options. We have that for each of the 10 numbers, so that means we have 210=1024 options to make a sum of the elements of A. This is larger than 1001 and thus there must exists two sums which are the same.

QED

This proof is a good illustration that the argument can be used to prove existence of a certain property, but given a set specific set A the proof does not help us with actually finding the equal sums. Unlike many of the other proof techniques we have dabbled in earlier.

Wrapping up

Other places I have seen the pigeon hole principle used is especially in computer science where two applications has been to prove that hash tables will have collisions and that loss less compression doesn’t work on all files.

Dijkstra wrote a short note on the underserved status of the pigeon hole which was pretty insightful. Chai Wah Wu has made some notes on the Generalized pigeonhole principle where he states several other statements which are a consequence of the pigeon hole principle. Last but not least I found a 12 page pdf file on the pigeon hole principle which is worth a read.

The pigeon image I used here is attributed John Bostock. The derivative work I made of the image is of course shared under the creative commons license as well.

Posted by Kristian

Leave a Reply