Today my friend asked me following question:
Consider the set $ A= \{1,2,3,4,5\}$ By using the elements of this set, can you find a permutation that neither has an increasing sequence of length 3, nor has a decreasing sequence of length 3?
for example:
$3,4,2,1,5$ has an increasing sequence of length $3$, namely $3,4,5$
$5,3,1,2,4$ has a decreasing sequence of length $3$, namely $5,3,2$
I feel like I cannot find such a sequence. I guess problem is that this set has 5 elements and therefore I cannot create such a sequence. If it had 4 elements, I would find lots of sequences with that property. (With the same number of elements, length 4 would be OK too.) But how can I prove it to him? Could you please explain to me?
Best Regards
Best Answer
You cannot create such a sequence. The general statement is that in any sequence of $n^2+1$ terms, there will be an increasing or decreasing subsequence of $n+1$ terms. Your problem is the $n=2$ version of this.
To prove it, associate each term with an ordered pair. The left element of the pair is the length of the longest increasing subsequence from the left that ends on this element. The right element is the length of the longest decreasing subsequence that starts with this element. For your example, $$\begin {array}{c c c c c} 3&4&2&1&5 \\(1,3)&(2,3)&(1,2)&(1,1)&(3,1) \end {array}$$ You can then read off the length $3$ subsequences: $3,2,1;\ \ 4,2,1;\ \ 3,4,5$ The point is that these ordered pairs are all distinct. For if $a$ is left of $b$ and $a \lt b$, the first element of $b$'s ordered pair will be at least $1$ greater than the first element of $a$'s. If $a \gt b$, the second element of $a$'s pair will be at least one greater than $b$'s. Since there are only $n^2$ pairs with maximum value $n$, there must be at least one pair that includes an $n+1$