Maths Olympiad Prep

Library / /135 of 136

Combinatorics Difficulty 9.1 IMO level Prove it Hong Kong

In a chess tournament there were nn (n>10n > 10) participants. Each participant plays against another exactly once. If a game ends in a draw, each participant gets 1 point, otherwise the winner gets 2 points and the loser gets none. At the end of the tournament, every participant found that half of his/her score came from games played against the ten participants with the lowest scores. This is true even for each of the ten participants with the lowest scores, (i.e. half of the scores of each of the 10 lowest scorers comes from playing with other 9 lowest scorers). Find the possible value(s) of nn.

Solution

nn can only be 25.

We first provide an example for the case n=25n = 25. Consider 10 participants A1,A2,,A10A_1, A_2, \dots, A_{10} in group A\mathcal{A}, and 15 participants B1,B2,,B15B_1, B_2, \dots, B_{15} in group B\mathcal{B}. Suppose the games played between 2 participants in the same group end in a draw. For the games played between 2 participants in different groups, the results are given below, where OO means a draw, while an empty box means the group B\mathcal{B} participant wins.

A1_1A2_2A3_3A4_4A5_5A6_6A7_7A8_8A9_9A10_{10}
B1_1OOOOOO
B2_2OOOOOO
B3_3OOOOOO
B4_4OOOOOO
B5_5OOOOOO
B6_6OOOOOO
B7_7OOOOOO
B8_8OOOOOO
B9_9OOOOOO
B10_{10}OOOOOO
B11_{11}OOOOOOO
B12_{12}OOOOOOO
B13_{13}OOOOOOO
B14_{14}OOOOOOOO
B15_{15}OOOOOOOO

The score of each participant in group A\mathcal{A} is 9+9=189+9=18, where 9 points come from the games played between them. The score of each participant in group B\mathcal{B} is 14+(6+2×4)=2814+(6+2\times4)=28, where 14 points come from the games played between them. So the conditions are satisfied.

Now, note that the two participants in a game always gain 2 points in total. Therefore, the total score of all participants is
2(n2)=n(n1). 2\binom{n}{2} = n(n-1).

For the 10 participants with the lowest scores, their total score gained by the games played between them is 2(102)=902\binom{10}{2} = 90. Therefore, their total score is
2×90=180. 2 \times 90 = 180.
For the other n10n-10 participants, their total score gained by the games played between them is 2(n102)=(n10)(n11)2\binom{n-10}{2} = (n-10)(n-11). Note that this is half of their total score since the remaining half comes from the other games. Therefore, their total score is
2(n10)(n11). 2(n - 10)(n - 11).

Combining all these, we need 180+2(n10)(n11)=n(n1)180+2(n-10)(n-11) = n(n-1). This is the same as (n16)(n25)=0(n-16)(n-25) = 0. Thus, n=16,25n = 16, 25.

For n=16n = 16, the 10 participants with the lowest scores obtain 180 points in total, while the other 6 participants obtain 2(1610)(1611)=602(16 - 10)(16 - 11) = 60 points in total. Since 18010=18>10=606\frac{180}{10} = 18 > 10 = \frac{60}{6}, it is impossible that all those 10 participants have the lowest score. Therefore, n=16n = 16 is rejected, and n=25n = 25 is the only possibility.

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.