Shortlist 2024, C1¶
Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : Australia
Concepts : Invariants et monovariants · Double comptage
Solution officielle : Shortlist officielle 2024 (avec solutions), section C1 (livret PDF)
Énoncé¶
Let \(n\) be a positive integer. A class of \(n\) students run \(n\) races, in each of which they are ranked with no draws. A student is eligible for a rating \((a, b)\) for positive integers \(a\) and \(b\) if they come in the top \(b\) places in at least \(a\) of the races. Their final score is the maximum possible value of \(a - b\) across all ratings for which they are eligible.
Find the maximum possible sum of all the scores of the \(n\) students.
Indices : les idées clés
- Le classement identique : si les élèves arrivent dans le même ordre à chaque course, l'élève classé \(k\)-ième a pour score \(n - k\), et la somme vaut \(\frac{n(n-1)}{2}\).
- Monovariant (solution 1) : des modifications successives des résultats, qui ne font jamais baisser le score total, ramènent à un classement identique.
- Double comptage (solutions 2 et 3) : la somme de tous les rangs (ou de poids \(1 - \frac{k}{n}\)) sur toutes les courses est connue, et majore la somme des scores.
- Échanger maximum et somme (solution 4) : pour des seuils \(b\) fixés, chaque course se maximise séparément, et le même classement est optimal pour toutes.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2024 (quatre solutions et une remarque).
Réponse : la somme maximale des scores est \(\frac{n(n-1)}{2}\).
Solution 1¶
La valeur est atteinte quand les élèves finissent dans le même ordre à chaque course : l'élève classé \(k\)-ième partout est éligible pour \((n, k)\), d'où un score \(n - k\) (et pas plus, puisque pour \(b < k\) il n'est jamais dans les \(b\) premiers), et \(\sum_{k=1}^{n} (n - k) = \frac{n(n-1)}{2}\).
Majoration. On va appliquer aux résultats des courses une suite de modifications, dont aucune ne diminue le score total (un monovariant), de sorte qu'après \(k\) modifications les \(k\) premières places soient les mêmes dans toutes les courses. On dit qu'un élève est noté à la \(b\)-ième place si son score vaut \(a - b\) parce qu'il est dans les \(b\) premiers dans \(a\) courses, \(b\) étant minimal avec cette propriété.
Supposons que les \(k - 1\) premières places soient identiques dans toutes les courses, et regardons les élèves notés à la \(k\)-ième place.
S'il n'y en a aucun, soit \(\ell > k\) minimal tel qu'un élève \(S\) soit noté à la \(\ell\)-ième place. Dans chaque course où \(S\) occupe l'une des places \(k\) à \(\ell\) (il y en a au moins \(\ell\), sinon \(S\) aurait un score strictement négatif, alors que la notation \((n, n)\) lui donne \(0\)), on réordonne les élèves occupant les places \(k\) à \(\ell\) de sorte que \(S\) finisse \(k\)-ième (l'ordre des autres étant arbitraire). Désormais \(S\) est noté à la \(k\)-ième place, son score a augmenté de \(\ell - k\), et aucun autre score n'a diminué (certains ont pu augmenter).
On sait maintenant que les \(k - 1\) premières places sont identiques dans toutes les courses et qu'au moins un élève est noté à la \(k\)-ième place. Choisissons-en un, \(S\). Dans chaque course où \(S\) finit après la \(k\)-ième place, on l'échange avec l'élève \(T\) qui est \(k\)-ième, sans toucher aux autres. Chaque échange augmente le score de \(S\) de \(1\) et diminue celui de \(T\) d'au plus \(1\) : le total ne diminue pas. À la fin, les \(k\) premières places sont identiques dans toutes les courses, et le score total n'a pas diminué.
En répétant cela \(n\) fois, on aboutit à un classement identique dans toutes les courses, dont le total vaut \(\frac{n(n-1)}{2}\). Le total initial était donc au plus \(\frac{n(n-1)}{2}\). \(\blacksquare\)
Solution 2¶
La valeur est atteinte avec le même classement dans les \(n\) courses. En prenant \(a = b = n\), on voit que chaque élève a un score positif ou nul.
Rangs d'un élève. Considérons un élève dont les rangs dans les courses sont \(r_1, r_2, \ldots, r_n\) et dont le score est \(s\). Montrons que
Quitte à renuméroter, \(r_1 \leq r_2 \leq \cdots \leq r_n\). L'élève est éligible pour \((a, b)\) si et seulement si \(r_a \leq b\), donc son score est \(s = \max_k (k - r_k)\) : il existe \(k\) avec \(s + 1 \leq k \leq n\) et \(k - r_k = s\). Pour maximiser \(\sum_i r_i\) en gardant ce score, on peut remplacer \(r_1, \ldots, r_{k-1}\) par \(r_k\) et \(r_{k+1}, \ldots, r_n\) par \(n\). Ainsi
La dernière inégalité vient de ce que, pour \(s + 1 \leq k \leq n\), la quantité \(k(n + s - k)\) (fonction concave de \(k\)) est minimale en \(k = n\), où elle vaut \(ns\).
Double comptage. La somme des rangs de tous les élèves dans toutes les courses vaut \(n \cdot \frac{n(n+1)}{2} = \frac{n^2(n+1)}{2}\). Si \(t\) est la somme de tous les scores, en sommant (1) sur les élèves :
ce qui donne \(t \leq \frac{n(n-1)}{2}\). \(\blacksquare\)
Solution 3¶
Dans chaque course, attribuons à l'élève classé \(k\)-ième le poids \(1 - \frac{k}{n}\) (positif ou nul). Si un élève est dans les \(b\) premiers dans au moins \(a\) courses, la somme de ses poids est au moins
Ainsi la somme des poids d'un élève sur toutes les courses est au moins égale à son score, et la somme de tous les poids (sur tous les élèves et toutes les courses) majore la somme des scores. Par double comptage, la somme des poids dans une course vaut \(\sum_{k=1}^{n} \left(1 - \frac{k}{n}\right) = \frac{n-1}{2}\), donc la somme de tous les poids vaut \(\frac{n(n-1)}{2}\).
Il y a égalité si et seulement si, pour chaque élève, les valeurs \(a\) et \(b\) donnant son score vérifient \(a = n\) et l'élève finit exactement à la \(b\)-ième place dans les \(n\) courses, c'est-à-dire si le classement est le même dans toutes les courses. \(\blacksquare\)
Solution 4¶
Donnons-nous un entier positif \(b(S)\) pour chaque élève \(S\). Notons \(a_b(S)\) le nombre de courses où \(S\) finit dans les \(b(S)\) premiers, et \(\mathrm{score}_b(S) = a_b(S) - b(S)\). Pour une course \(r\), notons \(I_b(S, r)\) le nombre valant \(1\) si \(S\) finit dans les \(b(S)\) premiers dans la course \(r\), et \(0\) sinon ; ainsi \(a_b(S) = \sum_r I_b(S, r)\).
Le problème demande le maximum, sur tous les résultats possibles des courses, de
On peut échanger les deux maximums. Pour un choix de \(b\) fixé, la somme \(\sum_S I_b(S, r)\) est maximisée (pas forcément de façon unique) par un certain classement de la course \(r\), et ce classement est le même pour toutes les courses. Donc la somme maximale des scores est atteinte quand les élèves sont classés de la même façon dans toutes les courses, ce qui donne la valeur \(\frac{n(n-1)}{2}\). \(\blacksquare\)
Remarques¶
Remarque (une modification trop naïve). Dans la solution 1, il est tentant de procéder plus simplement : trouver deux élèves \(S\) et \(T\) notés respectivement aux places \(k < \ell\) mais tels que \(S\) finisse après \(T\) dans une course, et les échanger dans cette course. Mais un tel échange peut faire baisser le total. Par exemple, avec \(k = 1\) et \(\ell = 4\), si dans une course \(S\) finit \(6\)e et \(T\) finit \(3\)e, l'échange retire à \(T\) une course comptant pour son score sans en ajouter une à \(S\).