I was recently travelling on a budget flight with a friend, with no assigned seating. Walking up to the queue, we wondered whether we would be able to sit together. As people joined behind us, my friend, who whole-heartedly detests maths in any disguise, pointed out that we certainly could. To be so full-up to mean that we couldn’t, each row of three would need at least two people sitting in it. Since we could see from the queue that we had more than a third of the passengers still left to board after us, then as long as we weren’t trampled in a boarding stampede, we could certainly sit together.
This was actually a subconscious application of the pigeonhole principle, one of the most intuitive theorems that mathematicians use. It states that if you have objects to put in boxes then one of those boxes must contain at least two of the objects.
Or if you put pigeons in pigeonholes (or envelopes in pigeon-holes) then, if , at least one of the holes has at least two pigeons. So far, the type of maths you wouldn’t be shocked to see explained on television by a primary-coloured puppet.
To apply this ‘theorem’ the plane-boarding case, imagine the plane is holding its full capacity of 120 passengers. Let’s say that the steward calls out the names of 41 passengers to debark, including my friend and I (or if you prefer, just rewind time until just before the moment we got on). Then by the pigeon-hole principle, because there are only 40 rows, at least two of these people must have left fromthe same row of three. This leaves some pair of seats clear if the other 39 are to re-embark after the two of us.
Plenty of free pairs of seats, in each row of three, are still empty after 79 people have boarded (we may need to ask someone to shuffle along the row if they chose to sit in the middle seat).
Here it’s easy to imagine the worst-case scenario after 40 people leave, one exiting each row, leaving no free pairs. But then one more has to leave, freeing up another free seat in the same row. By chance, you should expect more than one empty pair remaining (in reality, with different numbers, there were many). However, even if someone were antagonistically trying to keep us separate by rearranging the seating, they would have failed.
This extreme behaviour of the worst-case scenario can happen naturally. While commuting by bus each morning in London I observed that, on the upper deck, each person would try to sit in an empty double seat whenever possible, to avoid sitting next to anyone else. This is pretty typical behaviour. What did surprise me though, was that I noticed: the first person to come upstairs, who couldn’t find a row of their own, each day had an uncanny habit of choosing to sit down next to me (even though it was always different people). They seemed to stop choosing me first when, after a while, I started wearing headphones.
The pigeonhole principle is like a trivial coincidence-generating machine. If you’ve been to the gym ten times last year, then at least two times were on the same day. Here are some famous examples:
- There are at least two people in London with equi-hirsute manes: that is, with the same number of hairs on their head.
- It’s a frequently stated fact that if you have 23 random people in a room, then there’s a better than fifty percent chance that two share a birthday. This number perhaps surprises our non-probabilistic intuition because to guarantee two share a birthday we need 367 people (days in a leap year plus one).
- Sock-picking and hand-shaking can be found on Wikipedia, to avoid any further overlap here.
If you want to have a go at some harder examples, here’s a problem sheet from MIT.
One, two, skip a few…
You can go still further: if you have infinitely many objects and only finitely many holes, one of those holes must have infinitely many objects. For instance, in the
non-repeating decimal expansion of any irrational number such as or , at least one of the 10 digits must occur infinitely often. I think It is unknown whether each digit from 0 to 9 repeats infinitely often in those two. , but that would probably require a harder proof.
If you know about the different types of infinity (recently explained to the British public on radio by Matt Parker, the stand-up mathematician, on More or Less), you can continue along a similar vein with countably many pigeonholes, and uncountably many pigeons. Putting uncountably many pigeons in any one of your pigeonholes undoubtedly contravenes an even larger infinity of animal-cruelty laws—don’t even think about it.