Planes, manes and pigeonholes

All aboard?

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 N+1 objects to put in N boxes then one of those boxes must contain at least two of the objects.

  

Or if you put M pigeons in N pigeonholes (or envelopes in pigeon-holes) then, if M>N, 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.

Coincidence-generating machine

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.
 You can do better than this. If you have kN+1 objects and N holes, then you must end up with at least k+1 in one. In a previous article about two Ramsey-type games, a key step was the following: if you draw five lines coloured either red or blue, then at least three must be the same colour. Here the two pigeonholes are the choice of colours red and blue. 5=2 \times 2 +1, so one of these colours must have 2+1=3 lines assigned to it.

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 \sqrt{2}=1.41421356\ldots or \pi=3.14159265\ldots, 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.

Advertisements

3 Comments

Filed under Accessible, Maths in Life

3 responses to “Planes, manes and pigeonholes

  1. Your penultimate paragraph touches on whether pi and the square root of two are normal numbers.

    http://en.wikipedia.org/wiki/Normal_number

    http://en.wikipedia.org/wiki/Pi#Open_questions

    Note that at least two digits must appear infinitely often in the decimal expansion of any irrational number (otherwise the expansion would repeat after some point).

    • Thanks for pointing that out. Include me in the ranks of those who “believed that the numbers √2, π, and e are normal”. I should have stated it for any real number, but I wanted especially to avoid those fractions having a finite decimal expansion ending in zeros, like 1.2500000…

  2. Pingback: Mathblogging.org Weekly Picks « Mathblogging.org — the Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s