Skip to main content

Section 46.4 Various 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*}