The Pigeonhole Principle

 

Imagine that two people are playing “Paper, Rock, Scissors” and one wins the first game.  Then the loser chimes in and declares “best two out of three!” This is a common phrase heard in win/lose games and it utilizes a very important and subtle principle known as the pigeonhole principle. We know that two out of three works because given two options (win/lose) and three rounds, one person must win at least one more time than the other. Let us look at this in another context.

rock__paper__scissors__by_sweetnminty-d5cimzn

Suppose a man is getting dressed in the dark. He opens his sock drawer which has a dozen black socks and a dozen blue socks all unpaired. How many socks must he pull out to guarantee that he will have two of the same color? How many socks must he pull out to guarantee that he will have two black socks? Before we answer this question, let us look at the pigeon hole principle, also known as the Dirichlet drawer principle.

 

Pigeonhole Principle: Suppose I have k+1 objects to put into k slots for some positive integer k \ge 2. Then there must be at least one slot that has at least two objects in it.

Proof: Suppose that there is no box with two objects. Then each box must have exactly one object. Since there are k boxes we must have k objects, a contradiction.

 

With the principle explicitly stated let us return to the sock dilemma. Let us treat the color of the socks as slots. So there are two slots. Immediately by the pigeonhole principle we conclude that he needs one more than two, that is three, socks to guarantee two of matching color. But if he wants two black socks the story is a bit different. Since it is possible that he can pull out all 12 brown socks first, we see that there are 13 slots (12 brown and one black). Hence, we conclude he must pull out 14 socks to guarantee that he will get two black socks.

6a0120a55c9cd1970c01a3fd42b019970b-800wi

It is clear that the pigeonhole principle uses a sort of common sense logic. But this concept has many forms that are subtle but almost always present. Things like knowing that 13 people implies that there are at least two that have a birthday in the same month. Or 366 people to conclude that two of them have the same birthday, excluding leap year (don’t get this confused with the birthday problem which is a slightly different concept).

Some mathematical implications include things like the following. If we have a list of d+1 consecutive integers then there are two integers that have exactly the same remainder when divided by d. The last and perhaps one of the most important uses of the pigeonhole principle sparked an entire field of study. But for this we need the generalized pigeonhole principle.

 

Generalized Pigeonhole Principle: Suppose N objects are placed into k slots. Then there is at least one slot that has at least \lceil N/k \rceil .

 

Now suppose there is a group of six people where each pair of individuals consists of two friends or two enemies. We’d like to know that there are either three mutual friends or three mutual enemies in the group. To do this let A represent one of the six people. By the generalized pigeonhole principle, since there are five people and two slots we can conclude out of the remaining people, either three are enemies of A, or three are friends of A since \lceil 5/2 \rceil = 3. Now without loss of generality suppose persons B, C, and D are friends of A. If any two of these three individuals happen to be friends then A along with those two form a set of three mutual friends. If none of B, C, and D are friends then they form a set of three mutual enemies.

main-qimg-652c9c992d9465e4fa914275c5efc101

This problem is a famous example of the anthem of Ramsey Theory. This is an important part of combinatorics named after Frank Plumpton Ramsey, and attempts to answer questions of the form “how many elements of some structure must there be to guarantee that a particular property will hold?”

It is often the case in mathematics that a theorem can be phrased in many other ways that make it useful in many different fields. The pigeonhole principle is just one of many examples of this fact.

Advertisements

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