(Exercise 3 of submission 4 - Combinatorics (2020-2021))

42 students are lined up. Paul gives each student a certain positive number of pebbles. It is assumed that each student has strictly more pebbles than their right neighbor (except for the student all the way to the right of the line). How many pebbles has Paul distributed in total, at a minimum?
The exercise requires finding a minimum, so there are inevitably two steps: the analysis during which we determine a minimum number of pebbles, and the construction during which we show that the minimum found in the analysis is indeed achievable.

Let $a_{k}$ be the number of pebbles received by the $k$-th student from the right.

The student farthest to the left must receive at least 1 pebble, so the student to his right must have at least 2 to have strictly more. We thus prove by induction on $k \leqslant 42$ that " $a_{k} \geqslant k "$

The base case has already been established. Now suppose that $a_{k} \geqslant k$ for some integer $1 \leqslant k \leqslant n-1$. Since the $(k+1)$-th student must have strictly more pebbles than his right neighbor, we have $a_{k+1} > a_{k} \geqslant k$, so $a_{k+1} \geqslant k+1$, which completes the induction.

Paul must therefore distribute at least $a_{1}+\ldots+a_{42} \geqslant 1+\ldots+42=\frac{42 \times 43}{2}=903$ pebbles.

Conversely, if Paul gives exactly $k$ candies to the $k$-th student from the left, he will meet the given condition and will give a total of 903 pebbles. The minimum is therefore 903.