MathDB

The

n

contestant of EGMO are named

C_1, C_2, \cdots 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 process ends.

[*]Prove that the process cannot continue indefinitely, regardless of the Jury’s choices. [*]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.

Problem Statement