Difference between revisions of "Mock AIME 1 2010 Problems/Problem 4"
(created solution page) |
m (typo fix) |
||
(2 intermediate revisions by the same user not shown) | |||
Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
− | <math>\boxed{005}</math>. | + | 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 <math>2008</math>, one for each match played. Now, because nobody scored any points on the top player, we are left with a <math>2009</math>-player round robin. Here, there are <math>\tbinom{2009}2</math> matches, so <math>\tbinom{2009}2</math> points are avaliable. If we divide the points evenly amongst the remaining <math>2009</math> players, we see that each player receives <math>\tfrac{\tbinom{2009}2}{2009}=\tfrac{2008}{2!}=1004</math> points. Thus, the difference between first and second place is <math>2009-1004=1005</math>, so our answer is <math>\boxed{005}</math>. |
+ | |||
+ | To prove that it is possible to distribute points evenly amongst the lower <math>2009</math> players, consider the following scheme. Let these players be numbered <math>1</math> through <math>2009</math>. Begin with player <math>1</math>'s <math>2008</math> matches and continue in numerical order with the remaining matches for each player until all matches have been played. Let player <math>1</math> win against players <math>2</math> through <math>1005</math> and lose against players <math>1006</math> through <math>2009</math> to earn exactly <math>1004</math> points. Player <math>2</math> starts with a loss against player <math>1</math> and therefore must win against players <math>3</math> through <math>1006</math> and lose the rest. In general, for <math>n\leq1005</math>, player <math>n</math> starts off with <math>n-1</math> losses and therefore must win against players <math>n+1</math> through <math>n+1004</math>. Player <math>1006</math> starts off with a win against player <math>2</math> and <math>1004</math> losses and so must win the next <math>1003</math> matches (which go up to playing player <math>2009</math>). In general, for <math>n\geq1006</math>, player <math>n</math> starts with <math>n-1005</math> wins and <math>(2009-n)+(n-1005)=1004</math> losses and so must win all remaining matches to end with <math>1004</math> points. Thus, it is possible to distribute the <math>\tbinom{2009}2</math> points evenly amongst the lower <math>2009</math> players, so our answer <math>005</math> is valid. | ||
== See Also == | == See Also == | ||
− | + | {{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 |