I think the maximum money is $1 + 3 + \dots + (2^{n-1}-1)$ which implies (a). Call the 1-euro process a jump, and let $x_i$ denote the number of times that $C_i$ jumps. Note that (i) whenever $C_i$ jumps it must jump over some $C_j$ with $j > i$. (ii) $C_i$ can jump over a $C_j$ with $j > i$ at most $1 + x_j$ times. Now, we have $x_n = 0$ and for any other $1 \le k < n$, \[ x_k \le (1+x_{k+1}) + (1+x_{k+2}) + \dots + (1+x_n). \]This gives $x_{n-1} \le 1$, $x_{n-2} \le 3$, $x_{n-3} \le 7$ and so on which proves the bound. The construction is inductive. Let $a_n$ denote the answer for $n$. Start the girls in reverse order, apply inductive hypothesis to $c_1$ through $c_{n-1}$ to flip their order, then $c_1$, $c_2$, $\dots$, $c_{n-1}$ jump over $c_n$, then repeat. This gives a construction with $a_1 = 0$ and $a_n = 2a_{n-1} + (n-1)$ which is the same as the bound.

Do contestants have infinite supply of money?

MarkBcc168 wrote: Are contestants have infinite supply of money? Yes.

Consider how many times a number $i$ can make a move, say $a_i$. Of course $x_n=0$, and $x_{n-1}=1$ because after $1$ jump, $n$ must be behind $n-1$, so $n-1$ cannot jump anymore. In general, every time $i$ jumps, it must jump across at least one big number at least $i+1$, and then the big number will stay behind $i$, except possibly when some big number jumps and become in front of $i$ again. So $i$ can be "saved" by a big number $j\ge i+1$ at most $x_j$ times, then $j$ will forever be behind $i$. This means $x_i\le (n-i)+x_n+x_{n-1}+\cdots x_{i+1}$. Well, $x_{n-i}\le 2^{i}-1$. That's it, so total money is $x_1+\cdots x_n$, which is at most $\sum^{n-1}_{i=0}{(2^i-1)}$. Now equality holds when every jump of $i$ jumps across exactly $1$ big number. Pretty easy to see from $n=4$ above, a construction is to start from $n, (n-1), \cdots , 1$, then reorder $1$ to $n-1$ using $\sum^{n-2}_{i=0}{(2^i-1)}$ moves by induction hypothesis, then use $n-1$ moves to jump everything across $n$, then reorder again using $\sum^{n-2}_{i=0}{(2^i-1)}$ moves again. This amounts to $2 \sum^{n-2}_{i=0}{(2^i-1)}+(n-1)= \sum^{n-1}_{i=0}{(2^i-1)}$ moves which completes the inductive step. Base case is $f(2)=1$. Done.

Similar to the above solutions (actually reading them again almost exactly the same). First we prove the jury can collect at most $2^{n}-(n+1)$ euros which proves part $\text{a}$ Let $f(i)$ be the maximum number of moves that $C_{n-i}$ can carry out. Obviously $f(0)=0$. We now go by induction. When person $C_{n-i}$ moves they must jump over at least one of $C_{n}, \cdots, C_{n-i+1}$ so consider how many times each of these can appear in the group of people person $C_{n-i}$ jumps over gives: $$f(i)=(f(0)+1)+ \cdots +(f(i-1)+1)$$And it can easily be shown by induction that $f(i)=2^{i}-1$. At most $\sum f(i)=2^{n}-(n+1)$ moves are carried out. We now go by induction to prove this is possible. We claim that going from $1,2, \cdots, n \rightarrow n, \cdots, 2,1$ achieves the bound. This is obvious for $n=2$. For $n \geq 3$ we see we can go: $$1,2, \cdots, n \rightarrow n-1,n-2, \cdots ,1,n \rightarrow n-2, \cdots,1,n,n-1 \rightarrow \cdots \rightarrow n,1,2, \cdots, n-1 \rightarrow n,n-1, \cdots,1$$By the inductive hypothesis the first and last steps take $2^{n-1}-n$ moves each and the middles steps consist of jumping $n-1$ numbers giving a total of: $$2 \left(2^{n-1}-n \right)+(n-1)=2^{n}-(n+1)$$moves as desired. This proves the bound is optimal.

