<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[11pt]{article}
\usepackage{amsmath, amssymb, amsthm}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}

\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}

\theoremstyle{remark}
\newtheorem*{claim}{Claim}

\title{An Example of a Proof with Guiding Text}
\author{Prof. Peter Shor}
\date{\today}

\begin{document}
\maketitle

...The last example I want to present has 
to do with permutations. A permutation of $n$ is an ordering of the numbers from 1 to $n$. 
For example, a permutation of 7 is
\[
1 \ 4 \ 3 \ 7 \ 2 \ 6 \ 5 \, .
\]

We will prove the following theorem:
\begin{theorem}
 Every permutation of $n$  has either an
increasing subsequence or a decreasing subsequence of length $\lceil \sqrt{n}
\rceil$. 
\end{theorem}

Here $\lceil \cdot \rceil$ (``pronounced ceiling'') means to round up
to the next integer.  For a permutation of 7, the theorem guarantees an increasing or a
decreasing sequence of length at least $\lceil \sqrt{7} \rceil = 3$. The permutation 
above has an increasing subsequence 1, 4, 7 and a decreasing subsequence 4, 3, 2. 

\begin{proof}[Proof of Theorem 1]
We will associate to every number in the permutation an
ordered pair of two integers. The first integer associated with a number $k$
will be the length of the longest increasing subsequence ending with $k$,
and the second will be the length of the longest decreasing subsequence
ending with $k$. Thus, for the subsequence above, the ordered pairs will be
\[
\begin{array}{ccccccc}
1 &amp; 4 &amp; 3 &amp; 7 &amp; 2 &amp; 6 &amp; 5 \\
\left(\begin{array}{c}1\\1\end{array}\right) &amp;
\left(\begin{array}{c}2\\1\end{array}\right) &amp;
\left(\begin{array}{c}2\\2\end{array}\right) &amp;
\left(\begin{array}{c}3\\1\end{array}\right) &amp;
\left(\begin{array}{c}2\\3\end{array}\right) &amp;
\left(\begin{array}{c}3\\2\end{array}\right) &amp;
\left(\begin{array}{c}3\\3\end{array}\right) 
\end{array} \, .
\]
Here, the ordered pair associated with 2 is
$(2,3)$ because the longest increasing subsequence ending with 2 is 1, 2, which has
length 2, and the longest decreasing subsequence is 4, 3, 2, which has length 3.

\begin{claim}All these ordered pairs are distinct.
\end{claim}

First, we use the pigeonhole principle to show how this claim implies our theorem, and
then we will prove this claim. 

The pigeons will be 
the numbers 1, 2, $\ldots$, $n$, of the permutation, and the holes will be the 
ordered pairs.  To find a bound on the number of holes, let $\ell_i$ be the length of the longest increasing subsequence 
of our permutation, and let $\ell_d$ be the length of the longest decreasing
subsequence. It is clear that all the ordered pairs are less than or equal
to $(\ell_i,\ell_d)$, so the number of pairs is at most $\ell_i \ell_d$. 

If we assume the claim that each pigeon fits into a different hole, then we have
that the number of pigeons is at most the number of holes. There are $n$
pigeons and at most $\ell_i \ell_d$ holes. This gives us
\[
n \leq \ell_i \ell_d,
\]
showing that either $\ell_i \geq \sqrt{n}$ or $\ell_d \geq
\sqrt{n}$. Since $\ell_i$ and $\ell_d$ are integers, we can strengthen
this to $\ell_i\geq \lceil \sqrt{n}\rceil$ or $\ell_d \geq \lceil
\sqrt{n} \rceil$.  
\end{proof}

\begin{proof}[Proof of Claim] Suppose that we have two numbers in our permutation 
$s$ and $t$, with $s$ coming before $t$, and let $(a,b)$ and $(c,d)$ be the
ordered pairs associated with them.
\[
\begin{array}{ccccc}
\ldots &amp; s &amp; \ldots &amp; t &amp; \ldots\\
\ldots &amp; 
\left(\begin{array}{c}a\\b\end{array}\right) &amp;
\ldots &amp; 
\left(\begin{array}{c}c\\d\end{array}\right) &amp;
\ldots 
\end{array}
\]
There is an increasing sequence of length $a$ that
ends with $s$. 
If $s &lt; t$, we can add $t$ to this increasing sequence to obtain an
increasing sequence of length $a+1$ that ends with $t$, showing that $c \geq
a+1$. A similar argument shows that if $s &gt; t$, then $d \geq b+1$. Thus,
the two ordered pairs associated with $s$ and $t$ are distinct.  This proves
the claim.
\end{proof}

It is a fairly easy exercise to find permutations of $n$ 
that have no increasing or decreasing sequences longer than $\lceil \sqrt{n}
\rceil$ for any $n$, showing that our theorem is the strongest possible result.

\end{document} 

</pre></body></html>