EGMO 2018 Problem 3

The $n$ contestants of an EGMO are named $C_{1}, \ldots, C_{n}$. After the competition they queue in front of the restaurant according to the following rules.

• The Jury chooses the initial order of the contestants in the queue.
• Every minute, the Jury chooses an integer $i$ with $1 \leq i \leq n$.
• If contestant $C_{i}$ has at least $i$ other contestants in front of her, she pays one euro to the Jury and moves forward in the queue by exactly $i$ positions.
• If contestant $C_{i}$ has fewer than $i$ other contestants in front of her, the restaurant opens and the process ends. (a) Prove that the process cannot continue indefinitely, regardless of the Jury's choices. (b) Determine for every $n$ the maximum number of euros that the Jury can collect by cunningly choosing the initial order and the sequence of moves. (Hungary)