Jtdylktuy

We claim more generally that a book of $n$ pages and $n$ lemmas numbered $1$ through $n$ has at least one lemma on a page matching its number.

Proof by induction on $n$: The case $n=1$ is obvious. Now suppose the statement is true for some $n$, and suppose we have a book of $n+1$ lemmas and $n+1$ pages. If lemma $n+1$ is on a page numbered less than $n+1$, then lemmas $1$ through $n$ must be on pages $1$ through $n$, and there must be at least one lemma on a same-numbered page by the inductive hypothesis. If not, then lemma $n+1$ is on page $n+1$, and we're done.

For each page $i$ assign a number $p(i)$ that defines the highest number of lemma printed on all pages starting from page 1 up to page $i$ (inclusive). So if we have lemmas 3, 4 and 5 printed on page 12, with page 13 having images only: $p(12)=p(13)=5$.

We have the following sequence:

$$p(1), p(2), dots, p(100)=100tag{1}$$

If $p(1)ge1$ it means that lemma 1 is printed on the first page and we are done.

Let us consider a case when $p(1)=0$ (which basically means that the first page is reserved for images only).

The sequence of page numbers $i$ is strictly increasing and the sequence of values $p(i)$ is non-decreasing. Both sequencies have the same number of items (100), with $p(1)<1$ and $p(100)=100$.

Because of that we must have a pair of consecutive pages $i,space j=i+1$ such that:

$$p(i)<i$$

$$p(j)ge j$$

This basically means that lemma $j$ is not printed on page $i$ or on any other page before it. It is actually printed on page $j$ and this completes the proof.

Slight rephrasing of Oldboy's argument:

Let $a_i = i - p_i$, where $p_i$ is the page number of lemma $i$.

Then $a_1 leq 0$, $a_{100} geq 0$, and $a_{i+1}-a_{i} leq 1$. Thus $a_i$ must be $0$ for some $i$.

Consider the path of points $(L, p(L))$ where lemma $L$ is on page $p(L)$. Plot that path on the grid of lattice points $(x,y)$ for $1 le x, y le 100$. The path starts on or above the diagonal at point $(1, p(1))$ and ends on or below the diagonal at point $(100, p(100))$.

Following that path, you move to the right one step at a time as the lemma count increases. You may stay at the same horizontal level since many lemmas can appear on a page. Vertical steps can be longer, if pages of images intervene. Since you start out above the diagonal, you can't cross it for the first time on a vertical step. Since in order to end up on the other side of the diagonal you must cross it once, that must be a horizontal step, so you have landed on it on the way to the other side.

(This doesn't exactly answer your question, which calls "expressing [your proof] in a more mathematical way". I might be wrong, but I don't think that's possible.)

This is a special case of the Knaster-Tarski fixed point theorem (or a corollary thereof):

Theorem. Every increasing function from a certain set to itself has at least one fixed point

This is sometimes given as a nice exercise in real analysis courses, in the following form: Fixed point of a monotone on [0,1].

Here's a slightly amended proof by induction, which I hope will make the induction step more obvious.

Let $P_n$ be the proposition that for a book with $n$ sequentially numbered pages and $n$ or more sequentially numbered lemmas, at least one lemma is on a page with the same number as the lemma.

Suppose $P_n$ is true for some $n=k$, and consider the case of $k+1$ pages and $k+1$ lemmas. To avoid being on its own-numbered page, lemma $k+1$ has to be somewhere in the first $k$ pages, and to keep the lemmas in sequence, no other lemma can go on page $k+1$.

We therefore have to fit all $k+1$ lemmas onto the first $k$ pages. By $P_k$, this puts at least one of them on its own-numbered page.

So wherever lemma $k+1$ is, at least one lemma is on its own-numbered page.

Clearly this remains true if we add more lemmas without adding more pages. That is, with $k+1$ pages and $ge k+1$ lemmas, at least one lemma is on its own-numbered page: ie $P_{k+1}$ holds. That is, if $P_n$ is true for $n=k$, it is also true for $n=k+1$.

Now consider the case of $1$ page and $ge 1$ lemmas. Clearly lemma 1 is on page 1, so $P_1$ is true. Therefore, by induction, $P_n$ is true for all $nge 1$.

Finally, putting $n=100$ proves the case in the original question.

Another proof, this time not by induction.

[Edit: on being tidied up, this turned out to be basically an expanded version of the other proofs that don't use induction.]

Consider a book of $k$ lemmas and $k$ pages.

For $1le n le k$ and $ ninmathbb N$, let

• 
  $p_n$ be the page number of the $n$th lemma


• 
  $D_n=n-p_n$ be the difference between the lemma number and its page number.

We are asked to prove that for some $n$, $D_n=0$.

Suppose we have assigned pages to the first $n$ lemmas. The next lemma can be on either the same page as lemma $n$ or a later page, i.e.
$$p_{n+1}ge p_n$$
from which
$$D_{n+1}le D_n+1$$

That is, $D_n$ can't increase by more than $1$ between one lemma and the next.

If the first lemma is on the first page ($p_1=1$), or the last lemma is on the last page ($p_k=k$), we already have a lemma on its own-numbered page. So we need only consider the case where $p_1>1$ and $p_k<k$, making $D_1<0$ and $D_k>0$.

$D_n$ must therefore increase from a negative value to a positive one somewhere between $n=1$ and $n=k$. But it can only increase in steps of $1$. So for $D_n$ to change sign, there must be a value of $n$ for which $D_n=0$, ie for which lemma $n$ is on page $n$.

There is therefore at least one lemma on a page with the same number as the lemma.