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

1. length and of positive slope. (Going upward right)

2. 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. **