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 $2008$ , one for each match played. Now, because nobody scored any points on the top player, we are left with a $2009$ -player round robin. Here, there are $\tbinom{2009}2$ matches, so $\tbinom{2009}2$ points are avaliable. If we divide the points evenly amongst the remaining $2009$ players, we see that each player receives $\tfrac{\tbinom{2009}2}{2009}=\tfrac{2008}{2!}=1004$ points. Thus, the difference between first and second place is $2009-1004=1005$ , so our answer is $\boxed{005}$ .

To prove that it is possible to distribute points evenly amongst the lower $2009$ players, consider the following scheme. Let these players be numbered $1$ through $2009$ . Begin with player $1$ 's $2008$ matches and continue in numerical order with the remaining matches for each player until all matches have been played. Let player $1$ win against players $2$ through $1005$ and lose against players $1006$ through $2009$ to earn exactly $1004$ points. Player $2$ starts with a loss against player $1$ and therefore must win against players $3$ through $1006$ and lose the rest. In general, for $n\leq1005$ , player $n$ starts off with $n-1$ losses and therefore must win against players $n+1$ through $n+1004$ . Player $1006$ starts off with a win against player $2$ and $1004$ losses and so must win the next $1003$ matches (which go up to playing player $2009$ ). In general, for $n\geq1006$ , player $n$ starts with $n-1005$ wins and $(2009-n)+(n-1005)=1004$ losses and so must win all remaining matches to end with $1004$ points. Thus, it is possible to distribute the $\tbinom{2009}2$ points evenly amongst the lower $2009$ players, so our answer $005$ is valid.

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

Page

Toolbox

Search

Mock AIME 1 2010 Problems/Problem 4

Problem

Solution

See Also