1989 AIME Problems/Problem 11
Problem
A sample of 121 integers is given, each between 1 and 1000 inclusive, with repetitions allowed. The sample has a unique mode (most frequent value). Let be the difference between the mode and the arithmetic mean of the sample. What is the largest possible value of
? (For real
,
is the greatest integer less than or equal to
.)
Solution
Let the mode be , which we let appear
times. We let the arithmetic mean be
, and the sum of the numbers
be
. Then
D &= \left|M-x\right| = \left|\frac{S+xn}{121}-x\right| = \left|\frac{S}{121}-\left(\frac{121-n}{121}\right)x\right|
\end{align*}$ (Error compiling LaTeX. Unknown error_msg)As is essentially independent of
, it follows that we wish to minimize or maximize
(in other words,
). Indeed,
is symmetric about
; consider replacing all of numbers
in the sample with
, and the value of
remains the same. So, without loss of generality, let
. Now, we would like to maximize the quantity
![$\frac{S}{121}-\left(\frac{121-n}{121}\right)(1) = \frac{S+n}{121}-1$](http://latex.artofproblemsolving.com/7/d/5/7d54d12e05bbc735831671d2cd0c6d324265d917.png)
contains
numbers that may appear at most
times. Therefore, to maximize
, we would have
appear
times,
appear
times, and so forth. We can thereby represent
as the sum of
arithmetic series of
. We let
, so
![$S = (n-1)\left[\frac{k(1000 + 1001 - k)}{2}\right] + R(n)$](http://latex.artofproblemsolving.com/0/4/5/0456615e50545ebc7c6c5157c7cb4ca9135dbca8.png)
where denotes the sum of the remaining
numbers, namely
.
At this point, we introduce the crude estimate[1] that , so
and
Expanding (ignoring the constants, as these do not affect which yields a maximum) and scaling, we wish to minimize the expression
. By AM-GM, we have
, with equality coming when
, so
. Substituting this result and some arithmetic gives an answer of
.
In less formal language, it quickly becomes clear after some trial and error that in our sample, there will be values equal to one and
values each of
. It is fairly easy to find the maximum. Try
, which yields
,
, which yields
,
, which yields
, and
, which yields
. The maximum difference occurred at
, so the answer is
.
Notes
- ^ In fact, when
(which some simple testing shows that the maximum will occur around), it turns out that
is an integer anyway, so indeed
.
See also
1989 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 10 |
Followed by Problem 12 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.