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 $D^{}_{}$ be the difference between the mode and the arithmetic mean of the sample. What is the largest possible value of $\lfloor D^{}_{}\rfloor$ ? (For real $x^{}_{}$ , $\lfloor x^{}_{}\rfloor$ is the greatest integer less than or equal to $x^{}_{}$ .)

Solution

Let the mode be $x$ , which we let appear $n > 1$ times. We let the arithmetic mean be $M$ , and the sum of the numbers $\neq x$ be $S$ . Then

$\begin{align*}

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)

Since $n < 1000$ , we wish to maximize $D$ , and as $S$ is essentially independent of $x$ , it follows that we either wish to minimize or maximize $x$ (in other words, $x=1,1000$ ). Indeed, $D(x)$ is symmetric about $x = 500.5$ ; consider replacing all of numbers $x_i$ in the sample with $1001-x_i$ , and the value of $D$ remains the same. So, without loss of generality, we let $x=1$ . Now, we would like to maximize the quantity

$\frac{S}{121}-\left(\frac{121-n}{121}\right)(1) = \frac{S+n}{121}-1$

$S$ contains $121-n$ numbers that may appear at most $n-1$ times. Therefore, to maximize $S$ , we would have $1000$ appear $n-1$ times, $999$ appear $n-1$ times, and so forth. We can thereby represent $S$ as the sum of $n-1$ arithmetic series of $1000, 999, \ldots, 1001 - \left\lfloor \frac{121-n}{n-1} \right\rfloor$ . We let $k = \left\lfloor \frac{121-n}{n-1} \right\rfloor$ , so

$S = (n-1)\left[\frac{k(1000 + 1001 - k)}{2}\right] + R(n)$

where $R(n)$ denotes the sum of the remaining $121-(n-1)k$ numbers, namely $R(n) = (121-(n-1)k)(1000-k)$ .

At this point, we introduce the crude estimate^[1] that $k=\frac{121-n}{n-1}$ , so $R(n) = 0$ and

$\begin{align*}2S+2n &= (121-n)\left(2001-\frac{121-n}{n-1}\right)+2n \\ &= (120-(n-1))\left(2002-\frac{120}{n-1}\right) = C - (2002)(n-1) - \frac{120^2}{n-1}+2n$ (Error compiling LaTeX. Unknown error_msg)

where $C$ is some constant which does not affect which $n$ yields a maximum. Expanding and scaling again, we wish to maximize the expression

$-2002(n-1) + 2n - \frac{120^2}{n-1} + C = -2000(n-1)- \frac{120^2}{n-1} + C,$

or after scaling, we wish to minimize the expression $5(n-1) + \frac{36}{n-1}$ . By AM-GM, we have $5(n-1) + \frac{36}{n-1} \le 2\sqrt{5(n-1) \cdot \frac{36}{n-1}}$ , with equality coming when $5(n-1) = \frac{36}{n-1}$ , so $n-1 \approx 3$ . Substituting this result in gives an answer of $\boxed{947}$ .

In less formal language, it quickly becomes clear after some trial and error that in our sample, there will be $n$ values equal to one and $n-1$ values each of $1000, 999, 998 \ldots$ . It is fairly easy to find the maximum. Try $n=2$ , which yields $924$ , $n=3$ , which yields $942$ , $n=4$ , which yields $947$ , and $n=5$ , which yields $944$ . The maximum difference occurred at $n=4$ , so the answer is $947$ .

Notes

Template:Cite In fact, when $n = 2,3,4,5$ (which some simple testing shows that the maximum will occur around), it turns out that $\frac{121-n}{n-1}$ is an integer anyway, so indeed $k = \left\lfloor \frac{121-n}{n-1} \right\rfloor = \frac{121-n}{n-1}$ .

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

Page

Toolbox

Search

1989 AIME Problems/Problem 11

Contents

Problem

Solution

Notes

See also