Problem: The $n$ contestants of EGMO are named $C_1$, $C_2$, \dots, $C_n$.
After the competition,
they queue in front of the restaurant according to the following rules.
\begin{itemize}
  \ii The Jury chooses the initial order of the contestants in the queue.
  \ii Every minute, the Jury chooses an integer $i$ with $1 \leq i \leq n$.
  \begin{itemize}
    \ii 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.
    \ii If contestant $C_i$ has fewer than $i$ other contestants in front of her,
    the restaurant opens and the process ends.
  \end{itemize}
\end{itemize}
For every $n$, prove that this process must terminate
and determine the maximum number of euros
that the Jury can collect by cunningly choosing
the initial order and the sequence of moves.

Solution: The maximum money is
$1 + 3 + 7 + \dots + (2^{n-1}-1) = 2^n-n-1$,
which is finite.

Call the 1-euro process a jump,
and let $x_i$ denote the number of times that $C_i$ jumps.
Note that:
\begin{itemize}
  \ii Whenever $C_i$ jumps it must jump over some $C_j$ with $j > i$.
  \ii Contestant $C_i$ can jump over a $C_j$ with $j > i$ at most $1 + x_j$ times.
\end{itemize}
Now, we have $x_n = 0$ and in general,
\begin{align*}
  x_{n-1} &\le 1 + x_n \le 1 \\
  x_{n-2} &\le (1 + x_{n-1}) + (1 + x_{n-2}) \le 3 \\
  x_{n-3} &\le (1 + x_{n-1}) + (1 + x_{n-2}) + (1 + x_{n-3}) \le 7
\end{align*}
and so on, which gives the bound.

The construction is inductive; here is the example for $n = 3$,
with the food towards the right:
\[
  \begin{array}{ccc}
    C_1 & C_2 & C_3 \\
    C_2 & C_1 & C_3 \\
    C_2 & C_3 & C_1 \\
    C_3 & C_1 & C_2 \\
    C_3 & C_2 & C_1
  \end{array}
\]
In general, we can start the contestants in reverse order,
apply inductive hypothesis to $C_1$ through $C_{n-1}$ to flip their order,
then have $C_1$, $C_2$, $\dots$, $C_{n-1}$ jump over $C_n$,
then repeat.
This gives a construction with value $a_1 = 0$
and $a_n = 2a_{n-1} + (n-1)$ which is the same as the bound.