I will give another proof of the bound (at most $2^n-n-1$ euro). Strengthen the jury's process to Strengthened EGMO 2018 P3 wrote: 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 at least $i$ positions. If contestant $C_i$ has fewer than $i$ other contestants in front of her, the restaurant opens and process ends. We claim that even with this weaker conditions, the Jury still can collect at most $2^n-n-1$ euros. We will prove that by induction on $n$ with trivial base case $n=1$. First, remove $C_1$ out and using induction hypothesis on $(C_2, C_3,...,C_n)$, we see that jury collect at most $2^{n-1}-n$ euros from $C_2, C_3, ...,C_n$. Now it suffices to show that he can collect at most $2^{n-1}-1$ euros from $C_1$. Let $x$ be the number of euro collected from $C_1$. Notice that whenever jury collect one euro from $C_1$, $C_1$ will move at least one position forward while if jury collects euro from other $C_i$, he will move backward by one position. The net change is at least $x-(2^{n-1}-n)$. But this has to be at most $n-1$ so $x\leqslant 2^{n-1}-1$ as desired.

I am having trouble understanding the meaning of the problem statement. Can someone explain it, please?

Nice and easy. My solution was inspired by IMOSL 2012 C1 (Basically focus on the maximal and the minimal element). Anyway, here's my solution: Starting from the position farthest from the restaurant, label the positions $P_1,P_2, \dots ,P_n$ (i.e. the contestant at position $P_n$ is closest to the restaurant). Part (a) We will prove this with the help of a nested induction. First induct on $n$. The result is obvious when $n=1,2$. So assume that the result is true for $n-1$. Suppose that initially contestant $C_n$ is at the position $P_m$. The main observation is that the Jury can never choose $C_n$. We claim that $C_n$ must reach $P_1$ sooner or later. To show this we again induct (that's why a nested induction ), this time on $m$. For $m=1$, the claim is true ($C_n$ is at $P_1$ initially only!!). Suppose our claim is true for $m-1$. Now, let $\mathbb{A}$ denote the set of students placed at $P_1,P_2, \dots ,P_{m-1}$; and $\mathbb{B}$ denote the set of students placed at $P_{m+1},P_{m+2}, \dots ,P_n$. If at any moment of time, some contestant from $\mathbb{A}$ jumps over to $\mathbb{B}$ (i.e. crosses $C_n$), then $C_n$ will move to position $P_{m-1}$, and we can apply the second inductive hypothesis to conclude that $C_n$ must reach $P_1$. Once, $C_n$ reaches $P_1$, we can effectively ignore its presence (as it can never be the cause of any contestant's jump). Then using the first inductive hypothesis, we get that the game must terminate. Otherwise no contestant from the group $\mathbb{A}$ ever crosses over to $\mathbb{B}$. Then these two group of contestants will never interact with each other, and so the presence of $C_n$ is superfluous (once again it does not cause anyone's move). Hence, we can ignore $C_n$, and apply the first inductive hypothesis on the remaining $n-1$ contestants to get the desired conclusion. Hence, done. $\blacksquare$ Part (b) Let $f(n)$ be the desired maximum. We claim that it is given by $f(n)=2^n-n-1$. First we show that this is achievable. Initially arrange the contestants as $C_1,C_2, \dots ,C_n$ (starting from the extreme position, i.e. in the order $P_1,P_2, \dots ,P_n$). Let $g(n)$ be the maximum number of euros that the Jury can earn while reversing this order of contestants. To do so, first reverse the order of the first $n-1$ contestants in $g(n-1)$ moves, to get to the state $C_{n-1}, \dots ,C_2,C_1,C_n$. Then, in $n-1$ moves, take $C_1,C_2, \dots ,C_{n-1}$ (in that order) to the front, to reach at the stage $C_n,C_1,C_2, \dots ,C_{n-1}$. Now, again in $g(n-1)$ moves reverse the last $n-1$ contestants $(C_1,C_2, \dots ,C_n)$ to get the desired order of queue, i.e. $C_n,C_{n-1}, \dots ,C_2,C_1$. Thus, we get $g(n)=2g(n-1)+n-1$ with $g(2)=1$. Let $h(n)=g(n)+n+1$. Then the given condition becomes $h(n)=2h(n-1)$ satisfying $h(2)=4$. Thus, we have $h(n)=2^n$, which in turn gives $g(n)=2^n-n-1$. Thus, the claimed maximum is indeed achievable. Now, all we need to prove is that this maximum can not be improved. We again appeal to an inductive proof. Our claim is easily true for $n=1,2$. Suppose that it is true for $n-1$. We will show that this is the maximum for $n$ contestants. This time our center of focus will be $C_1$. Suppose that the jury applies $k$ moves on $C_1$ before the process terminates, and applies $2^{n-1}-n$ moves on the remaining contestants (by the inductive hypothesis). In each move not on $C_1$, she may move backward by atmost $1$ position. Thus, the total distance moved by $C_1$ over the whole process cannot be less than $k-(2^{n-1}-n)$ towards the restaurant. However, this distance cannot exceed $n-1$ (as $C_1$ can at the most move from $P_1$ to $P_n$). This gives $k+n-2^{n-1} \leq n-1$. Thus, $$f(n)=(2^{n-1}-n)+k \leq (2^{n-1}-n)+2^{n-1}-1=2^n-n-1 \quad \blacksquare$$ REMARK: In fact one can easily show that in the end, the contestants must be ordered as $C_n,C_{n-1}, \dots ,C_2,C_1$ (starting from the extreme position, i.e. in the order $P_1,P_2, \dots ,P_n$). Just give the weights $w_k(i)=i+j$ to each contestant $C_i$ present at position $P_j$ after $k$ moves. Then a necessary condition for the jury to choose $C_i$ is $w_k(i) \leq n$. This means that we must have $w_{f(n)}(i) \geq n+1$ for all $i \in \{1,2, \dots ,n\}$. Also, $w_k(1)+w_k(2)+ \dots +w_k(n)=n(n+1)$ for every possible value of $k$. Thus, we get $$n(n+1)=\sum_{i=1}^n w_{f(n)}(i) \geq \sum_{i=1}^n n+1=n(n+1) \Rightarrow \text{As equality holds, so } w_{f(n)}(i)=n+1 \text{ } \forall i \in \{1,2, \dots ,n\}$$This is only possible when contestant $C_i$ is at position $P_{n-i+1}$, and the queue is as ordered above. P.S. Can someone please check my solution to part (a) . It is a bit different than what I usually do.

