Question 141
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)
- 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)