Maths Olympiad Prep

Library / /324 of 520

Combinatorics Difficulty 7.0 National olympiad Find the answer

Example 1 Given that after 20 gymnasts perform, 9 judges respectively assign them ranks from 1 to 20. It is known that, among the 9 ranks each athlete receives, the maximum and minimum differ by at most 3. Now, the sums of the ranks received by each person are arranged as c1c2c20c_{1} \leqslant c_{2} \leqslant \cdots \leqslant c_{20}. Find the maximum value of c1c_{1}. (All-Soviet Union, 2nd)

A number or a short expression. Spacing and $ signs are ignored.

Solution

Analysis and Solution First, note that the goal of the solution is c1Pc_{1} \leqslant P, which is equivalent to the existence of an ii such that ciPc_{i} \leqslant P. Therefore, estimating the total score of any player can provide an estimate for c1c_{1}.

To minimize the score (rank), it is desirable to have more judges rank the player first. Thus, we can estimate the score of the player who is ranked first the most. One case is self-evident, i.e., if a player gets 9 first places, it is clear that c19c_{1} \leqslant 9. Furthermore, when the "first" places are more evenly distributed, we should use an overall estimate, examining the total scores of the players who received first places. Let there be rr players who are ranked first.
(1) r=1r=1, then c1=9c_{1}=9.
(2) r=2r=2, then because there are 9 first places, at least one player AA gets 5 first places. Since the scores a player receives from different judges do not differ by more than 3, the other 4 scores of AA do not exceed 4. Therefore, the total score of AA is no more than 5+4×4=215+4 \times 4=21, so c121c_{1} \leqslant 21.
(3) r=3r=3, consider the total score SS of all players. They received a total of 9 first places, and there are another 18 ranks. Each rank's score is at most 4. Therefore, S9+9×3+9×4=72S \leqslant 9+9 \times 3+9 \times 4=72, so c1723=24c_{1} \leqslant \frac{72}{3}=24.
(4) r=4r=4, similarly estimate the total score of these 4 players, we have S90S \leqslant 90, so c1[904]=22c_{1} \leqslant\left[\frac{90}{4}\right]=22.
(5) r5r \geqslant 5, each of these rr players' scores does not exceed 4, thus there are at least 9r5×9=459 r \geqslant 5 \times 9=45 ranks not higher than 4. However, the 1 to 4 ranks given by 9 judges are at most 9×4=369 \times 4=36, which is a contradiction.

In summary, c124c_{1} \leqslant 24.
Finally, c1=24c_{1}=24 is possible. In fact, let c1=c2=c3=(1+1+1)+(3+3+3)+(4+4+4),c4=(2+2+2+2+2)+(5+5+5+5),c5=(2+2+2+2)+(5+5+5+5+5)c_{1}=c_{2}=c_{3}=(1+1+1)+(3+3+3)+(4+4+4), c_{4}=(2+2+2+2+2)+(5+5+5+5), c_{5}=(2+2+2+2)+(5+5+5+5+5), and ci=i+i++i(i=6,7,8,,20)c_{i}=i+i+\cdots+i (i=6,7,8, \cdots, 20). See the table below:
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline Player & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \cdots & 20 \\
\hline 1 & 1 & 3 & 4 & 2 & 5 & 6 & 7 & 8 & 9 & \cdots & 20 \\
\hline 2 & 1 & 3 & 4 & 2 & 5 & 6 & 7 & 8 & 9 & \cdots & 20 \\
\hline 3 & 1 & 3 & 4 & 2 & 5 & 6 & 7 & 8 & 9 & \cdots & 20 \\
\hline 4 & 3 & 4 & 1 & 2 & 5 & 6 & 7 & 8 & 9 & \cdots & 20 \\
\hline 5 & 3 & 4 & 1 & 2 & 5 & 6 & 7 & 8 & 9 & \cdots & 20 \\
\hline 6 & 3 & 4 & 1 & 5 & 2 & 6 & 7 & 8 & 9 & \cdots & 20 \\
\hline 7 & 4 & 1 & 3 & 5 & 2 & 6 & 7 & 8 & 9 & \cdots & 20 \\
\hline 8 & 4 & 1 & 3 & 5 & 2 & 6 & 7 & 8 & 9 & \cdots & 20 \\
\hline 9 & 4 & 1 & 3 & 5 & 2 & 6 & 7 & 8 & 9 & \cdots & 20 \\
\hline Rank Sum & 24 & 24 & 24 & 30 & 33 & 54 & 63 & 72 & 81 & \cdots & 180 \\
\hline
\end{tabular}

Therefore, the maximum value of c1c_{1} is 24.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.