Maths Olympiad Prep

Library / /24 of 25

Combinatorics Difficulty 8.2 Shortlist Prove it European Girls' Mathematical Olympiad (EGMO)

Problem:

The nn contestants of an EGMO are named C1,,CnC_{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 ii with 1in1 \leq i \leq n.
- If contestant CiC_{i} has at least ii other contestants in front of her, she pays one euro to the Jury and moves forward in the queue by exactly ii positions.
- If contestant CiC_{i} has fewer than ii 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 nn the maximum number of euros that the Jury can collect by cunningly choosing the initial order and the sequence of moves.

(Hungary)

Solutions — 2

Solution 1

Solution:

The maximal number of euros is 2nn12^{n}-n-1.

To begin with, we show that it is possible for the Jury to collect this number of euros. We argue by induction. Let us assume that the Jury can collect MnM_{n} euros in a configuration with nn contestants. Then we show that the Jury can collect at least 2Mn+n2 M_{n}+n moves in a configuration with n+1n+1 contestants. Indeed, let us begin with all the contestants lined up in reverse order. In the first MnM_{n} moves the Jury keeps Cn+1C_{n+1} in first position and reverses the order of the remaining contestants, then in the next nn moves all contestants C1,,CnC_{1}, \ldots, C_{n} (in this order) jump over Cn+1C_{n+1} and end up in the first nn positions of the line in reverse order, and finally in the last MnM_{n} moves the Jury rearranges the first nn positions.

Since M1=0M_{1}=0 and Mn+12Mn+nM_{n+1} \geq 2 M_{n}+n, an easy induction shows that Mn2nn1M_{n} \geq 2^{n}-n-1.

Let us show now that at most 2nn12^{n}-n-1 moves are possible. To this end, let us identify a line of contestants with a permutation σ\sigma of {1,,n}\{1, \ldots, n\}. To each permutation we associate the set of reverse pairs
R(σ):={(i,j):1i<jn and σ(i)>σ(j)} R(\sigma):=\{(i, j): 1 \leq i<j \leq n \text{ and } \sigma(i)>\sigma(j)\}
and the nonnegative integer
W(σ):=(i,j)R(σ)2i W(\sigma):=\sum_{(i, j) \in R(\sigma)} 2^{i}
which we call the total weight of the permutation. We claim that the total weight decreases after any move of the contestants. Indeed, let us assume that CiC_{i} moves forward in the queue, let σ\sigma be the permutation before the move, and let σ\sigma' denote the permutation after the move. Since CiC_{i} jumps over exactly ii contestants, necessarily she jumps over at least one contestant CjC_{j} with index j>ij>i. This means that the pair (i,j)(i, j) is reverse with respect to σ\sigma but not with respect to σ\sigma', and this yields a reduction of 2i2^{i} in the total weight. On the other hand, the move by CiC_{i} can create new reverse pairs of the form (k,i)(k, i) with k<ik<i, but their total contribution is at most
20+21++2i1=2i1 2^{0}+2^{1}+\ldots+2^{i-1}=2^{i}-1
In conclusion, when passing from σ\sigma to σ\sigma', at least one term 2i2^{i} disappears from the computation of the total weight, and the sum of all the new terms that might have been created is at most 2i12^{i}-1. This shows that W(σ)W(σ)1W\left(\sigma'\right) \leq W(\sigma)-1.

We conclude by observing that the maximum possible value of W(σ)W(\sigma) is realized when all pairs are reverse, in which case
W(σ)=i=1n(i1)2i=2nn1. W(\sigma)=\sum_{i=1}^{n}(i-1) 2^{i}=2^{n}-n-1.
This proves that the number of moves is less than or equal to 2nn12^{n}-n-1, and in particular it is finite.

Solution 2

Solution:

As in the previous solution, the fundamental observation is again that, when a contestant CiC_{i} moves forward, necessarily she has to jump over at least one contestant CjC_{j} with j>ij>i.

Let us show now that the process ends after a finite number of moves. Let us assume that this is not the case. Then at least one contestant moves infinitely many times. Let i0i_{0} be the largest index such that Ci0C_{i_{0}} moves infinitely many times. Then necessarily Ci0C_{i_{0}} jumps infinitely many times over some fixed Cj0C_{j_{0}} with j0>i0j_{0}>i_{0}. On the other hand, we know that Cj0C_{j_{0}} makes only a finite number of moves, and therefore she can precede Ci0C_{i_{0}} in the line only a finite number of times, which is absurd.

In order to estimate from above the maximal number of moves, we show that the contestant CiC_{i} can make at most 2ni12^{n-i}-1 moves. Indeed, let us argue by "backward extended induction". To begin with, we observe that the estimate is trivially true for CnC_{n} because she has no legal move.

Let us assume now that the estimate has been proved for Ci,Ci+1,,CnC_{i}, C_{i+1}, \ldots, C_{n}, and let us prove it for Ci1C_{i-1}. When Ci1C_{i-1} moves, at least one contestant CjC_{j} with j>i1j>i-1 must precede her in the line. The initial configuration can provide at most nin-i contestants with larger index in front of Ci1C_{i-1}, which means at most nin-i moves for Ci1C_{i-1}. All other moves are possible only if some contestant in the range Ci,Ci+1,,CnC_{i}, C_{i+1}, \ldots, C_{n} jumps over Ci1C_{i-1} during her moves. As a consequence, the total number of moves of Ci1C_{i-1} is at most
ni+k=in(2nk1)=2ni+11 n-i+\sum_{k=i}^{n}\left(2^{n-k}-1\right)=2^{n-i+1}-1
Summing over all indices we obtain that
i=1n(2ni1)=2nn1 \sum_{i=1}^{n}\left(2^{n-i}-1\right)=2^{n}-n-1
which gives an estimate for the total number of moves.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.