Maths Olympiad Prep

Library / /392 of 520

Combinatorics Difficulty 6.0 AIME, harder Find the answer

15 There are 10 players A1,A2,,A10A_{1}, A_{2}, \cdots, A_{10}, their points are 9,8,7,6,5,4,3,2,1,09, 8, 7, 6, 5, 4, 3, 2, 1, 0, and their ranks are 1st, 2nd, 3rd, 4th, 5th, 6th, 7th, 8th, 9th, 10th. Now a round-robin tournament is held, that is, each pair of players will play exactly one match, and each match must have a winner. If the player with a higher rank wins the player with a lower rank, the winner gets 1 point, and the loser gets 0 points; if the player with a lower rank wins the player with a higher rank, the winner gets 2 points, and the loser gets 0 points. After all the matches, the total points of each player (the sum of the points obtained in this round-robin tournament and the previous points) are calculated, and the players are re-ranked according to the total points. Find the minimum value of the new champion's total points (ties are allowed).

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

Solution

15 If the new champion's score does not exceed 11 points, then A1A_{1} can win at most 2 games; A2A_{2} can win at most 3 games; A3A_{3} can win at most 4 games; A4A_{4} can win at most 5 games; A5A_{5} can increase his score by at most 6 points, but there are only 5 players with fewer points than him at the start. Therefore, if he increases his score by 6 points, he must win at least 1 game against players ranked higher than him, meaning he can win at most 4 games against players ranked lower, thus he can win at most 5 games; A6A_{6} can increase his score by at most 7 points, but there are only 4 players with fewer points than him at the start. Therefore, if he increases his score by 7 points, he must win at least 2 games against players ranked higher than him, meaning he can win at most 3 games against players ranked lower, thus he can win at most 5 games; A7A_{7} can increase his score by at most 8 points, but there are only 3 players with fewer points than him at the start. Therefore, if he increases his score by 8 points, he must win at least 3 games against players ranked higher than him, meaning he can win at most 2 games against players ranked lower, thus he can win at most 5 games; A8A_{8} can increase his score by at most 9 points, but there are only 2 players with fewer points than him at the start. Therefore, if he increases his score by 9 points, he must win at least 4 games against players ranked higher than him, meaning he can win at most 1 game against players ranked lower, thus he can win at most 5 games; A9A_{9} can increase his score by at most 10 points, but there is only 1 player with fewer points than him at the start. Therefore, if he increases his score by 10 points, he must win at least 5 games against players ranked higher than him, thus he can win at most 5 games; A10A_{10} can increase his score by at most 11 points, and he can win at most 5 games against players ranked higher than him, thus he can win at most 5 games.
In summary, the maximum number of games won by all players is 2+3+4+5×7=442+3+4+5 \times 7=44, but each match between two players results in one win, totaling C102=45\mathrm{C}_{10}^{2}=45 (games), which is a contradiction.
The following example shows that the new champion's cumulative score can be 12 points.
A1A_{1} wins against A2,A3,A4A_{2}, A_{3}, A_{4}, loses to A5,A6,A7,A8,A9,A10A_{5}, A_{6}, A_{7}, A_{8}, A_{9}, A_{10}, with a cumulative score of 9+3=129+3=12;
A2A_{2} wins against A3,A4,A5,A6A_{3}, A_{4}, A_{5}, A_{6}, loses to A7,A8,A9,A10A_{7}, A_{8}, A_{9}, A_{10}, with a cumulative score of 8+4=128+4=12;
A3A_{3} wins against A4,A5,A6,A7A_{4}, A_{5}, A_{6}, A_{7}, loses to A8,A9,A10A_{8}, A_{9}, A_{10}, with a cumulative score of 7+4=117+4=11;
A4A_{4} wins against A5,A6,A7,A8A_{5}, A_{6}, A_{7}, A_{8}, loses to A9,A10A_{9}, A_{10}, with a cumulative score of 6+4=106+4=10;
A5A_{5} wins against A6,A7,A8,A9A_{6}, A_{7}, A_{8}, A_{9}, loses to A10A_{10}, with a cumulative score of 5+2+4=115+2+4=11;
A6A_{6} wins against A7,A8,A9,A10A_{7}, A_{8}, A_{9}, A_{10}, with a cumulative score of 4+2+4=104+2+4=10;
A7A_{7} wins against A8,A9,A10A_{8}, A_{9}, A_{10}, with a cumulative score of 3+2×2+3=103+2 \times 2+3=10;
A8A_{8} wins against A9,A10A_{9}, A_{10}, with a cumulative score of 2+2×3+2=102+2 \times 3+2=10;
A9A_{9} wins against A10A_{10}, with a cumulative score of 1+2×4+1=101+2 \times 4+1=10;
A10A_{10} has a cumulative score of 0+2×5=100+2 \times 5=10.

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.