Proving the existence of a weakly increasing subsequence of length $n$

Let for all integers $i=1,2,\ldots,2^{n-1}$be given integers $f(i)$ such that $$1\le f(i)\le i.$$

Can one show that there exist $a_{1},a_{2},\ldots,a_{n}$ such $1=a_{1}<a_{2}<\cdots<a_{n}\le 2^{n-1}$, and $$f(a_{1})\le f(a_{2})\le \cdots\le f(a_{n})$$

I consider this for some hours, and I can't make this work.

Solution 1:

Consider your function $f$ and build a tree of vertices $\{(1,f(1)),(2,f(2), \ldots, (2^{n-1},f(2^{n-1})\}$ as follows :

• Step 1: add $(1,f(1))$ to the empty tree as the root node.
• Step k: add $(k,f(k))$ to the tree, as the son of the vertex $(i,f(i))$ such that $f(i)\le f(k)$. Among all possibilities, choose a vertex $(i,f(i))$ of maximal depth.

The depth of a vertex is its distance from the root node.

It's easy to verify that :

1. if $(i,f(i))$ and $(j,f(j))$ are different vertices of same depth then $f(i) \ne f(j)$.
2. If $(i,f(i))$ is added at depth $k$ then no more than $f(i)-1$ vertices can be added in the following steps at the same depth $k$.
3. The depth of $(i,f(i))$ is the size (minus 1) of the longest increasing subsequence of $f(1),\ldots,f(i)$.

By induction, you can find that they can't be more than $2^k$ vertices of depth $k$ (because, by induction, the first vertex added with depth $k$ is $(i,f(i))$ with $i\le2^k$ and therefore $f(i)\le2^k$).

So a tree of $2^{n+1}-1$ vertices has at least height $n$, and a tree of $2^{n+1}$ vertices has at least height $n+1$. This proves your property.

Now, you can also find the $f$ with the smallest increasing subsequence :

1,2,1,4,3,2,1,8,7,6,5,4,3,2,1,16 and so on...

I added the suggestions of Ewan Delanoy and miracle173, thanks to them !

Solution 2:

This is basically equivalent to the answer by Xoff, but formulated a bit differently.

Proposition. For given $n>0$, any finite sequence $a_1,a_2,\ldots,a_l$ of integers with $1\leq a_i\leq i$ for all $i$ that contains no weakly increasing subsequences of length $n$, has length $l<2^{n-1}$.

Proof by induction on $n$; the case $n=1$ is obvious, since only the empty sequence has no weakly increasing sequences of length$~1$. Now let $n>1$ and let a sequence satisfying the hypotheses be given. Define $g:\{1,2,\ldots,l\}\to\{1,\ldots,n-1\}$ by setting $g(i)$ to the length of the longest increasing subsequence that ends with $a_i$. We may assume that the range of $g$ is the entire set $\{1,\ldots,n-1\}$ (it is certainly an initial interval, and if $n-1$ is not in the range then the induction hypothesis immediately gives our result), so we can set $m(k)=\min\{\, i\mid g(i)=k\,\}$ for $k=1,2,\ldots,n-1$. Now once we establish that (1) for every$~k$ the subsequence of those $a_i$ with $g(i)=k$ is strictly decreasing, and therefore of length at most the value $a_{m(k)}$ of its initial term, and (2) $a_{m(k)}\leq 2^{k-1}$, the result will follow, because the sequences of (1) form a partition of $a_1,a_2,\ldots,a_l$ and hence $l\leq a_{m(1)}+\cdots+a_{m(n-1)}\leq 2^0+2^1+\cdots+2^{n-2}<2^{n-1}$. But (1) is direct from the definition: if $i<j$ with $g(i)=g(j)=k$ would have $a_i\leq a_j$, one could extend a maximal subsequence of length $k$ ending at $a_i$ with $a_j$, contradicting $g(j)=k$. And since $a_1,a_2,\ldots,a_{m(k)-1}$ has no weakly increasing subsequences of length$~k$, point (2) follows from $a_{m(k)}\leq m(k)\leq 2^{k-1}$, the former inequality holding by hypothesis, and the latter by the induction hypothesis. QED

Of course the statement of the question is just the contrapositive of our proposition.

One may add that $l=2^{n-1}-1$ is only attained if the strictly decreasing sequences of (1) decrease by unit steps and the inequality of (2) is an equality; this happens only for the sequence $$ (a_1,a_2,\ldots,a_{2^{n-1}-1}) =(1,~~2,1,~~4,3,2,1,~~\dots,~~2^i,2^i-1,\ldots,2,1,~~\ldots, ~~2^{n-2},\ldots,1) $$ defined by $a_i=2^{n_i}-i$ where $n_i=\lceil \lg(i+1)\rceil$, so that $2^{n_i}$ is the first power of two strictly exceeding$~i$.