# Pigeonhole Principle and Miscellaneous Applications (2)
**[1]**
<center> <img src = "https://i.imgsafe.org/6d/6dbb3ad7b5.gif" height = "300" width = "400"/> </center>

Continuing our discussion of pigeonhole principle from [Math Talk #3](https://steemit.com/math/@mathsolver/math-talk-3-pigeonhole-principle-and-its-usage), I will post some miscellaneous applications of Pigeonhole principle. 

## 1. Partitioning the subset of Natural numbers

### 1-1. Concerning the set <img src="http://latex.codecogs.com/gif.latex?\left\{&space;1,&space;2,&space;...,&space;2n&space;\right\}" title="\left\{ 1, 2, ..., 2n \right\}" align = "center"/> 

**Problem 1.** - **[2]**
Given any <img src="http://latex.codecogs.com/gif.latex?n&plus;1" title="n+1" align = "center"/> integers among  <img src="http://latex.codecogs.com/gif.latex?\left\{&space;1,&space;2,&space;...,&space;2n&space;\right\}" title="\left\{ 1, 2, ..., 2n \right\}" align = "center"/>, show that two of them are relatively prime. Show that the result is false if we choose <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> integers. 

**Solution 1.** 
Partition the set <img src="http://latex.codecogs.com/gif.latex?\left\{&space;1,&space;2,&space;...,&space;2n&space;\right\}" title="\left\{ 1, 2, ..., 2n \right\}" align = "center"/>  into  <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> subsets of the form

<center> <img src="http://latex.codecogs.com/gif.latex?\left\{&space;1,&space;2&space;\right\},&space;\left\{&space;3,&space;4&space;\right\},&space;...,&space;\left\{&space;2n-1,&space;2n&space;\right\}" title="\left\{ 1, 2 \right\}, \left\{ 3, 4 \right\}, ..., \left\{ 2n-1, 2n \right\}" /> </center>

Then by Pigeonhole principle, choosing <img src="http://latex.codecogs.com/gif.latex?n&plus;1" title="n+1" align = "center"/> 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 <img src="http://latex.codecogs.com/gif.latex?n" title="n" />, then clearly choosing <img src="http://latex.codecogs.com/gif.latex?\left\{&space;2,&space;4,&space;6,&space;...,&space;2n&space;\right\}" title="\left\{ 2, 4, 6, ..., 2n \right\}" align = "center"/> (the set of even numbers) will be the counterexample. 

---
**Problem 2.** - **[3]**
Given any <img src="http://latex.codecogs.com/gif.latex?n&plus;1" title="n+1" align = "center"/> integers among  <img src="http://latex.codecogs.com/gif.latex?\left\{&space;1,&space;2,&space;...,&space;2n&space;\right\}" title="\left\{ 1, 2, ..., 2n \right\}" align = "center"/>, show that one of them is divisible by another. Show that the result is false if we choose <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> integers.

**Solution 2.**
By prime factorizing theorem for positive integers, every positive integers can be expressed as 

<center> <img src="http://latex.codecogs.com/gif.latex?k&space;=&space;2^m&space;\times&space;\ell" title="k = 2^m \times \ell" /> </center>

where <img src="http://latex.codecogs.com/gif.latex?m&space;\geq&space;0" title="m \geq 0" align = "center"/> and <img src="http://latex.codecogs.com/gif.latex?\ell" title="\ell" /> is odd. First, make <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> pigeonholes as follows. 

<center> <img src="http://latex.codecogs.com/gif.latex?\left\{&space;1&space;\right\},&space;\left\{&space;3&space;\right\},&space;\left\{&space;5&space;\right\},&space;...,&space;\left\{&space;2n-3&space;\right\},&space;\left\{&space;2n-1&space;\right\}" title="\left\{ 1 \right\}, \left\{ 3 \right\}, \left\{ 5 \right\}, ..., \left\{ 2n-3 \right\}, \left\{ 2n-1 \right\}" /> </center>

In other words, every odd number less than <img src="http://latex.codecogs.com/gif.latex?2n" title="2n" /> is partitioned into singleton sets. Now, 

<center> <img src="http://latex.codecogs.com/gif.latex?k&space;=&space;2^{m}&space;\times&space;\ell&space;\leq&space;2n&space;\implies&space;\ell&space;\leq&space;2n" title="k = 2^{m} \times \ell \leq 2n \implies \ell \leq 2n" /> </center>

since <img src="http://latex.codecogs.com/gif.latex?m&space;\geq&space;0" title="m \geq 0" align = "center"/> . Since there are <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> distinct odd numbers, among <img src="http://latex.codecogs.com/gif.latex?n&plus;1" title="n+1" align = "center"/> numbers, there should exist two <img src="http://latex.codecogs.com/gif.latex?k_1,&space;k_2" title="k_1, k_2" align = "center"/> having same <img src="http://latex.codecogs.com/gif.latex?\ell" title="\ell" align = "center"/> by pigeonhole principle. Then we can express as 

<center> <img src="http://latex.codecogs.com/gif.latex?k_1&space;=&space;2^{m_1}&space;\times&space;\ell,\&space;k_2&space;=&space;2^{m_2}&space;\times&space;\ell&space;\implies&space;k_1&space;|&space;k_2&space;\text{&space;or&space;}&space;k_2&space;|&space;k_1" title="k_1 = 2^{m_1} \times \ell,\ k_2 = 2^{m_2} \times \ell \implies k_1 | k_2 \text{ or } k_2 | k_1" /> </center>

depending on the magnitude of <img src="http://latex.codecogs.com/gif.latex?m_1,&space;m_2" title="m_1, m_2" align = "center" />. 

If the number reduces to <img src="http://latex.codecogs.com/gif.latex?n" title="n" />, then clearly the set of all odd numbers <img src="http://latex.codecogs.com/gif.latex?\left\{&space;1,&space;3,&space;5,...,&space;2n-1&space;\right\}" title="\left\{ 1, 3, 5,..., 2n-1 \right\}" align = "center"/> would be the counterexample. 

---

**Problem 3.** - **[4]**
Let <img src="http://latex.codecogs.com/gif.latex?a_1&space;<&space;a_2&space;<&space;...&space;<&space;a_n" title="a_1 < a_2 < ... < a_n" align = "center"/> and <img src="http://latex.codecogs.com/gif.latex?b_1&space;>&space;b_2&space;>&space;...&space;>&space;b_n" title="b_1 > b_2 > ... > b_n" align = "center"/> where <img src="http://latex.codecogs.com/gif.latex?a_1,...,a_n,&space;b_1,...,b_n" title="a_1,...,a_n, b_1,...,b_n" align = "center"/> are all distinct elements in  <img src="http://latex.codecogs.com/gif.latex?\left\{&space;1,&space;2,&space;...,&space;2n&space;\right\}" title="\left\{ 1, 2, ..., 2n \right\}" align = "center"/>. Prove that 

<center> <img src="http://latex.codecogs.com/gif.latex?\sum_{i=1}^{n}&space;|a_i&space;-&space;b_i|&space;=&space;n^2" title="\sum_{i=1}^{n} |a_i - b_i| = n^2" /> </center>

**Solution 3.** 
First, partition the whole set into two disjoint subsets

<center> <img src="http://latex.codecogs.com/gif.latex?\left\{&space;1,&space;2,&space;...,&space;n&space;\right\},&space;\left\{&space;n&plus;1,&space;n&plus;2,&space;...,&space;2n&space;\right\}" title="\left\{ 1, 2, ..., n \right\}, \left\{ n+1, n+2, ..., 2n \right\}" /> </center> 


Now fix index <img src="http://latex.codecogs.com/gif.latex?i" title="i" /> , and consider <img src="http://latex.codecogs.com/gif.latex?a_i,&space;b_i" title="a_i, b_i" align = "center"/> . <img src="http://latex.codecogs.com/gif.latex?a_1,&space;a_2,&space;...,&space;a_{i-1},&space;b_{i&plus;1},&space;...,&space;b_n" title="a_1, a_2, ..., a_{i-1}, b_{i+1}, ..., b_n" align = "center"/> are all smaller than <img src="http://latex.codecogs.com/gif.latex?\max(a_i,&space;b_i)" title="\max(a_i, b_i)" align = "center"/> . So at least 

<center> <img src="http://latex.codecogs.com/gif.latex?\max(a_i,&space;b_i)&space;>&space;(i&space;-&space;1)&space;&plus;&space;(n&space;-&space;i)&space;&plus;&space;1&space;=&space;n&space;-&space;1&space;&plus;&space;1&space;=&space;n&space;\implies&space;\max(a_i,&space;b_i)&space;\geq&space;n&space;&plus;&space;1" title="\max(a_i, b_i) > (i - 1) + (n - i) + 1 = n - 1 + 1 = n \implies \max(a_i, b_i) \geq n + 1" /> </center> 

So <img src="http://latex.codecogs.com/gif.latex?\max(a_1,&space;b_1),&space;\max(a_2,&space;b_2),&space;...,&space;\max(a_n,&space;b_n)" title="\max(a_1, b_1), \max(a_2, b_2), ..., \max(a_n, b_n)" align = "center"/> are all elements of the latter set <img src="http://latex.codecogs.com/gif.latex?\left\{&space;n&plus;1,&space;...,&space;2n&space;\right\}" title="\left\{ n+1, ..., 2n \right\}" align = "center" /> . Since 

<center> <img src="http://latex.codecogs.com/gif.latex?\max(a_i,&space;b_i)&space;=&space;\max(a_j,&space;b_j)&space;\implies&space;i&space;=&space;j" title="\max(a_i, b_i) = \max(a_j, b_j) \implies i = j" /> </center>

those <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> elements of the form <img src="http://latex.codecogs.com/gif.latex?\max(a_i,&space;b_i)" title="\max(a_i, b_i)" align = "center" /> are all distinct, so that by Pigeonhole principle, they occupy exactly one element in <img src="http://latex.codecogs.com/gif.latex?\left\{&space;n&plus;1,&space;...,&space;2n&space;\right\}" title="\left\{ n+1, ..., 2n \right\}" align = "center" /> . 

Since <img src="http://latex.codecogs.com/gif.latex?\min(a_i,&space;b_i)&space;<&space;\max(a_i,&space;b_i)" title="\min(a_i, b_i) < \max(a_i, b_i)" align = "center"/> and all  <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> elements of the form <img src="http://latex.codecogs.com/gif.latex?\min(a_i,&space;b_i)" title="\max(a_i, b_i)" align = "center" /> are distinct, by Pigeonhole principle, they occupy exactly one element in <img src="http://latex.codecogs.com/gif.latex?\left\{&space;1,&space;2,&space;...,&space;n&space;\right\}" title="\left\{ 1, 2, ..., n \right\}" align = "center"/>. So 

<center> <img src="http://latex.codecogs.com/gif.latex?\begin{align*}&space;\sum_{i=1}^{n}&space;|a_i&space;-&space;b_i|&space;&=&space;\sum_{i=1}^{n}&space;\left[&space;\max(a_i,&space;b_i)&space;-&space;\min(a_i,&space;b_i)&space;\right]&space;\\&space;&=&space;\sum_{i=1}^{n}&space;\max(a_i,&space;b_i)&space;-&space;\sum_{i=1}^{n}&space;\min(a_i,&space;b_i)&space;\\&space;&=&space;(n&plus;1&space;&plus;&space;n&plus;2&space;&plus;&space;...&space;&plus;2n)&space;-&space;(1&plus;2&plus;...&space;n)&space;\\&space;&=&space;n^2&space;\end{align*}" title="\begin{align*} \sum_{i=1}^{n} |a_i - b_i| &= \sum_{i=1}^{n} \left[ \max(a_i, b_i) - \min(a_i, b_i) \right] \\ &= \sum_{i=1}^{n} \max(a_i, b_i) - \sum_{i=1}^{n} \min(a_i, b_i) \\ &= (n+1 + n+2 + ... +2n) - (1+2+... n) \\ &= n^2 \end{align*}" /> </center> 

## 2. Erd&ouml;s - Szerkes Theorem
The original theorem is as follows. 

**Theorem.**
For given <img src="http://latex.codecogs.com/gif.latex?r,&space;s&space;\in&space;\mathbb{N}" title="r, s \in \mathbb{N}" align = "center"/> any sequence of distinct real numbers with length at least <img src="http://latex.codecogs.com/gif.latex?(r-1)(s-1)&space;&plus;&space;1" title="(r-1)(s-1) + 1" align = "center"/> contains a **monotonically increasing** subsequence of length r **or** a **monotonically decreasing** subsequence of length s. 

**Proof.** - **[5]**
First denote <img src="http://latex.codecogs.com/gif.latex?(r-1)(s-1)&space;&plus;&space;1" title="(r-1)(s-1) + 1" align = "center"/> as <img src="http://latex.codecogs.com/gif.latex?n_1,&space;n_2,&space;...,&space;n_{(r-1)(s-1)&plus;1}" title="n_1, n_2, ..., n_{(r-1)(s-1)+1}" align = "center"/> . Also for each <img src="http://latex.codecogs.com/gif.latex?n_i" title="n_i" align = "center"/>, we assign a pair <img src="http://latex.codecogs.com/gif.latex?(a_i,&space;b_i)" title="(a_i, b_i)" align = "center"/> such that 

<center> <img src="http://latex.codecogs.com/gif.latex?\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;\&space;n_i&space;\mapsto&space;(a_i,&space;b_i)\\&space;a_i:=&space;\text{length&space;of&space;longest&space;monotonically&space;increasing&space;subsequence&space;ending&space;in&space;}n_i\\&space;b_i:=&space;\text{length&space;of&space;longest&space;monotonically&space;decreasing&space;subsequence&space;ending&space;in&space;}n_i" title="\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n_i \mapsto (a_i, b_i)\\ a_i:= \text{length of longest monotonically increasing subsequence ending in }n_i\\ b_i:= \text{length of longest monotonically decreasing subsequence ending in }n_i" /> </center>

Now we seek some properties of this pair. Since all numbers are distinct, 

<center> <img src="http://latex.codecogs.com/gif.latex?i&space;<&space;j\&space;\land&space;n_i&space;\leq&space;n_j&space;\implies&space;a_i&space;<&space;a_j" title="i < j\ \land n_i \leq n_j \implies a_i < a_j" /> </center>

as well as 

<center> <img src="http://latex.codecogs.com/gif.latex?i&space;<&space;j\&space;\land&space;n_i&space;\geq&space;n_j&space;\implies&space;b_i&space;>&space;b_j" title="i < j\ \land n_i \geq n_j \implies b_i > b_j" /> </center>

So, <img src="http://latex.codecogs.com/gif.latex?(a_i,&space;b_i)&space;\neq&space;(a_j,&space;b_j)" title="(a_i, b_i) \neq (a_j, b_j)" align = "center"/> for any case. 

If number of possible values of <img src="http://latex.codecogs.com/gif.latex?a_i" title="a_i" align = "center"/> is less than <img src="http://latex.codecogs.com/gif.latex?r" title="r" /> and number of possible values of <img src="http://latex.codecogs.com/gif.latex?b_i" title="b_i" align = "center"/> is less than <img src="http://latex.codecogs.com/gif.latex?s" title="s" />, then in total, there will be at most <img src="http://latex.codecogs.com/gif.latex?(r-1)(s-1)" title="rs" align = "center"/> number of <img src="http://latex.codecogs.com/gif.latex?(a_i,&space;b_i)" title="(a_i, b_i)" align = "center"/> pairs. This contradicts to the fact that all pairs are distinct (which in total <img src="http://latex.codecogs.com/gif.latex?(r-1)(s-1)&space;&plus;&space;1" title="(r-1)(s-1) + 1" align = "center"/>), so by **Pigeonhole principle**, either 

<center> <img src="http://latex.codecogs.com/gif.latex?a_i&space;\geq&space;r" title="a_i \geq r" /> </center>

or

<center> <img src="http://latex.codecogs.com/gif.latex?b_i&space;\geq&space;s" title="b_i \geq s" /> </center>

for some index <img src="http://latex.codecogs.com/gif.latex?i" title="i" />. 

## 2-1. Visualization of Theorem
Let's say we have <img src="http://latex.codecogs.com/gif.latex?M=(r-1)(s-1)&space;&plus;&space;1" title="(r-1)(s-1) + 1" align = "center"/> distinct real numbers,

<center> <img src="http://latex.codecogs.com/gif.latex?n_1,&space;n_2,&space;...,&space;n_M" title="n_1, n_2, ..., n_M" /> </center>

Now in 2D <img src="http://latex.codecogs.com/gif.latex?\mathbb{R}^2" title="\mathbb{R}^2" /> plane, math each number <img src="http://latex.codecogs.com/gif.latex?n_i" title="n_i" align = "center"/> to the point <img src="http://latex.codecogs.com/gif.latex?n_i&space;\mapsto&space;(i,&space;n_i)" title="n_i \mapsto (i, n_i)" align = "center"/> . Then we can always find a polygonal path either 

1. length <img src="http://latex.codecogs.com/gif.latex?r-1" title="r-1" /> and of positive slope. (Going upward right) 

2. length <img src="http://latex.codecogs.com/gif.latex?s-1" title="s-1" /> and of negative slope. (Going downaward right)

### Example

The case when <img src="http://latex.codecogs.com/gif.latex?r&space;=&space;s&space;=&space;5" title="r = s = 9" /> .  Randomly generate <img src="http://latex.codecogs.com/gif.latex?(r-1)(s-1)&space;&plus;&space;1&space;=&space;17" title="(r-1)(s-1) + 1 = 37" align = "center"/> points.
**[6]**
<center >
<img src = "https://i.imgsafe.org/6d/6da41b2732.png" /> </center> 

We can see that it consists of 5 <img src="http://latex.codecogs.com/gif.latex?=r" title="=r" /> 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. **