I have been studying Pigeonhole Principle and came across this theorem that is mentioned in the Discrete Mathematics book by Rosen. I understand the theorem and understand the example presented along with the same. But I am slightly confused by the what I understand to be the limitations in applicability of this theorem.
For example what about sequences that are not $n^2+1$ elements long, say sequences of length 11? While the theorem can be applied to sequences of length 10 by taking $n$ as 3 ($3^2+1=10$), I cannot find any $n$ such that $n^2+1=11$. Does that mean the theorem is not applicable in such cases? Does that mean there is no strictly increasing (or decreasing) subsequence of any particular length for any such sequences?
I read the theorem over and over again but it does seem like that the theorem is applicable to a very limited set of sequences i.e. sequences whose length can be written in form $n^2+1$. I was wondering if there was any possible relation between sequences of lengths that are not $n^2+1$ (say 7, 8, 9, 11 or 12) and the length of strictly increasing/decreasing sub-sequences that can be observed in such sequences.
Best Answer
Take a sequence of length $11$ and remove one element of your choice. The theorem guarantees that the resulting sequence contains a sequence of $4$ either strictly increasing or strictly decreasing numbers. This subsequence is obviously present also in the original sequence of length $11$.
In general, find the largest $n$ such that $n^2+1$ is less than or equal to the length of your sequence. Then you can apply the pigeonholing theorem.