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.

Let $x_1,\ldots,x_n$ be a finite sequence of real numbers. Let $f(\{x_i\}_{i=1}^n)=f(\{x_i\})$ be the length of the largest non-decreasing subsequence, and let $g(\{x_i\})$ be the length of the largest non-increasing subsequence.

Define the function

$$m(n)=\min_{\{x_i\}}f(\{x_i\})g(\{x_i\})$$

Considering a strictly increasing sequence, we can see that $m(n)\le n$. Is it true that $m(n)=n$ for all $n\in\mathbb{N}$?

Similarly, define $f'$ ($g'$) as the length of the largest strictly increasing (decreasing) subsequence, and define

$$M(n)=\max_{\{x_i\}}f'(\{x_i\})g'(\{x_i\})$$

Considering a 'mountain', that is, a sequence that strictly increases through its first half, and then strictly decreases through its second half, we see that $$M(n)\ge \begin{cases}\frac{n(n+2)}{4}&n\text{ even}\\\frac{(n+1)^2}{4}&n\text{ odd}\end{cases}$$

Is this actually an equality for all $n\in\mathbb{N}$? This all checks out for small values of $n$, but as the answers to this question point out, we should be wary about trusting patterns for small values.

share|improve this question
    
I don't understand.. Isn't $M(n) = 1,\,\forall n$? Consider the sequence $\pi,\pi,\pi,\pi,...$? –  Lord Soth Apr 12 '13 at 23:57
    
Oh the second one is a maximization, OK. –  Lord Soth Apr 12 '13 at 23:59

2 Answers 2

up vote 2 down vote accepted

The statement $m(n)=n$ is (also) true, because of the (very slightly stronger) fact:

If for a sequence of numbers the lengths of the longest weakly increasing and of the longest strictly decreasing sequence are respectively $pq$, then $n\leq pq$.

Two proofs. One is to assign to each term $x_i$ of the sequence a pair $(k,l)$ where $k$ is the length of the longest weakly increasing subsequence ending with $x_i$, and $l$ the length of the longest strictly decreasing subsequence ending with $x_i$. Then $1\leq k\leq p$ and $1\leq l\leq q$ and for $i<j$ the pair $(k',l')$ attached to $x_j$ has either $k'>k$ (if $x_i\leq x_j$) or $l'>l$ (otherwise), so in particular $(k',l')\neq(k,l)$ always. As there are only $pq$ possible pairs for $n$ terms, one must have $n\leq pq$. See this note by E. W. Dijkstra (second example) and also this answer by @Ross Millikan.

The other proof is to apply Schensted insertion to the sequence, which results in a pair of tableaux of a shape with $q$ rows and $p$ columns; since the shape (a Young diagram) fits inside the rectangle of those dimensions, one gets $n\leq pq$.

share|improve this answer
    
Wonderful. Thank you! –  Jared Apr 15 '13 at 17:13

For $M(n)$ you are correct. This follows from the AM-GM inequality. You have two numbers that sum to $n$ and want to maximize the product. This happens when you split it as evenly as possible.

share|improve this answer
    
Sure. This is clear. Thank you. Any ideas for $m(n)$? –  Jared Apr 13 '13 at 18:21

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.