Cfxtrjtrk

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?

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

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.

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 "exressing [your proof] in a more mathematical way". I might be wrong, but I don't think that's possible.)