Pigeonhole Principle in Mathematics

1. What is Pigeonhole Principle?

First, let's look at the following figure.

There are five pigeons, and four holes. Suppose we want to locate each pigeons into holes. Then since the number of holes is strictly less than the number of pigeons, there exist at least one hole which contains more than 1 (so, at least 2) pigeons. This is the basic concept of Pigeonhold principle. More formally, it can be stated as follows.

Pigeonhole Principle.

If items are put into containers, with then at least one container must contain at least items.

Well the proof is simple. By division algorithm of integers, where (it can not be zero, since ). So if all the containers contain at most items, then which is contradiction.

2. Its Usage?

Well you can think this is so trivial that no body will ever use it, but actually it is really useful as well as important principle in mathematics. Here are some examples.

2-1. Decimal Expansion of Rational Number

We already learned in Elementary school (well, at least without a proof) that every positive rational number is either terminating decimal or repeating decimal. This can be proved very easily by Pigeonhole Principle.

1. If the decimal terminates, it is not our interest; nothing more to prove.

2. Suppose the decimal does not terminate. We have to formulate our goal. Pick any positive rational number where .

Since we assumed that decimal does not terminate, there exist a sequence such that

with the fact that .

Step 1. By division algorithm of integers, for some quotient and remainder . Then

Step 2. Now . Again by division algorithm of integers, for some suitable quotient and remainder. Now

Step 3. Inductively define the quotient and remainder by for . Then by pigeonhole principle, there should exist two indices such that and (because ). After that point (-th step), the division algorithm is just the repetition of what we did after the -th step.

Step 4. Let be the smallest index such that for some . surely exists by Well-Ordering Principle of natural numbers. Also pick the smallest index among such and denote it as . Then the final answer would be

Not only we've showed the desired result, but actually we've constructed the period with the help of Well Ordering Principle!

2-2. Dense subset of Real numbers

Pick any irrational number . Then consider the set

which is the collection of all fractional part of integer multiple of . Since it is the fractional part, . Now the question is

Is dense in ?

Well, it seems correct, because product between irrational number and integer is also irrational. Let's prove it using Pigeonhole principle.

First, let be given. Pick any natural number such that . Then consider

If , then , so it is clear that all elements are distinct. If we divide into equal intervals

then by Pigeonhole Principle, any two distinct elements are in the same subinterval. Then it is clear that

as well as

for some integer . So,

This implies that , is a limit point of . Now we divide into cases.

1. If a point is in , then we are done; because already we showed zero is a limit point of .

2. If a point is in some other interval of the form , then take

. Since , we get the fact that such points are also limit points of .

So we've constructed a countable subset of , which does not contain any rational numbers (except zero)!.

3. Conclusion

Well, the concept of pigeonhole principle is quite simple, but the usage is very broad and also deep. Combined with elementary analysis, we can deduce some useful facts about dense subset using pigeonhole principle!.