TWSB: Holes and the Pigeons that Occupy Them

Today I’m going to talk about the pigeonhole principle and why it’s so freaking awesome.

The principle can be best introduced using an example. Suppose you had (for whatever weird reason) three pigeons that you wanted to put into holes. However, though you have three pigeons, you only have two holes. Can you still put the pigeons in the holes? Yes, of course you can, but there’s a catch: one of the holes will have to contain two pigeons, regardless of how you arrange the birds.

This awesome article entitled “16 Fun Applications of the Pigeonhole Principle” shows some examples of how this idea can be extended to larger numbers—that for any n number of “pigeonholes,” if there exist >n “pigeons,” then there has to be one hole with more than one pigeon in it.

The easiest demonstration of this principle (at least to me) was this one: “For every 27 word sequence in the US constitution, at least two words will start will the same letter.” In this case, the words are the “pigeons” and the letters of the English alphabet are the “pigeonholes.” There are 26 pigeonholes (the 26 letters of the alphabet, obviously) but 27 pigeons. Thus, the n, >n principle applies and therefore you have to have a pigeonhole (letter) that has more than one pigeon (word) “in” it.

Cool, huh? Or rather, FREAKING AWESOME.

The article also talks about another way to understand the principle. It involves math! Go back to the fact that the principle rests on their being n pigeonholes and >n pigeons. For any dataset that doesn’t consist of each datum having the same value, the average is (very) loosely defined as a “middle” value. That is, it’s a value larger than the minimum but also smaller than the maximum.

This is mathematically the same as the n, >n thingy we’re talking about. If we were to have the same number of pigeons and pigeonholes (n and n, respectively), the average value of (pigeons/pigeonholes) would be (n/n) or 1, meaning that on average, 1 pigeon would belong to 1 pigeonhole. However, in cases where there are more pigeons than pigeonholes, the average value of (pigeons/pigeonholes) would be (>n/n), or a value greater than one. What does that mean? It means that on average, more than 1 pigeon belongs to each hole. And because the average is (in general!) smaller than the maximum, it means that there has to be at least two pigeons for one hole.

SNAZZY.

I leave you with one of the examples that’s still a bit crazy for me, even though the way he breaks it down makes total sense.

On New Years at New York’s Time Square, over 820 people will have the same birthday.
There are roughly 300,000 attendees on New Years split over a possible 366 birthdays. The average is 300,000 / 366 = 819.7 people per birthday. The maximum must at least be the average, so there must be a birthday that at least 820 people share.

2 responses

1. […] The first page I randomly turned to in the book had a discussion of the pigeonhole principle (a This Week’s Science Blog topic awhile back), so I have automatic love for that class. The professor is the same dude I had for […]

Like

2. […] Math. The Pigeonhole Principle is one of my favorite math-related things. I’ve done a blog on the actual Principle before, but while we were talking about it today I think I realized why the conclusions you can […]

Like