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

_{6}= {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.

## No comments:

## Post a Comment