It's clear that (b) implies (a), but it's much more natural to solve (a) first, so we present a solution seperately to (a). The solution in fact motivates the solution to (b). (a) We prove a stronger statement to enable induction. Consider distinct $x_1,\ldots,x_n$. We claim that if $C_{x_1}\cdots C_{x_n}$ are in a row, then the process eventually stops. It's obvious for $n=1$, so suppose it's true for $n-1$. Let $x_m$ be the largest in $\{x_1,\ldots,x_n\}$. We see that $x_m\ge n$, so $C_{x_m}$ can never participate in a move except moving back in the line. So if the process ran indefentley, there is some point at which $x_m$ stops moving. Let $C_{y_1}\ldots C_{y_r}$ be the ones ahead of $C_{x_m}$. We never have a move from someone behind as $C_{x_m}$ never moves, so by the induction hypothesis, $C_{y_1}\ldots C_{y_r}$ stops, so the whole process stops. Thus, we're done by induction. (b) Let $f(n)$ be the answer. We claim that $f(n)=2^n-n-1$. Let $g(i)$ be the maximum number of times that $C_i$ moves forward. Note that $C_i$ can hop over $C_j$ where $j>i$ at most $g(j)+1$ times, since each time it hops over $C_j$, it can hop over agin only if $C_j$ hops. Any move of $C_i$ hops over some $C_j$ where $j>i$, so \[g(i)\le g(i+1)+\cdots+g(n)+(n-i).\]Using $g(n)=0$, we easily see by induction that $g(i)\le 2^{n-i}-1$. So \[f(n)\le g(1)+\cdots=g(n)=2^n-n-1.\] We now show that $2^n-n-1$ moves is attainable. Suppose we can turn $n\cdots 21$ into $12\cdots n$ in $2^n-n-1$ moves. Then, turn $(n+1)n\cdots 21$ into $(n+1)12\cdots n$ in $2^n-n-1$ moves. In $n$ moves, hop each of $1,\ldots n$ over $n+1$ to get \[n\cdots 21(n+1).\]Apply another $2^n-n-1$ moves to turn this into $12\cdots n(n+1)$. This takes a total of \[2(2^n-n-1)+n=2^{n+1}-(n+1)-1\]moves, so by induction, we have a construction.

