Pigeonhole Principle and Miscellaneous Applications (2)
[1]
Continuing our discussion of pigeonhole principle from Math Talk #3, I will post some miscellaneous applications of Pigeonhole principle.
1. Partitioning the subset of Natural numbers
1-1. Concerning the set 
Problem 1. - [2]
Given any integers among
, show that two of them are relatively prime. Show that the result is false if we choose
integers.
Solution 1.
Partition the set into
subsets of the form
Then by Pigeonhole principle, choosing integers forces us to pick two (i.e. all ) elements in single partition. Since consecutive integers are relatively prime, there is at least one pair of integers which are relatively prime.
If the number reduces to , then clearly choosing
(the set of even numbers) will be the counterexample.
Problem 2. - [3]
Given any integers among
, show that one of them is divisible by another. Show that the result is false if we choose
integers.
Solution 2.
By prime factorizing theorem for positive integers, every positive integers can be expressed as
where and
is odd. First, make
pigeonholes as follows.
In other words, every odd number less than is partitioned into singleton sets. Now,
since . Since there are
distinct odd numbers, among
numbers, there should exist two
having same
by pigeonhole principle. Then we can express as
depending on the magnitude of .
If the number reduces to , then clearly the set of all odd numbers
would be the counterexample.
Problem 3. - [4]
Let and
where
are all distinct elements in
. Prove that
Solution 3.
First, partition the whole set into two disjoint subsets
Now fix index , and consider
.
are all smaller than
. So at least
So are all elements of the latter set
. Since
those elements of the form
are all distinct, so that by Pigeonhole principle, they occupy exactly one element in
.
Since and all
elements of the form
are distinct, by Pigeonhole principle, they occupy exactly one element in
. So
2. Erdös - Szerkes Theorem
The original theorem is as follows.
Theorem.
For given any sequence of distinct real numbers with length at least
contains a monotonically increasing subsequence of length r or a monotonically decreasing subsequence of length s.
Proof. - [5]
First denote as
. Also for each
, we assign a pair
such that
Now we seek some properties of this pair. Since all numbers are distinct,
as well as
So, for any case.
If number of possible values of is less than
and number of possible values of
is less than
, then in total, there will be at most
number of
pairs. This contradicts to the fact that all pairs are distinct (which in total
), so by Pigeonhole principle, either
or
for some index .
2-1. Visualization of Theorem
Let's say we have distinct real numbers,
Now in 2D plane, math each number
to the point
. Then we can always find a polygonal path either
length
and of positive slope. (Going upward right)
length
and of negative slope. (Going downaward right)
Example
The case when . Randomly generate
points.
[6]
We can see that it consists of 5 points, which is of positive slope polygon path.
3. Conclusion
Pigeonhole Principle can be a powerful tool in discrete mathematics and in any field concerning some counting.
4. Citations
[1] http://cpptruths.blogspot.com/2014/05/the-pigeonhole-principle-in-c.html (only image is used)
[2] http://web.archive.org/web/20120124185755/http://math.mit.edu/~rstan/a34/pigeon.pdf Problem 7
[3] http://web.archive.org/web/20120124185755/http://math.mit.edu/~rstan/a34/pigeon.pdf Problem 8
[4] http://web.archive.org/web/20120124185755/http://math.mit.edu/~rstan/a34/pigeon.pdf Problem 13
[5] Seidenberg, A. (1959), "A simple proof of a theorem of Erdős and Szekeres" (PDF), Journal of the London Mathematical Society, 34: 352, doi:10.1112/jlms/s1-34.3.352.
[6] https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem (only image is used)
**Solutions to the problems are made by myself. **