Mock AIME 1 2010 Problems/Problem 4
Problem
A round robin tournament is a tournament in which every player plays every other player exactly once. There is a round robin tournament with 2010 people. In each match, the winner scores one point, and the loser scores no points. There are no ties. Find the last three digits of the greatest possible difference between the first and second highest scores appearing among the players.
Solution
Clearly, to maximize the difference between the first and second place scores, we desire that the top player has as many points as possible. This maximum is , one for each match played. Now, because nobody scored any points on the top player, we are left with a -player round robin. Here, there are matches, so points are avaliable. If we divide the points evenly amongst the remaining players, we see that each player receives points. Thus, the difference between first and second place is , so our answer is .
To prove that it is possible to distribute points evenly amongst the lower players, consider the following scheme. Let these players be numbered through . Begin with player 's matches and continue in numerical order with the remaining matches for each player until all matches have been played. Let player win against players through and lose against players through to earn exactly points. Player starts with a loss against player and therefore must win against players through and lose the rest. In general, for , player starts off with losses and therefore must win against players through . Player starts off with a win against player and losses and so must win the next matches (which go up to playing player ). In general, for , player starts with wins and losses and so must win all remaining matches to end with points. Thus, it is possible to distribute the points evenly amongst the lower players, so our answer is valid.
See Also
Mock AIME 1 2010 (Problems, Source) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 |