[Math Talk #3] Pigeonhole Principle and its Usage
![](https://steemitimages.com/640x0/https://i.imgsafe.org/53/53b3599246.jpeg)
Pigeonhole Principle in Mathematics
1. What is Pigeonhole Principle?
First, let's look at the following figure.
![](https://steemitimages.com/640x0/https://i.imgsafe.org/4f/4f4744ac02.jpeg)
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.
If the decimal terminates, it is not our interest; nothing more to prove.
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
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
This implies that ,
is a limit point of
. Now we divide into cases.
If a point
is in
, then we are done; because already we showed zero is a limit point of
.
If a point is in some other interval of the form
, then take
. Since
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!.