Krdytkyu

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 no 1, then it is proved. Let's assume lemma nr 1 is written on page nr k, k>1. Then in at least one page there must be 2 lemmas. Let's assume that always in page k+i we have the lemma nr i+1 and so on. Then the last 100-k-i lemmas must fit in the last page, which means that there will be at least one lemma (number 100) in page 100.
But I don't know how to express it in a more mathematical way!

Any help?

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

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.