15 There are 10 players , their points are , 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).
Solution
15 If the new champion's score does not exceed 11 points, then can win at most 2 games; can win at most 3 games; can win at most 4 games; can win at most 5 games; 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; 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; 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; 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; 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; 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 , but each match between two players results in one win, totaling (games), which is a contradiction.
The following example shows that the new champion's cumulative score can be 12 points.
wins against , loses to , with a cumulative score of ;
wins against , loses to , with a cumulative score of ;
wins against , loses to , with a cumulative score of ;
wins against , loses to , with a cumulative score of ;
wins against , loses to , with a cumulative score of ;
wins against , with a cumulative score of ;
wins against , with a cumulative score of ;
wins against , with a cumulative score of ;
wins against , with a cumulative score of ;
has a cumulative score of .