Exercise 3. 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 at the far right of the line). How many pebbles did Paul distribute in total, at a minimum?
Solution to Exercise 3 The exercise asks to find a minimum, so there are inevitably two steps: the analysis during which we determine a minimum number of pebbles, and the construction during which the minimum found in the analysis is shown to be achievable.

We denote $a_{k}$ as the number of pebbles the $k$-th student from the right receives.

The student farthest to the left must receive at least 1 pebble, so the student to their right must have at least 2 to have strictly more. We thus prove by induction on $\mathrm{k} \leqslant 42$ that $\mathrm{a}_{\mathrm{k}} \geqslant \mathrm{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 their 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 $\sum_{k=1}^{42} a_{k} \geqslant \sum_{k=1}^{42} k=\frac{42 \cdot 43}{2}=903$ pebbles.

Conversely, if Paul gives exactly $k$ pebbles 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.

Graders' Comments: All students who submitted the exercise understood the issues, but few managed to provide a correct solution. Indeed, two types of cases arise:

- Some showed that the $i$-th student had at least $i$ pebbles for $1 \leqslant i \leqslant 42$ by induction or by iterating their reasoning, and deduced that Paul had given at least 903 pebbles. This reasoning is correct, but it does not ensure that 903 is the minimum: I could just as well have said that he gave at least one pebble to each, so 42 pebbles, and deduced that 42 is the minimum. To show that a number is the minimum value of a quantity, one must show two things: that the quantity is at least this value AND that there exists a realization where the quantity has this value. Here, it was necessary to mention that by giving $i$ pebbles to the $i$-th student for $i$ between 1 and 42, Paul gives 903 pebbles, and the distribution of pebbles meets the conditions of the problem.
- Some tried to "minimize locally" the number of pebbles: since Paul's goal is to give a minimum number of pebbles, he gives a minimum number of pebbles to the first person, then to the second, etc. The problem is that often in problems where one wants to minimize a quantity, trying to minimize step by step can lead to incorrect results. For example, consider the following game: given 3 bills, one of 50 euros, one of 10 euros, and one of 5 euros. Alice chooses the first bill you take, then Bob takes the one he wants, and Alice the last, except if Alice took the 10 euro bill, in which case Bob takes the 5 euro one. Here, to maximize, it is better to take the 10 euro bill first. Similarly, here it could be the same: for example, if the rule was that Paul gives at least 1 pebble to each student, and if a student has 1 pebble, their right neighbor has 2000, the minimum was to give 2 pebbles to each student except the last, whereas if one tries to minimize step by step, one would want to give 1 pebble to the first student, which is suboptimal.