The Pigeonhole Principle

Ah, my old friend, the Pigeonhole Principle. If not the most interestingly named mathematical principle, then certainly in the top five. I can’t tell you how many times this wonderful tool has gotten me out of a tight jam. However, what exactly is it? And how can it be used? First, the classic example of the principle: given 5 pigeons and 4 pigeon holes, what can we say about the distribution of pigeons?

Pigeons

It should be obvious that no matter how we try to place the pigeons, at least 2 of them will have to share a hole.

Therefore, we can say that, given 5 pigeons and 4 pigeonholes, at least one hole must contain 2 or more pigeons. Let’s restate this more generally:

The Pigeonhole Principle (version 1)

Given k + 1 pigeons and k pigeonholes, at least one hole must contain 2 or more pigeons (in our example above, k was equal to 4). Now let’s apply this idea to a few situations.

First, suppose you attend a party with 13 guests. I guarantee you that at least 2 of you will have a birthday in the same month. Here is how the logic goes.

First, the “pigeons” are the guests at the party. There are 13, or 12 + 1 of them. The “holes” are the possible months in which to have a birthday. There are 12 of them. Hence, by the pigeonhole principle, at least 2 guests must have a birthday in the same month. Presto! Problem solved!

How about this one. If you pick five numbers from the integers 1 to 8, then two of them must add up to 9.

First, we notice that 1 and 8 add up to 9. Therefore, we will pair them together and consider this pair a “hole.” Second, 2 and 7 add up to 9, another hole. Then we have 3 and 6. Finally 4 and 5. In all, there are four such pairs, or four holes.

However, since we must select five numbers (pigeons), by the pigeonhole principle, two of the numbers must be from the same pair (hole). Moreover, these two numbers will sum to 9, since that is how we constructed each pair. (If you don’t believe me, give it a try)

Ok, time to step it up a notch.

Suppose you host a party with 10 guests (this generalizes to “n” guests for the math enthusiasts out there), then at least 2 people have the same number of friends at the party (not to be confused with the SAME friends).

Consider some arbitrary person at the party, say Bob. Bob could have no friends at the party. Or maybe Bob has 3 friends, or 7 friends. He could have up to a maximum of 9 friends at the party, since Bob can’t be friends with himself.

We are going prove this result using a case-by-case analysis.

For case 1, suppose Bob is a pretty shy and he doesn’t know anyone at the party. Now consider another arbitrary person, Alice. Alice could have 3 friends or 7 friends or maybe even 8 friends. However, no matter how popular Alice is, she cannot have 9 friends at the party since she is not friends with Bob. Poor Bob. In fact, since no one at the party is friends with Bob, the maximum number of friends anyone can have is 8.

Now for the principle. We will consider the guests at the party as the pigeons, there are 10 of them. We will consider the possible values for number of friends they have as the pigeonholes. The possible values are 0, 1, 2, 3, 4, 5, 6, 7, and 8. Hence, there are 9 possible values, and by the pigeon hole principle, 2 people must have the same number of friends. Nice!

How about case 2? We suppose that Bob is less shy. Therefore, everyone at the party has at least 1 friend. Now the possible values are 1, 2, 3, 4, 5, 6, 7, 8 and 9 (if everyone has a friend it is possible that some super popular person is friends with everyone at the party). Again, there are 9 possible values and by the pigeon hole principle, 2 people must have the same number of friends.

In either case, the result is true and we are done!

Who would have thought that pigeonholes and pigeons could be related to weekend parties?

Advertisements

1 Comment

Filed under Uncategorized

One response to “The Pigeonhole Principle

  1. I followed until you got to the party. Then I felt too lonely and I lost interest.

    Stop picking on us poor Bobs!

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