I was trying to prove the Erdős–Szekeres theorem using pigeon hole. The book I'm referring to, is using Proof by contradiction and then pigeon hole principle.
here's the statement
Theorem
Every sequence of n^2 + 1 distinct real numbers contains a subsequence
of length n + 1 that is either strictly increasing, or strictly decreasing
Proof
Let a1, a2, . . . , an^2+1 be the distinct numbers in the sequence. With term ak
associate the pair (ik, dk) where ik is the length of the longest increasing subsequence
starting at ak, and dk is the length of the longest decreasing sequence starting at
ak.
ASSUME there are no decreasing or increasing subsequences of length n+ 1 (we
give a proof by contradiction). Then ik and dk are both positive integers ≤ n, for
k = 1, 2, . . . , n^2 + 1. So there are (by the Product Rule) n
2 possible ordered pairs
(ik, dk). **By the Pigeonhole Principle, two of these pairs must be equal**
That is, for some as and at with s < t we have is = it and ds = dt.
If as < at, then since is = it, an increasing subsequence of length it + 1 can be built starting at as and following it with the increasing subsequence of length it which begins at at. Therefore is = it + 1 6= it, a CONTRADICTION.
If ax > at, we can similarly conclude that ds = dt+1+dt, a CONTRADICTION.
My confusion is By the Pigeonhole Principle, two of these pairs must be equal, how can we say both increasing and decreasing sequence length is same using Pigeon hole principle ?
Best Answer
The key is recognize the holes and the pigeons.
You have $n^2+1$ pigeons that corresponds to the ordered pairs $\{(i_1,k_1),(i_2,k_2), \dots, (i_{n^2+1},k_{n^2+1})\}$, such that $i_k,d_k \leq n$.
You are putting those $n^2+1$ pigeons in $n^2$ holes which are the total number of ordered pairs such that $i_k, d_k \leq n$.
Thus, there is at least one hole that has two pigeons i.e, two pairs must be equal.