Just need to solve for (b) as (b) implies (a) immidiately. We'll prove that the maximum is $\boxed{2^n - n - 1}$. We'll first prove the bound, and then provide a construction. To prove the bound, consider the maximal number of hops $C_k$ can do. Denote this as a function $f(k)$. Let the participants be $C_1, C_2, \dots, C_{n + 1}$. Note that $C_{n + 1}$ can't hop as there are only $n$ other students. Notice that $C_{n}$ can only hop at most once , that is when $C_{n + 1}$ is in front of $C_n$. But notice that once this hop is done, $C_n$ can't hop to the front again by the previous hypothesis, and therefore there can't be $n$ contestants in front of $C_n$. Now, a similar process hold for $C_k$. It can only hops to the front when at least one of $C_{k + 1}, C_{k + 2} , \dots, C_{n + 1}$ is in $C_k$'s front. Notice that $C_i$ can only hop pass $C_j$ at most $f(j)+ 1$ times $( i < j$). This is when it was initially given that $C_j$ was in front of $C_i$, and every time $C_j$ hops to front, $C_i$ hops once. Therefore, we have \[ f(i) \le \sum_{k = i + 1}^{n + 1} f(k) \]It's easy to get $f(n + 1 - k) \le 2^k - 1$ at this point. Hence, the maximum number of hops allowed is \[ f(1) + f(2) + \dots + f(n + 1) = 2^{n + 1} - (n + 2) \](Remember this is the case for $n + 1$ contestants.) Now, to prove that such value is attainable, we use strong induction. First, notice that it terminates if and only if its is placed as $C_nC_{n - 1} C_{n - 2} \dots C_2 C_1$. To prove this, notice that this indeed terminates, and by swapping any two position not in order, there must exists a index which is less than the number of people in front of him/her. Now we'll prove that there exists a sequence of $2^n - (n + 1)$ hops from $C_1 C_2 \dots C_n$ to $C_n C_{n - 1} \dots C_1$. Case check for $n = 1, 2, 3$ is easy. Now, assume that it is true for $n \le k$. We'll prove that it is true for $n = k + 1$ as well. Denote $A(n)$ as the number of hops from $C_1 C_2 \dots C_n$ to $C_n C_{n - 1} \dots C_1$. Notice that we can do the following series of moves: \[ (C_1 C_2 \dots C_{n - 1}) C_n \to (C_{n - 1} C_{n - 2} \dots C_1) C_n \to (C_{n - 2} C_{n - 3} \dots C_1 C_n) C_{n - 1} \to (C_n C_{n - 2} \dots C_1)C_{n - 1} = C_n ( C_{n - 2} \dots C_1 C_{n - 1} ) \to C_n C_{n - 1} C_{n - 2} \dots C_1 \]The first move is essentially $A(n - 1)$. The second move is just $1$, which is $C_{n - 1}$ hops to the front. The third move and the last move is the same, which is the number of move from $C_{n - 2} C_{n - 3} \dots C_1 C_{n - 1}$ to $C_{n - 1} C_{n - 2} \dots C_1$. Let this number be $B(n - 1)$. Hence, \[ A(n) = A(n -1) + 2B(n - 1) + 1 \]To calculate $B(n)$, notice that we can do the following algorithm: Let the $C_k$'s hop in order from the smallest $k$ to the front. Then, we proceed by induction again. \[ C_{n - 1} C_{n - 2} \dots C_1 C_n \to C_n (C_1 C_2 \dots C_{n -1 }) \to C_n (C_{n - 1} C_{n - 2} \dots C_1) \]This gives us $n - 1$ hops for the first move, and $A(n - 1)$ hops for the second move. Hence, \[ B(n) = A(n - 1) + n - 1 \]Therefore, we have the recursion \[ A(n) = A(n - 1) + 2A(n - 2) + 2n - 1 \]It suffices to see that $A(n) = 2^n - (n + 1)$.

Let $f(i)$ be the maximum number of times $i$ can hop forward. Clearly $f(n)=0$. We claim $f(n-k) \le 2^k-1$ for $k=0,\ldots,n-1$. We induct on $k$, the base case of $k=0$ clear, since $n$ can never hop forward. There are two key observations. By pigeonhole, when some $i$ hops forward, it must hop over some number greater than $i$. This is because $i$ hops over $i$ numbers, and there are only $i-1$ numbers at most $i$. When $i$ hops over $j$, then $j$ must hop over $i$ for $i$ to be able to hop over $j$ ever again. This is because when $i$ hops over $j$, $i$ is now ahead of $j$, and will never be behind $j$ unless $j$ hops over $i$. Combining the above two observations, we note that $i$ can hop over $j$ at most $f(j)+1$ times for any $j>i$; we add 1 for the initial time $i$ hops over $j$. Therefore, we establish the bound \begin{align*} f(n-k) &\le (f(n)+1) + (f(n-1)+1)+ \cdots + (f(n-k+1)+1) \\ &\le 2^0 + 2^1 + \cdots + 2^{k-1} \\ &= 2^k-1. \end{align*}Now, the maximum number of total hops is \[ f(1)+f(2)+\cdots+f(n) \le (2^{n-1}-1) + \cdots + (2^0-1) = 2^n-n-1. \]Note that this implies part (a), since we have bounded from above the total number of hops possible. For part (b), it remains to show we can achieve equality. We claim we can go from $12\ldots n \to n\cdots 1$ in $2^n-n-1$ moves; induct on $n$, $n=1$ clear. We can do $12\ldots n \to (n-1)\cdots 1n$ in $2^{n-1}-(n-1)-1$ moves. Then do $n-1$ moves to get to $n12\ldots (n-1)$. Then do another $2^{n-1}-(n-1)-1$ to finish. In total, we have \[ 2(2^{n-1}-(n-1)-1) + (n-1) = 2^n-n-1\]moves, as desired.

