Stuffing Pigeons into Orifices

Ah, the pigeonhole principle. There’s a good chance you know of this, but in case you haven’t (or you just “forgot” apparently, showing off in front of your friends even though you’ve never heard of it before), here it is, in simple words:

You’re putting items into boxes (pigeonholes). If you have more items than you have boxes, you’ll have at least one box with more than one item. Sounds obvious, doesn’t it? Well, it is.

For example, you have 10 black and 10 white socks in a drawer. If you pick out 3 socks at random, you’re definitely going to have a matching pair. Because even if the first 2 socks are of different colours, the third one will match up with one of them, right?

Let’s extend that sock example. You have 10 black, 10 white, 10 blue, 10 green, 10 red and 10 yellow socks. What’s the maximum number you need to pick out at random this time? The answer is 7, because even if you don’t get a matching pair in the first 6 (i.e., all of them are different colours), the seventh one will match up with one of them.

Okay, now let’s cut to the chase. The pigeonhole principle, though so simple, can be used to prove things that aren’t very intuitive at all. A famous example is proving that at least two people in London have exactly the same number of hairs on their head. This is because the number of hairs on a human head is definitely less than a million (10⁶), and the number of people in London is more than a million. Using the pigeonhole principle, we get the result. (how?)

How about another example? You have a set $\left\{ {a_1, a_2, a_3, \dots, a_n}\right\}$ of integers. Prove that a subset of these can be chosen whose sum is divisible by n.

+Solution!
Take the n+1 integers given by: $0$ , $a_1$ , $a_1+a_2$ … until $a_1+a_2+ \dots + a_n$ .

Two of these integers have a difference that is divisible by n.
(why? hint: how many possible remainders can you get when you divide a number by, say, 2? 3? n?)

Taking the difference of those two integers, we get the answer.

Now, how about some geometry? All points on an infinite plane are coloured either red or blue. Prove that there exists two points of the same colour at any given distance apart.

+Solution!
Place an equilateral triangle on the plane anywhere, with side length equal to the distance given.

Now since there are 2 colours and 3 points, at least two of those three points have to be the same colour (remember the first socks example?).
So, we have found two points of the same colour at that distance apart.

Did you like that one? Too bad. Here’s one last geometry question, which I’m leaving unanswered. It’s tougher than the other one, yes. But go ahead, give it a go.

All points on an infinite plane are coloured either red, green or blue. Prove that there exists a rectangle in the place with all vertices of the same colour.

Stuffing Pigeons into Orifices

Speak up! Let us know what you think.