Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 7 down vote accepted

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$

share|improve this answer
    
@bcf: Right you are. Good generalization. –  Ross Millikan Dec 1 '13 at 16:00
add comment

I would like to complement the nice answer by Ross Millikan by a somewhat less elementary argument that shows that the lower bound $n^2+1$ for forcing either an increasing or decreasing subsequence of length exceeding $n$ is sharp, namely one can find (many) permutations of $n^2$ that avoid such subsequences.

If one applies the Robinson-Schensted correspondence to a permutation, then corresponding pair of Young tableaux has as number of rows the length of the longest decreasing subsequence of the permutation, and as number of columns the length of the longest increasing subsequence. Now the largest Young diagram with $n$ rows and $n$ columns is square and has $n^2$ unit squares. Therefore one gets the result that a permutation of $n^2+1$ or more must have either an increasing or decreasing subsequence of length exceeding $n$, but also a method to find precisely the permutations of $n^2$ that do not have such subsequences: take any pair of square standard Young tableaux and apply the Robinson-Schensted correspondence in reverse to find the corresponding permutation. For $n=2$ there are $2$ such Young tableaux and therefore $2^2=4$ permutations of $4$ with the desired property, but this number grows rapidly: for $n=5$ there are $701149020$ square Young tableaux and therefore $701149020^2=491609948246960400$ permutations of $25$ without increasing ordecresing subsequences of length exceeding $5$.

Note also that one can impose separate limits $n,m$ on the length of increasing and decreasing subsequences; one can then go up to permutations of $nm$ without exceeding these limits.

share|improve this answer
add comment

You cannot find such a permutation:

Let $a_1,a_2,a_3,a_4,a_5$ be a permutation of $1,2,3,4,5$.

  • If $a_1\not\in\{4,5\}$ and $a_5\not\in\{4,5\}$ then $a_1,4,5$ is an increasing subsequence or $5,4,a_5$ is a decreasing, depending in what order $4,5$ appear in $a_2,a_3,a_4$.
  • If $a_1\not\in\{4,5\}$ and $a_5\in\{4,5\}$ then
    (i) $a_5=5$: $a_1,4,5$ is an increasing subsequence,
    (ii) $a_1=3,a_5=4$: $1,2,4$ is an increasing subsequence or $3,2,1$ decreasing , depending in what order $1,2$ appear in $a_2,a_3,a_4$,
    (iii)$a_1\neq3,a_5=4$: $a_1,3,4$ is an increasing subsequence.
  • If $a_1\in\{4,5\}$ and $a_5\not\in\{4,5\}$ then we proceed as in the previous case.
  • If $\{a_1,a_5\}=\{4,5\}$ $2,3,a_5$ is an increasing subsequence or $a_1,3,2$ is a decreasing, depending in what order $2,3$ appear in $a_1,a_2,a_3,a_4,a_5$.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.