## EGMO '18 P3

For discussing Olympiad Level Combinatorics problems
Abdullah Al Tanzim
Posts: 24
Joined: Tue Apr 11, 2017 12:03 am

### EGMO '18 P3

The $n$ contestants of EGMO are named $C_1,C_2,...,C_n$. After the competition, they queue in front of the restaurant according to the following rules.
1. The Jury chooses the initial order of the contestants in the queue.
2. Every minute the Jury chooses an integer $i$ with $1\leq i\leq n$.
i) If contestant $C_i$ has at least $i$ other contestant in front of her , then 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$ contestant in front of her, the restaurant opens and the process ends.

a) Prove that the process cannot continue indefinitely,regarsless of the Jury's choices.

b) Determine for every n, the maximum number of euros that the Jury can collect by cunningly choosig the initial order and the sequence of moves.
Everybody is a genius.... But if you judge a fish by its ability to climb a tree, it will spend its whole life believing that it is stupid - Albert Einstein

Abdullah Al Tanzim
Posts: 24
Joined: Tue Apr 11, 2017 12:03 am

### Re: EGMO '18 P3

Let $f(n)$ denote the maximum number of euros the Jury can make if there are $n$ contestants. We will prove that $f(n)= 2^n-(n+1)$ for every $n\geq1$ which proves part (a).

If a contestant $C_i$ makes a move and gets ahead of a contestant $C_j$, we will say $C_i$ crossed $C_j$. Also, let $a_k$ denote the number of moves contestant $C_k$ can make.

Claim: $a_{n-k} \leq 2^k-1$

Proof: we will use strong induction on $k$, For $k=0$ , it's easy to see that $C_n$ can make no move. So, $a_n=0$.Now assume that for all $k$
$(0\leq k\leq m)$, we have $a_{n-k}= 2^k-1$.
Note that for $j>i$, the contestant $C_i$ can cross $C_j$ at most $r+1$ times if $C_j$ crosses $C_i$ $r$ number of times.That's because whenever $C_i$ crosses $C_j$ , she gets ahead of $C_J$ and in order to cross $C_j$ again, $C_J$ has to cross $C_i$. Note also that a contestant $C_i$ can make a move if and only if there exists a contestant $Cj (j>i)$ who is ahead of her.So, we have

$a_{n-(m+1)} \leq a_n+1+a_{n-1}+1+a_{n-2}+1+....+a_{n-m}+1 = 1+2^1+2^2+......+2^m$ $= 2^{m+1}-1$.

Now, the maximum number of euros the Jury can make is $a_1+a_2+.....+a_n \leq 2^{n-1}-1+2^{n-2}-1+.......+1+0= 2^n-(n+1)$.

Now, we have prove there indeed exists an initial order and sequence of moves that ensures the Jury can make exactly $2^n-(n+1)$ euros.
we can do it inductively. We choose $C_nC_{n-1}....C_1$ as the initial order for all $n$ and let $b_n$ be the maximum number of moves that can be done with our construction. Suppose $b_{n-1}=2^{n-1}-n$ .Initially for $n=2$ we have $C_2C_1\rightarrow C_1C_2$.
Then for $n$ contestants, firstly we fix contestant $C_n$ and perform the $b_{n-1}$ moves that makes the queue in the form $C_nC_1C_2....C_{n-1}$.Then we let the contestants $C_{n-1},C_{n-2},....,C_1$ to make a move in this order.It makes the queue $C_{n-1}C_{n-2}....C_1C_n$. Then we let the first $(n-1)$ contestants perform the $b_{n-1}$ moves and so it makes the queue in the form $C_1C_2....C_n$.
So, this construction gives us the recurrence relation $b_n= 2b_{n-1}+n-1$ and we can easily get $b_n= 2^n-(n+1)$

and we are done.
Everybody is a genius.... But if you judge a fish by its ability to climb a tree, it will spend its whole life believing that it is stupid - Albert Einstein