I LOVE THE PIGEONHOLE PRINCIPLE ASDFDHFHJDFJFLFSGHHH
So today is the last day of classes before finals. We spent today talking about the Pigeonhole Principle in Discrete 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 reach from the Principle seem so counter-intuitive to people (or at least why it was so to me when I first learned of it).
Let’s take a fairly simple example to demonstrate.
Suppose I have a group of 27 individuals. According to the Pigeonhole Principle, I can state that at least two of these people will have names that start with the same letter of the alphabet. I won’t go into why this is so (you can read my version of the explanation here on my previous PP post, linked above), but even if you’re pretty familiar with it, this still seems a little counter-intuitive, doesn’t it? You think, “wait, how can that possibly be a valid conclusion? There’s no way we can guarantee that!”
Where does this aversion to this conclusion come from?
Well, originally for me, I realized it stemmed from how I actually interpreted the conclusion itself. I always automatically interpreted the conclusion as claiming, in the case above: “there will be at least one name that starts with every letter of the alphabet in my group of 27 people.”
Which, of course, is not what the conclusion says at all. There is no claim made about the dispersion of the number of names per letter other than the fact that at least one letter will be the first letter in two names. I could have the case where I have a single name beginning with each letter A-Y, and then two names that begin with the letter Z. That still fits with the conclusion. However, I could also have NO names that start with a letter A-Y and have all 27 start with the letter Z. That’s valid, too. All the conclusion tells us is that at least one letter will begin two names. It doesn’t say that all the letters have to start a name (that is, it doesn’t say that all “pigeonholes” actually have to be utilized).
Now that I’ve typed that out, it seems like a really stupid reason for having trouble understanding the Principle, so it’s probably just me who has this issue. But anyway.
Isn’t this Principle COOL either way?!
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.
Eigenblogger 