IMO2024 Shortlisted Problems

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 $k$ such modifications the first $k$ positions are the same in every race. Say that a student is scored on the $b^{\text{th}}$ place if their score is $a-b$ because they came in the top $b$ places in $a$ of the races and $b$ is minimal with this property for that student.

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

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

Repeating this $n$ times yields the required result.

Note that taking $a=b=n$ shows each student has a nonnegative score. Consider a student who has race ranks $r_1,r_2,\dots ,r_n$ and a final score of $s$. We first prove that $$\sum _i{r}_i⩽n(n-s).$$ Without loss of generality, suppose that $r_1⩽r_2⩽\cdots ⩽r_n$. There must exist some $k$ with $s+1⩽k⩽n$ and $k-r_k=s$. In order to maximise ${\sum }_i{r}_i$ while retaining the score of $s$, we can replace each of $r_1,\dots ,r_{k-1}$ by $r_k$, and replace each of $r_{k+1},\dots ,r_n$ by $n$. Then the sum is $$\sum _i{r}_i⩽k{r}_k+(n-k)n=n^2-k\left(n-r_k\right)=n^2-k(n+s-k)⩽n^2-sn\text{\hspace{1em}(1)}$$ The final inequality follows from the fact that given $s+1⩽k⩽n$, the quantity $k(n+s-k)$ is minimised when $k=n$.

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

---

Alternative solution.

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

Note that taking $a=b=n$ shows each student has a nonnegative score. Consider a student who has race ranks $r_1,r_2,\dots ,r_n$ and a final score of $s$. We first prove that $$\sum _i{r}_i⩽n(n-s).$$ Without loss of generality, suppose that $r_1⩽r_2⩽\cdots ⩽r_n$. There must exist some $k$ with $s+1⩽k⩽n$ and $k-r_k=s$. In order to maximise ${\sum }_i{r}_i$ while retaining the score of $s$, we can replace each of $r_1,\dots ,r_{k-1}$ by $r_k$, and replace each of $r_{k+1},\dots ,r_n$ by $n$. Then the sum is $$\sum _i{r}_i⩽k{r}_k+(n-k)n=n^2-k\left(n-r_k\right)=n^2-k(n+s-k)⩽n^2-sn\text{\hspace{1em}(1)}$$ The final inequality follows from the fact that given $s+1⩽k⩽n$, the quantity $k(n+s-k)$ is minimised when $k=n$.

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

---

Alternative solution.

In each race, assign the student in the $k^{\text{th}}$ place a weight of $1-\frac{k}{n}$. If a student finishes in the top $b$ places in at least $a$ of the races, the total of their weights is at least $a\left(1-\frac{b}{n}\right)=a-b\left(\frac{a}{n}\right)⩾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 $\frac{n-1}{2}$, so the sum of all weights across all races is $\frac{n(n-1)}{2}$. Equality is achieved if and only if, for each student, the values of $b$ and $a$ determining that student's score have $a=n$ and they finish in exactly the $b^{\text{th}}$ place in all $n$ races; that is, if the students are ranked the same in every race.

---

Alternative solution.

Given a positive integer $b(S)$ for each student $S$, define $a_b(S)$ to be the number of races in which $S$ finished in the top $b(S)$ places, and define ${\mathrm{score}}_b(S)=a_b(S)-b(S)$; for a race $r$, let $I_b(S,r)$ be 1 if $S$ finished in the top $b(S)$ places in race $r$ and 0 otherwise, so $$a_b(S)=\sum _r{I}_b(S,r)$$ Then the problem asks for the maximum across all possible results of the races of $$\underset{b}{\max }\sum _S{\mathrm{score}}_b(S)=\underset{b}{\max }\left(\sum _r\sum _S{I}_b(S,r)-\sum _{S}b(S)\right).$$ Given $b$, the sum ${\sum }_S{I}_b(S,r)$ is maximised (not necessarily uniquely) for some choice of the rankings in race $r$, 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.