Section46.4Various Problems

Let $a_{1},\ldots,a_{k^{2}+1}$ be any sequence of integers. Prove that it contains a monotone subsequence of length $k+1\text{.}$

Solution

Given $i\in \{1,\ldots,k^2+1\}\text{,}$ let $d(i)$ be the length of the longest subsequence $a_i\leq a_{j_1}\leq cdots\leq c_{d(i)-1}$ with $i\lt j_1\lt \cdots\lt j_{d(i)-1}\text{.}$

Suppose that for each $i$ we have $d(i)\leq k\text{.}$ Then, by the Pigeonhole Principle, there is $\ell \in \{1,\ldots,k\}$ such that $|\{i\in \{1,\ldots,k^2+1\}:d(i)=\ell\}|\geq k+1\text{.}$

Let $i_1\lt i_2\lt \cdots \lt i_{k+1}$ be such that $d(a_{i_1})=d(a_{i_2})=\cdots=d(a_{i_{k+1}})=\ell\text{.}$

If there are $1\leq p\lt q\leq k+1$ such that $a_{i_p}\leq a_{i_q}$ then $d(i_p)\geq 1+d(i_q)>\ell\text{,}$ which contradicts our choice of $a_{i_p}\text{.}$ Hence,

\begin{equation*} a_{i_1}\lt a_{i_2}\lt \cdots \lt a_{i_{k+1}}\text{,} \end{equation*}

which completes the proof of the claim.

Let $f$ be an integral–valued function defined on $\{1,\ldots,2^{n-1}\}\text{,}$ such that $1 \leq f(i) \leq i\text{,}$ for $i = 1,\ldots,2^{n-1}\text{.}$ Prove that there is a sequence

\begin{equation*} 1 = a_{1} \lt\dots \lt a_{n} \leq 2^{n-1} \end{equation*}

with

\begin{equation*} f(a_{1}) \leq \dots \leq f(a_{n})\text{.} \end{equation*}

Prove that the bound is sharp.

Solution

Let $d(x)$ be the maximum length of sequence $x=a_1\lt a_2\lt \cdots$ with $f(a_1)\leq f(a_2)\leq\cdots\text{.}$ Since $f(1)=1\text{,}$ it follows that $\max d(x)=d(1)\text{.}$

We use mathematical induction on $n$ to prove the claim.

For the base case when $n=1\text{,}$ we have $f(1)=1=a_1=2^{1-1}=1\text{,}$ i.e., the claim is true. Suppose that $n\gt 1$ is such that the claim is true for all $m\geq n-1\text{.}$

We first prove that if $d(x)\geq d(1)-k\text{,}$ then $f(x)\leq 2^k$ for $0\leq k\leq d(1)-1\text{.}$ Assume by contradiction that $f(x)\gt 2^k$ and $t(x)\geq d(1)-k\text{.}$ Then, since $x\geq f(x)>2^k\text{,}$ it follows that $x\gt 2^k\text{,}$ which implies $k\lt n-1\text{.}$ Let

\begin{equation*} x=a_1\lt \cdots\lt a_{d(x)}\text{ with }f(a_1)\leq\cdots\leq f(a_{d(x)}). \end{equation*}

By the induction hypothesis, there exists

\begin{equation*} 1\leq b_0\lt b_1\lt \cdots\lt b_k\leq 2^k\text{ with }f(b_0)\leq f(b_1)\leq\cdots\leq f(b_k). \end{equation*}

This, together with

\begin{equation*} f(b_0)\leq f(b_1)\leq\cdots\leq f(b_k)\leq b_k\leq 2^k\lt f(a_1)\leq\cdots\leq f(a_{d(x)}) \end{equation*}

implies $d(1)\leq d(x)+k+1\text{,}$ i.e., $d(1)-k\geq d(x)+1\text{,}$ contradicting the assumption that $d(x)\geq d(1)-k\text{.}$

If $x\lt y$ and $d(x)=d(y)\text{,}$ then $f(x)\not= f(y)\text{.}$ Otherwise the chain starting with $y$ could be extended to $x\text{.}$ Therefore,

\begin{equation*} |\{x:d(x)=d(1)-k\}|\leq 2^k\text{ for }0\leq k\leq d(1)-1. \end{equation*}

Hence,

\begin{equation*} 2^{n-1}=\sum_{k=0}^{d(1)-1}|\{x:d(x)=d(1)-k\}|\leq\sum_{k=0}^{d(1)-1}2^k=2^{d(1)-1} \end{equation*}

and $d(1)\geq n\text{.}$ In other words, the maximum length of the sequence $1=a_1\lt a_2\lt \cdots$ with $f(a_1)\leq f(a_2)\leq\cdots$ is at least $n\text{,}$ which completes the proof of the induction step.

By the Principle of Mathematical Induction, the claim is true for all $n\in \mathbb{N}\text{.}$

We show the sharpness of the bound in the following way.

Let $g(2^k+l)=2^k-l$ with $0\leq k\leq n-2$ and $0\leq l\leq 2^k-1\text{.}$ Then

\begin{equation*} \begin{array}{c||c||cc||cccc||c||cccc} m\amp1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp \cdots\amp 2^{n-2}\amp 2^{n-2}+1\amp \ldots\amp 2^{n-1}-1\\ \hline g(m)\amp1\amp2\amp1\amp4\amp3\amp2\amp1\amp\cdots\amp 2^{n-2}\amp 2^{n-2}-1\amp\ldots\amp 1\\ \end{array} \end{equation*}

Observe that, for any $1\leq i\leq 2^{n-1}-1\text{,}$ $g(i)\leq i\text{.}$ Notice that the range of $g$ consists of $n-1$ monotone decreasing intervals. Any sequence

\begin{equation*} 1\leq a_1\lt \cdots \lt a_t\leq 2^{n-1}-1\text{ with }f(a_1)\leq\cdots\leq f(a_t) \end{equation*}

contains at most one number from each these intervals. Therefore, the longest possible sequence is of the length $n-1\text{:}$

\begin{equation*} 1=2^0 \lt 2=2^1\lt 4=2^2\lt \cdots \lt 2^{n-2}\text{.} \end{equation*}