Here is another solution (sketch) for part (a) (inspired by Evan's solution to IMO 2019/5): Let \(G_n\) be the obvious directed graph. It suffices to show that there is no cycle. Suppose \(u_1\to u_2\to \cdots \to u_k \to u_1\) is a cycle. Then the position of contestant \(C_n\) in each \(u_i\) is the same. So we can delete \(C_n\) and induct down. Done.

I claim that each contestant $C_{n-i}$ can make at most $2^{i} - 1$ moves, and thus generates at most that much money. Let person $C_i$ make $f(i)$ moves. We will prove this recursively; note that clearly $f(n) = 0$ since there will always be $< n$ people in front of her. Furthermore, note that in general, if $C_k$ is able to make a move, then there are $\geq k$ contestants in front of her and one of them will be $C_{\ell}$ with $\ell > k$. For each $\ell > k$, person $C_k$ can skip over person $C_{\ell}$ at most $1 + f(\ell)$ times since every time $C_k$ skips over $C_{\ell}$, person $C_{\ell}$ must make a skip to be skipped over again by $C_k$, and $C_{\ell}$ can make at most $1 + f(\ell)$ moves. Hence, we can write\[f(k) \leq \sum_{\ell > k} (1 + f(\ell))\]and if we inductively assume that $f(n - i) \leq 2^i - 1$ for all $i \leq m$, then we have\[f(n - (m + 1)) \leq (1 + f(n)) + \ldots + (1 + f(n - m)) \leq 2^0 + \ldots 2^m = 2^{m+1} - 1\]proving our inductive hypothesis. Finally summing over all contestants $C_i$, we get that\[f(1) + \ldots + f(n) \leq \sum_{i = 0}^{n-1} (2^i - 1) = \boxed{2^n - (n + 1)}.\]We now find an inductive construction. I claim that we can turn $C_n\ldots C_2C_1$ into $C_1C_2\ldots C_n$ legally in $2^n - (n+1)$ moves. This is clearly true for $n = 0$; next, suppose it is true for some $m$ and then we show that we can do it for $m + 1$. Indeed,\[C_{m+1}C_m\ldots C_2C_1 \to C_{m+1}C_1C_2\ldots C_m\]takes $2^m - (m + 1)$ moves. Then have each $C_1 \to C_m$ skip over $C_{m+1}$ to the front of the line, starting from $C_1$. This takes $m$ moves and turns\[C_{m+1}C_1C_2\ldots C_m \to C_mC_{m-1}\ldots C_1C_{m+1}\]and we reverse $C_m\ldots C_1$ with $2^m - (m+1)$ moves to get them into proper order. This is a total of\[2(2^m - (m+1)) + m = 2^{m+1} - (m+2)\]moves, proving our inductive construction. $\blacksquare$

Let $A = \sum_i \sum_{j<i} 2^{j-1}f(i,j)$. Where \[f(i,j) = \begin{cases} 1 & \text{if $C_j$ is in front of $C_i$}\\ 0 &\text{otherwise} \end{cases}\]$A$ increases every minute. $A\leq \sum_i \sum_{j<i} 2^{j-1} = \sum_i 2^{i-1}-1 = 2^n-1-n = 2^n - (n+1)$. Hence, the maximum number of euros is $2^n-(n+1)$. This is achieved when the initial configuration is $C_1C_2C_3\dots C_{n}$.

The jury can collect at most $2^n-(n+1)$ euros. For ease of writing, assume that the names of the contestants are given in height order, where $C_1$ is the shortest contestant and $C_n$ is the tallest. We first prove the following lemma: Lemma 1: When a contestant $C_i$ moves forward, the number of taller contestants behind $C_i$ strictly increases. Proof: Note that the number of contestants taller than $C_i$ is $n-i$. If a contestant starts at the $x$th place and moves to the $(x-i)$th place, then there were at most $n-x$ contestants taller than $C_i$ and behind her before she moved. Further, after $C_i$ moves, those $n-x$ contestants must still be behind $C_i$. Now, there are $x-i-1$ contestants who are in front of the $(x-i)$th place, and at least $(n-i)-(n-x)=x-i$ contestants who were in front of $C_i$ before she moved. This means that the number of taller contestants in front of $C_i$ must strictly decrease, so the number of taller contestants behind $C_i$ will strictly increase. $\blacksquare$ We now prove the key claim, which establishes this figure as an upper bound and also proves (a). Claim: The contestant $C_{n-k}$, where $0 \leq k \leq n-1$, can move forward at most $2^k-1$ times. Proof: We use strong induction on $k$. For the base case, where $k=0$, we are considering the contestant $C_n$. Since there are $n-1$ other contestants, there can never be at least $n$ contestants in front of $C_n$, so $C_n$ can never move forward. That is, $C_n$ can move forward at most $2^0-1=0$ times. Now for the inductive step. Suppose we know that for some $0 \leq a \leq n-1$, all contestants $C_{n-k}$ where $0 \leq k \leq a$ can move forward at most $2^k-1$ times. We will show that the contestant $C_{n-(k+1)}$ can move forward at most $2^{k+1}-1$ times. By lemma 1, the number of taller contestants behind $C_{n-(k+1)}$ strictly increases when she moves, so for $i<k+1$, $C_{n-(k+1)}$ moves past $C_{n-i}$ at most once, unless $C_{n-i}$ moves as well. But since $i<k+1$, we know by inductive hypothesis that the contestant $C_{n-i}$ moves forward at most $2^i-1$ times. Therefore, $C_{n-(k+1)}$ can move past $C_{n-i}$ at most $2^i-1+1=2^i$ times, so $C_{n-(k+1)}$ can move forward at most $$\sum_{i=0}^k 2^k=2^{k+1}-1$$times, completing the induction. $\blacksquare$ This claim implies that the jury can collect at most $$\sum_{i=0}^{n-1} 2^i-1=2^n-(n+1)$$euros, which proves the upper bound. It remains to show that there exists a construction that allows the jury to collect this number of euros. Call a process where $k$ contestants initially lined up in the order $$C_k,C_{k-1},C_{k-2},\ldots,C_1$$make some number of moves, ultimately finishing lined up in the order $$C_1,C_2,C_3,\ldots,C_k$$a "$k$-reverse". Claim: The $k$-reverse can be achieved in exactly $2^k-(k+1)$ moves. Proof: We use induction on $k$. The base case of $k=1$ is trivial. Now suppose that for some value of $a$, the $a$-reverse can be achieved in exactly $2^a-(a+1)$ moves. Then we consider the $a+1$ reverse. Initially, the contestants are lined up in the following order: $$C_{a+1},C_a,C_{a-1},\ldots,C_1$$Now we apply an $a$-reverse to the last $a$ contestants, which by inductive hypothesis can be achieved in exactly $2^a-(a+1)$ moves. This results in the following order: $$C_{a+1},C_1,C_2,\ldots,C_a$$From here, we make $C_a$ jump to the front, then $C_{a-1}$ jump behind her, and so on until $C_1$ jumps in front of $C_{a+1}$. This clearly takes $a$ moves and results in this order: $$C_a,C_{a-1},C_{a-2},\ldots,C_1,C_{a+1}$$Finally, we apply an $a$-reverse to the first $a$ contestants, which takes exactly $2^a-(a+1)$ moves. After this, the contestants are lined up in the order: $$C_1,C_2,C_3,\ldots,C_{a+1}$$In total, this process takes: $$2^a-(a+1)+a+2^a-(a+1)=2^{a+1}-(a+2)$$moves, completing the induction and proving the claim. $\blacksquare$ This implies that the jury can line up the contestants in reverse order, then apply an $n$-reverse to get $2^n-(n+1)$ euros. Combining this with our upper bound implies the desired answer. $\blacksquare$ Also, the original text should say "The $n$ contestants", no? Remark (on motivation): As with most of the other solutions presented here, I basically ignored (a) since it would be proved by (b) anyways. That being said, when I first worked on the problem I worked on proving (a) first. After a bit of experimentation I got to the claim that the contestant $C_{n-k}$ can only move forward a finite number of times, and proved it with a similar approach to the one given in the proof of the upper bound, only without numbers. After a bit of playing around with smaller cases to figure out part (b), it became somewhat clear that $C_{n-k}$ could only move forward at most $2^k-1$ times, after which it's not too difficulty to adapt the proof of the claim to show this (just add numbers).

My solution for $a$ is using monovariant - We assign a weight of $ti$ to $C_i$ where t is number of students ahead of $C_i$ , and then by simple counting principles , we can deduce that, in each move our total weight is decreasing but it must be non negative , hence the process must terminate and we will be done.

Sol for part a :- We'll prove that if the contestants are assigned any n different natural numbers then the process will end in a finite no. of moves. We'll induct on n. For n=1, it is trivial For n=2, if the contestant, who is in the 2nd position, is not assigned 1 then the process ends in 0 move otherwise she is assigned 1 & the process ends in 1 move (as she will move to first position & it ends). Now suppose the process ends in a finite no. of moves for n=1,....,k We'll prove that the process ends ends in a finite no. of moves for n=k+1. Also if S is a set of contestants in which this process happens,then N(S) denote the no. of moves taken for the process to end. Suppose the maximal index assigned to a contestant is r. Clearly C_r can't move ahead as r≥n. Let C_r be at kth position at some point , Let the set of people ahead of C_r & behind of C_r be J & K respectively. By induction hypothesis C_r remains at kth postion for atmost N(J)+N(K) moves. After that either the process ends or in the next move C_r goes to (k+1)th position. This completes the proof.

Took a hint on how to prove the bound. Let $a_{k}$ denote the number of times $C_{k}$ jumps. Note that $C_{i}$ can jump over $C_{j}$ atmost $1+a_{j}$ times, which gives us: \[a_{i} \leq (a_{i+1}+1) + \dots (a_{n}+1)\]Note that $a_{n} = 0$, now we can induct to get that $a_{i} = 2^{n-i} - 1$, just sum this over to get that the judges can atmost extort $2^{n} - (n+1)$ euros from innocent contestants. The construction is pretty trivial. Take $C_{N}$ in the first position, now sort the things before $C_{N}$, which will take atmost $S(N-1)$ moves, now after that is sorted we we'll take $C_{N}$ in the last place and then do those $S(N-1)$ moves again, which gives us $2^{N} - (N+1)$.

similar to USAMO 2010 P2

We claim that the Jury can get at most $2^n-(n+1)$ euros, which indeed terminates the process. Let $a_k$ be the number of times that $C_k$ moves, and call a move cutting. Since $C_i$ cuts $i$ places, $C_i$ always cuts some $C_j$ with $j>i$, and since $C_i$ cuts $C_j$ at most $1+a_j$ times, we have $$a_k\le (a_{k+1}+1)+(a_{k+2}+1)+...+(a_n+1)\stackrel{a_n=0}{\implies}a_i\le 2^{n-i}-1$$by induction. By summing over all k, we get our claimed answer (let this be $b_n$). As for the construction, from the back to front, the order is $C_1C_2...C_n$, which works because in $b_{n-1}$ moves the sequence goes to $C_{n-1}C_{n-2}...C_1C_n$, in another $b_{n-1}$ moves (having $C_1$ cut $C_n$, then $C_2$, etc.) it goes to $C_nC_1C_2...C_{n-1}$, and in another $b_{n-1}$ moves it goes to $C_nC_{n-1}...C_1$, from where there are no more moves. Since $b_2=1$ and $b_n=2b_{n-1}+n-1$, indeed, our answer $b_n$ is of the form $2^n-(n+1)$ by induction. $\blacksquare$ Remark. The equality case construction serves as a sanity check that our estimates are accurate.

Ooo ! so close I did Part A by nested induction Found the answer for Part B(but made a mistake in my proof)

Very nice monovariant-esque problem. We first label the spots in the queue from front to back as $1$, $2$, all the way till $n$. Call a contestant $C_i$ tired if for all $j \geq i$, $C_j$ is in spot $j$. A lazy configuration is one where the jury may not make any more moves. Claim: The $n$ contestants reach a lazy configuration in at most $2^n - (n + 1)$ moves. Proof. We induct. The base case is easy to verify. Now say we have shown the claim holds for $n - 1$ contestants, so that it suffices to show it holds for $n$ contestants. Note that $C_n$ may never move forwards in the queue. Lemma: In $2^{n-1} - 1$ moves, $C_n$ will be tired. Proof. Say there are $k$ people behind $C_n$ in the original order. Note that by induction, these $k$ people take at most $2^{k} - (k+1)$ moves to reach a lazy configuration. Then eventually each contest $C_i$ behind $C_n$ must move in front of her, in a total of $k$ moves. This provides a bound of $2^k - (k+1) + k = 2^k - 1$ moves. This is maximized at $k = n - 1$ for our desired bound. To see that this is optimal say that some contestant $C_i$ initially behind $C_n$ leaves before a lazy position of the $k$ contestants is reached. This is either sub-optimal, or does not affect our bound, as desired. $\square$ Now from our induction $C_n$ is tired in at most $2^{n-1} - 1$ moves. Clearly then we may disregard $C_n$ and induct downwards to $n - 1$ contestants, as $C_n$ does not affect the ability of other contestants to move forwards, nor is she able to move herself. Then it takes the remaining $n-1$ contestants at most $2^{n-1} - n$ moves to reach a lazy configuration. Thus we have a final bound for $n$ contestants of, \begin{align*} 2^{n-1} - 1+ 2^{n-1} - n = 2^n - (n+1) \end{align*}which proves our initial claim. $\square$ Then for construction order the contestants in reverse order, namely $C_n$ till $C_1$ from front to back. Then move the person furthest behind in the queue that is not yet tired. This can easily be shown to work. Solve/Writeup: $1$ hour

The answer is $2^n-(n+1)$. Note that the process stops, the contestants must be in the order $C_n, C_{n-1}, \dots, C_1$. Claim: $C_{n-k}$ can move at most $2^k-1$ times. Proof: We induct on $k$. The base case is $k=0$, $C_n$ clearly cannot move. Now assume the claim hold for some $k$. Each time she moves, $C_{n-(k+1)}$ will move over at least one of $C_n, C_{n-1}, \dots, C_{n-k}$. If she moves over some contestant $C_{n-i}$ twice, $C_{n-i}$ must have moved back over $C_k$, so $C_{n-(k+1)}$ moves over $C_{n-i}$ at most $2^i$ times. Therefore, $C_{n-(k+1)}$ moves at most $\sum_{i=0}^k 2^i = 2^{k+1}-1$ times. Thus, there are at most $$\sum_{k = 0}^{n-1} 2^{k}-1 = 2^n - (n+1)$$moves. We now prove this is achievable. Claim: If the contestants are ordered $C_1, C_2, \dots, C_n$, we can make $2^n-(n+1)$ moves. Proof. We induct on $n$. The base case $n=1$ is clearly true. Now assume the claim holds for some $n$, we will prove it holds for $n+1$. First, we order the first $n$ contestants in $2^n-(n+1)$ moves. Then the contestants are in the order $C_n, C_{n-1}, \dots, C_1, C_{n+1}$. We start with $C_1$ and move each contestant over $C_{n+1}$, which takes $n$ moves. Now the order is $C_{n+1}, C_1, C_2, \dots, C_n$, and we can order the last $n$ contestants in $2^n-(n+1)$ moves. This takes a total of $2(2^n-(n+1)) + n = 2^{n+1} - (n+2)$ moves, as desired.

Consider imagining the contestants jumping over other contestants heads in the queue for fun. Let $c_m$ be the number of jumps contestant $C_m$ makes. Then notice that every time contestant $C_m$ makes a jump, she flies over at least one contestant $C_n$ such that $n > m$ by Pigeonhole. So then in order to maximize $c_m$, every time $C_n$ jumps over $C_m$, $C_m$ would jump in order to satisfy the previous requirement giving us the recursion $c_m \leq \sum_{i = m+1}^{n} c_i$, and $c_n = 0$ so $c_m \leq 2^{n-m + 1} - 1$ is our bound, so summing gives $c_1 + c_2 + \dots \leq 2^{n} - n - 1$. We claim that the ordering $C_1C_2C_3 \dots C_n$ will satisfy our maximal bound by induction with our base case being obviously true. Then after $2^{n-1} - n$ moves, the ordering will becomes $C_{n-1}C_{n-2} \dots C_1C_n$ and after another $n-1$ moves it becomes $C_nC_1C_2 \dots C_{n-1}$. Then apply our induction again on $C_1C_2\dots$ to get another $2^{n-1} - n$ to get a total of $2^n - n - 1$ euros as desired.

The answer is $2^n - n - 1$. The construction can be shown by recursion: for example, for $n=5$, the process \[54321 \to 51234 \to 43215 \to 12345\]can be shown recursively to attain the same number of euros as the answer claims. To prove the bound, we use a monovariant. At any point during the process, let $f(i)$ denote the number of higher-numbered contestants in front of $C_i$. We claim that \[\sum_{i=1}^n f(i) 2^{i-1}\]decreases at each step. In other words, this is the number of inversions, where an inversion $a>b$ is weighted $2^b$. This decreases at each step since the contestant $a$ moving forwards must cut some contestant with a higher number than herself – this breaks an inversion with weight $2^{a}$, and even if this contestant forms an inversion with all other contestants, this adds at most \[1+ 2 + 4+ \dots + 2^{a-1} < 2^a\]to the monovariant. By rearrangement, the maximum value the monovariant could start out with is \[\sum_{i=1}^n (i-1) 2^{i-1} = 2^n - n- 1.\]