A sample of 121 [integers](https://artofproblemsolving.com/wiki/index.php/Integer) is given, each between 1 and 1000 inclusive, with repetitions allowed. The sample has a unique [mode](https://artofproblemsolving.com/wiki/index.php/Mode) (most frequent value). Let $D$ be the difference between the mode and the [arithmetic mean](https://artofproblemsolving.com/wiki/index.php/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](https://artofproblemsolving.com/wiki/index.php/Floor_function) less than or equal to $x$.)
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*}
As $S$ is essentially independent of $x$, it follows that we wish to minimize or maximize $x$ (in other words, $x \in [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](https://artofproblemsolving.com/wiki/index.php/Without_loss_of_generality), 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](https://artofproblemsolving.com#note_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)\end{align*}
Expanding (ignoring the constants, as these do not affect which $n$ yields a maximum) and scaling, we wish to minimize the expression $5(n-1) + \frac{36}{n-1}$. By [AM-GM](https://artofproblemsolving.com/wiki/index.php/AM-GM), we have $5(n-1) + \frac{36}{n-1} \ge 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 and some arithmetic 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](https://artofproblemsolving.com/wiki/index.php/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$.