Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Mock AIME 1 2010 Problems/Problem 4

Revision as of 09:16, 2 August 2024 by Thepowerful456 (talk | contribs) (→‎Solution)

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.

See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_1_2010_Problems/Problem_4&oldid=224204"