Difference between revisions of "Mock AIME 1 2010 Problems/Problem 4"
m (better see also) |
m (typo fix) |
||
Line 8: | Line 8: | ||
== See Also == | == See Also == | ||
− | {{Mock AIME box|year=2010|n=1|num-b= | + | {{Mock AIME box|year=2010|n=1|num-b=3|num-a=5}} |
Latest revision as of 09:44, 2 August 2024
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 |