The Pigeonhole Principle
Introduction
Picture the scene. You are in a small village, and there are 7 pigeons on the island. Of course, they are enjoying their time in the village (it seems), but how about when the sun relegates itself below the sea and the sands: when the stars come out?
There are some pigeonholes on the ground for them to rest and protect themselves so they don't become a midnight snack - upon further inspection, however, you find there is only 6. The soil is too rough for you to create another one, so, naturally, what happens?
Two pigeons enter one pigeonhole. Of course - but what does this have to do with maths?
Enter the pigeonhole principle.
What is the pigeonhole principle?
If you weren't caught up in trying to find a loophole to the analogy I had laid out, you'll find the pigeonhole principle really helps - the pigeonhole principle is a theorem used in mathematical fields like data science, discrete maths, and combinatorics.
Essentially, it that states that if you organise n items into m containers, and n > m... at least one container will hold two or more of these items.
It stems from basic combinatorics and replacement probability (and maybe common sense); however, it goes a lot deeper than what meets the eye in its applications, which to me is what makes it so elegant.
A proof by contradiction of the pigeonhole principle
The pigeonhole principle is quite simple to wrap your head around conceptually, which might coax you into thinking the proof will be something as diabolical as trying to defend Jack the Ripper in a court of law...
...but it assuredly isn't. Imagine that you are given that there are n items and m containers, and n>m.
If the pigeonhole principle was false, then at most there would be 1 item per container.
This would mean there are m items and m containers, which implies n=m.
However, this contradicts what was given!
As a result, the pigeonhole principle is a FACT.
1. Unwishful thinking
The point of the pigeonhole principle in a lot of its applications is that you have to imagine what happens given the worst possible luck in trying to make it happen.
That may not make sense at first, but imagine you have a deck of cards (INCLUDING joker cards) and you'd like at least two cards of the same suit.
The question is: how many cards need to be drawn from the top of the deck to GUARANTEE success?
HINT: someone has rigged the shuffling of these cards such that it is really hard to achieve this. What would they do?
Click for solution
If someone else was to rig the cards to make it as hard to achieve your goal as possible, they would maximise the amount of cards you have to draw, which would require you to exhaust every single suit, including the joker.
So imagine... heart, spade, club, diamond, joker... what comes next?
The fact is, it doesn't matter - we know the next card is going to be one of these, so the answer is 6.
2. Application to geometry
Let's now think about something a little more abstract than a deck of cards.
Suppose you have a 1cm by 1cm square and you have to pick 5 points on the square... how do you know the maximum distance between the closest pair of points will be sqrt(2)/2 cm?
Click for solution
Think unwishfully again - maximise the distance with the first 4 points by making sure they're all as far as can be (i.e. on the corners of the square.
Now you need one more point. There's two ways this could go down...
1. You place the fifth point in the middle and the corner points alongside the centre point make 4 pairs each which are all the joint closest pair. Their distance, according to the Pythagorean theorem, IS sqrt(2)/2 cm, so the rule holds.
2. Imagine the same scenario except the point is moved around. This increases the distance between some pairs but also DECREASES some such that the distance is LESS than this, so again, the rule holds!The learning curve
The way I initially discovered the pigeonhole principle was actually quite recent. It could be that in the back of my mind I've known of this principle by name before I had object permanence, but alas: under the clutches of my own heuristics, we'll assume this is something that was new to me a few months ago...
It was the day of the BMO1 (November 20th, 2024) - I had no idea what to expect, given this was my first ever dip in the pool of Olympiad problems within a live exam. Three and a half hours...but I'm still standing...
...or not.
This is a commentary on the BMO1 2024 Q6 from a contestant's perspective. I would recommend trying it first.
Come Question 6 and I'm completely baffled - a mysterious fellow Bjork has 64 sugar cubes of various colours and wants me to ascertain to her that she CAN arrange them such that she can make equidistant disjointed pairs...
The mystery of the context within this question reflects how mysterious this was to me. My mind was at 3-dimensional vectors and grids and aleatory geometrical assertions that ultimately took me nowhere; my next instinct was then to just guess a case whereby this would work and hope it would get me somewhere.
Nothing.
The problem left me at a dead end - I had left it at that with that problem, proofread my other answers, and called it a day.
It wasn't until a few days later that the solutions were uploaded on the UKMT website - in light of this information, I looked at question 6 as this was the most unfamiliar to me.
I understand it now.
The solution says to use the extended pigeonhole principle to prove it with a smaller cube; in truth, this to me proved such an elegant solution that I now think about the pigeonhole principle in circumstances in such a way that even Bjork herself couldn't parallel...