Maths Olympiad Prep

Library / /9 of 15

Combinatorics Difficulty 8.8 Shortlist Prove it IMO

Let nn be a positive integer. A class of nn students run nn races, in each of which they are ranked with no draws. A student is eligible for a rating (a,b)(a, b) for positive integers aa and bb if they come in the top bb places in at least aa of the races. Their final score is the maximum possible value of aba-b across all ratings for which they are eligible.
Find the maximum possible sum of all the scores of the nn students.

Solutions — 4

Solution 1

The answer can be achieved by the students finishing in the same order in every race. To show that this is the maximum, we will apply a series of modifications to the results of the races, each of which does not decrease the total score, such that after kk such modifications the first kk positions are the same in every race. Say that a student is scored on the bthb^{\text{th}} place if their score is aba-b because they came in the top bb places in aa of the races and bb is minimal with this property for that student.

Supposing that the first k1k-1 positions are the same in every race, look at the students scored on the kthk^{\text{th}} place. If there are no such students, let >k\ell>k be minimal such that some student SS is scored on the th\ell^{\text{th}} place. Then, in every race where SS appears in any place from the kthk^{\text{th}} through the th\ell^{\text{th}} inclusive (of which there must be at least \ell, otherwise SS would achieve a higher rating of 0 based on the nthn^{\text{th}} place), reorder the students in places kk through \ell so that SS finishes in the kthk^{\text{th}} place instead (and otherwise the ordering of those students is arbitrary). Now SS is scored on the kthk^{\text{th}} place, their score has gone up by k\ell-k and no other scores have gone down (some might have gone up as well).

Now we know that the first k1k-1 positions are the same in every race and at least one student is scored on the kthk^{\text{th}} place. Pick one such student SS. In each race where SS finishes behind the kthk^{\text{th}} place, swap them with the student TT who finishes in the kthk^{\text{th}} place, leaving the positions of all other students unchanged. Each such swap increases the score of SS by 1 and decreases the score of TT by at most 1, so such swaps do not decrease the total score. At the end of this process, the first kk positions are the same in every race and the total score has not decreased.

Repeating this nn times yields the required result.

Note that taking a=b=na=b=n shows each student has a nonnegative score. Consider a student who has race ranks r1,r2,,rnr_{1}, r_{2}, \ldots, r_{n} and a final score of ss. We first prove that
irin(ns). \sum_{i} r_{i} \leqslant n(n-s) .
Without loss of generality, suppose that r1r2rnr_{1} \leqslant r_{2} \leqslant \cdots \leqslant r_{n}. There must exist some kk with s+1kns+1 \leqslant k \leqslant n and krk=sk-r_{k}=s. In order to maximise iri\sum_{i} r_{i} while retaining the score of ss, we can replace each of r1,,rk1r_{1}, \ldots, r_{k-1} by rkr_{k}, and replace each of rk+1,,rnr_{k+1}, \ldots, r_{n} by nn. Then the sum is
irikrk+(nk)n=n2k(nrk)=n2k(n+sk)n2sn(1) \sum_{i} r_{i} \leqslant k r_{k}+(n-k) n=n^{2}-k\left(n-r_{k}\right)=n^{2}-k(n+s-k) \leqslant n^{2}-s n \tag{1}
The final inequality follows from the fact that given s+1kns+1 \leqslant k \leqslant n, the quantity k(n+sk)k(n+s-k) is minimised when k=nk=n.

The sum of ranks of all students across all races is n2(n+1)2\frac{n^{2}(n+1)}{2}. If the total of all student scores is tt, then (1) implies
n2(n+1)2n3tn \frac{n^{2}(n+1)}{2} \leqslant n^{3}-t n
This rearranges to tn(n1)2t \leqslant \frac{n(n-1)}{2}, as required.

Solution 2

The answer can be achieved by having the same ranking for all nn races.

Note that taking a=b=na=b=n shows each student has a nonnegative score. Consider a student who has race ranks r1,r2,,rnr_{1}, r_{2}, \ldots, r_{n} and a final score of ss. We first prove that
irin(ns). \sum_{i} r_{i} \leqslant n(n-s) .
Without loss of generality, suppose that r1r2rnr_{1} \leqslant r_{2} \leqslant \cdots \leqslant r_{n}. There must exist some kk with s+1kns+1 \leqslant k \leqslant n and krk=sk-r_{k}=s. In order to maximise iri\sum_{i} r_{i} while retaining the score of ss, we can replace each of r1,,rk1r_{1}, \ldots, r_{k-1} by rkr_{k}, and replace each of rk+1,,rnr_{k+1}, \ldots, r_{n} by nn. Then the sum is
irikrk+(nk)n=n2k(nrk)=n2k(n+sk)n2sn(1) \sum_{i} r_{i} \leqslant k r_{k}+(n-k) n=n^{2}-k\left(n-r_{k}\right)=n^{2}-k(n+s-k) \leqslant n^{2}-s n \tag{1}
The final inequality follows from the fact that given s+1kns+1 \leqslant k \leqslant n, the quantity k(n+sk)k(n+s-k) is minimised when k=nk=n.

The sum of ranks of all students across all races is n2(n+1)2\frac{n^{2}(n+1)}{2}. If the total of all student scores is tt, then (1) implies
n2(n+1)2n3tn \frac{n^{2}(n+1)}{2} \leqslant n^{3}-t n
This rearranges to tn(n1)2t \leqslant \frac{n(n-1)}{2}, as required.

Solution 3

In each race, assign the student in the kthk^{\text{th}} place a weight of 1kn1-\frac{k}{n}. If a student finishes in the top bb places in at least aa of the races, the total of their weights is at least a(1bn)=ab(an)aba\left(1-\frac{b}{n}\right)=a-b\left(\frac{a}{n}\right) \geqslant a-b. Thus the sum of a student's weights across all races is at least their score, and so the sum of all weights for all students across all races is at least the sum of all the scores of all students. The sum of weights in each race is n12\frac{n-1}{2}, so the sum of all weights across all races is n(n1)2\frac{n(n-1)}{2}. Equality is achieved if and only if, for each student, the values of bb and aa determining that student's score have a=na=n and they finish in exactly the bthb^{\text{th}} place in all nn races; that is, if the students are ranked the same in every race.

Solution 4

Given a positive integer b(S)b(S) for each student SS, define ab(S)a_{b}(S) to be the number of races in which SS finished in the top b(S)b(S) places, and define scoreb(S)=ab(S)b(S)\operatorname{score}_{b}(S)=a_{b}(S)-b(S); for a race rr, let Ib(S,r)I_{b}(S, r) be 1 if SS finished in the top b(S)b(S) places in race rr and 0 otherwise, so
ab(S)=rIb(S,r) a_{b}(S)=\sum_{r} I_{b}(S, r)
Then the problem asks for the maximum across all possible results of the races of
maxbSscoreb(S)=maxb(rSIb(S,r)Sb(S)). \max_{b} \sum_{S} \operatorname{score}_{b}(S)=\max_{b}\left(\sum_{r} \sum_{S} I_{b}(S, r)-\sum_{S} b(S)\right) .
Given bb, the sum SIb(S,r)\sum_{S} I_{b}(S, r) is maximised (not necessarily uniquely) for some choice of the rankings in race rr, which is the same choice for every race. So the maximum possible sum of the scores of all the students occurs when all students are ranked the same in all races, which yields the given answer.

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 and solution reproduced as published; topic and difficulty added by this site.