Given a book with $100$ pages and a $100$ lemmas, prove that there is some lemma written on the same page as its index

Question

A book consists of 100 pages and contains 100 lemmas and some images. Each lemma is at most one page long and can't be split into two pages (it has to fit in one page). The lemmas are numbered from 1 to 100 and are written in ascending order. Prove that there must be at least one lemma written on a page with the same number as the lemma's number.

If lemma no. $1$ is written on page $1$, then it is proved. Let's assume lemma no. $1$ is written on page $k, k>1$. Then on at least one page there must be $2$ lemmas. Let's assume that always on page $k+i$ we have lemma no. $i+1$ and so on. Then the last $100-k-i$ lemmas must fit on the last page, which means that there will be at least one lemma (number $100$) on page $100$.

But I don't know how to express it in a more mathematical way!

Any help?

Answer 1

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.

Answer 2

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.)

Answer 3

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)=100\tag{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.

Answer 4

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$.

Answer 5

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 $n\ge 1$.

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

Answer 6

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].

Answer 7

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 $1\le n \le k$ and $ n\in\mathbb 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.