The Pigeon Hole Principle
If a set of m elements were partitioned into n subsets, with m > n, then there is a subset containing more than one elements.
As an example, suppose you try to put 11 pigeons into 10 pigeon holes, then at least one pigeon hole will have at least 2 pigeons. A simple intuitive statement, but difficult to prove mathematically (proven by Dirichlet). For our purpose, let's take its truth value intuitively.
It has many applications in mathematics. My favorite is to show that now there are two people living on Earth born in the same year, month, day, ... down to the second. The power of this theorem is that you don't need to go out to ask every single person. Last year, the population on Earth reach 6 billion. Assume the oldest person is 150 years. Then there are about 4.7 billion seconds in the past 150 years. If you see each second as a pigeon hole, then at least two people will be put into the same second. In other words, at least two people were born in the same year, month, day, hour, minute and second.
Another example involves socks that most of us probably heard about. A bag contains 5 red, 7 blue, 6 white, 8 brown and 2 black socks. If you take out one sock at a time without looking and without placing it back to the bag, how many do you have to take in order to guarantee a pair of the same color? Sounds complicated. But the pigeon hole principle applies here. Imagine each color is a pigeon hole, you want to know how many socks you need in order to guarantee a hole will contain two. Since there are 5 different colors, you need 6 socks to fulfill the goal.
Using the pigeon hole principle, it is not difficult to show that there are two people in New York City with the same number of hair. Andrew Wiles applied the pigeon hole principle to an infinite number of sets in his proof of the Fermat's last theorem. We can find many more similar examples. I will leave two for the readers to think about.
(1) If you put 5 points in a 2´2 square, show that there are two points that are less that Ö2 apart.
(2) If we paint the surface of a sphere point by point and more than half of the points are painted, show that there is at least one pair of antipodal points that are painted. (antipodes are a pair of points at the opposite end of a diameter in a sphere)