Pigeon-Hole Principle

My lecturer during my undergraduate studies taught me this principle once. My first reaction was, to be honest: 

Yeah. Okay. So?

I mean, seriously.

If there are more pigeons than pigeonholes, then some pigeonholes must contain two or more pigeons.

Uh. Of course it does. I know that.
Is this supposed to be useful for something?

This principle is probably one of the most simple-minded, obvious, right-in-your-face principles I’ve ever encountered in Mathematics.  Sure, Math is full of obvious and right-in-your-face theorems, axioms and principle. For instance, it is possible to draw a straight line from any point to any point, the whole is greater than the part, and many more.  I mean, they are so obvious it makes you question why people bothered to write down these things. Needless to say I had a good laugh during my Plane Geometry class. Gradually though, my obnoxiousness level went down a bit and I learnt that these facts were written down not because they are mind-boggling discoveries, but because it is important for us to put down a base. An agreement. Something we can move forward from. Let’s be honest, if Euclid did not wrote the definition of a line before, we probably never bother to think that only one line can be drawn through 2 points. Knowing Mathematics and crazy, anal people in it, at some point someone definitely is going to make it a problem.

One thing that sets Pigeon-Hole Principle apart from those axioms is while they are only meant as a basic understanding; Pigeon-Hole Principle can actually help you to solve very complicated problems. Seriously, when I first read the problems never in my mind I thought they are solvable with only this principle. Some of the problems are as follows.

1)    In New York City, there are two non-bald people who have the same number of hairs on their head.

This is actually quite simple. It is easy to think that there are so many strands of hair on a human’s head that we jump into conclusion that it’s impossible for two different people to have the same number of hair. But as many as human hairs are, it is nothing compared to the number of human residing in the great great New York City.

The human head can contain up to several hundred thousand hairs, with a maximum of about 500,000. In comparison there are millions of people in New York City. Consequently, at least two of them must share the same number of hairs, if not more.

2)   Prove that for any positive integer n, there are a multiple of n whose digits only contains “1” and “0”.

This problem was given by my current professor.  At first, I cannot make any connection from this to Pigeon-Hole Principle. But apparently it is not that complicated!

Consider 6 and integer modulo 6, which is a set of remainders if you divide any integer with 6.

Z₆ = {0, 1, 2, 3, 4, 5}

Now let’s take 7 integers whose digits are all 1; 1, 11, 111, 1111, 11111, 1111111. Based on Pigeon-Hole Principle, there must be at least 2 integers congruent modulo 6 to the same number, which are 11 and 11111.

 11111 = 1851.6 + 5

       11 =       1.6 + 5

Now we just have to subtract 11 from 11111.

11100 = 1850.6

And voila!

The proof for n was submitted for my assignment though, and I didn't write a copy of it since it was so simple; once you figure it out with any given integer you can do it with n.