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

Difference between revisions of "1989 AIME Problems/Problem 11"

(will complete later)
(some rigor)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
−
It is obvious that there will be <math>n+1</math> values equal to one and <math>n</math> values each of <math>1000, 999, 998 \ldots</math>. It is fairly easy to find the [[maximum]]. Try <math>n=1</math>, which yields <math>924</math>, <math>n=2</math>, which yields <math>942</math>, <math>n=3</math>, which yields <math>947</math>, and <math>n=4</math>, which yields <math>944</math>. The maximum difference occurred at <math>n=3</math>, so the answer is <math>947</math>.
+
Let the mode be <math>x</math>, which we let appear <math>n > 1</math> times. We let the arithmetic mean be <math>M</math>, and the sum of the numbers <math>\neq x</math> be <math>S</math>. Then
 +
<center><math>\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*}</math></center>
 +
Since <math>n < 1000</math>, we wish to maximize <math>D</math>, and as <math>S</math> is essentially independent of <math>x</math>, it follows that we either wish to minimize or maximize <math>x</math> (in other words, <math>x=1,1000</math>). Indeed, <math>D(x)</math> is symmetric about <math>x = 500.5</math>; consider replacing all of numbers <math>x_i</math> in the sample with <math>1001-x_i</math>, and the value of <math>D</math> remains the same. So, [[without loss of generality]], we let <math>x=1</math>. Now, we would like to maximize the quantity
 +
<center><math>\frac{S}{121}-\left(\frac{121-n}{121}\right)(1) = \frac{S+n}{121}-1</math></center>
 +
<math>S</math> contains <math>121-n</math> numbers that may appear at most <math>n-1</math> times. Therefore, to maximize <math>S</math>, we would have <math>1000</math> appear <math>n-1</math> times, <math>999</math> appear <math>n-1</math> times, and so forth. We can thereby represent <math>S</math> as the sum of <math>n-1</math> arithmetic series of <math>1000, 999, \ldots, 1001 - \left\lfloor \frac{121-n}{n-1} \right\rfloor</math>. We let <math>k = \left\lfloor \frac{121-n}{n-1} \right\rfloor</math>, so
 +
<center><math>S = (n-1)\left[\frac{k(1000 + 1001 - k)}{2}\right] + R(n)</math></center>
 +
where <math>R(n)</math> denotes the sum of the remaining <math>121-(n-1)k</math> numbers, namely <math>R(n) = (121-(n-1)k)(1000-k)</math>.  
  
−
{{incomplete|solution}}
+
At this point, we introduce the crude estimate{{ref|1}} that <math>k=\frac{121-n}{n-1}</math>, so <math>R(n) = 0</math> and
 +
<center><math>\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</math></center>
 +
where <math>C</math> is some constant which does not affect which <math>n</math> yields a maximum. Expanding and scaling again, we wish to maximize the expression
 +
<center><math>-2002(n-1) + 2n - \frac{120^2}{n-1} + C = -2000(n-1)- \frac{120^2}{n-1} + C,</math></center>
 +
or after scaling, we wish to minimize the expression <math>5(n-1) + \frac{36}{n-1}</math>. By [[AM-GM]], we have <math>5(n-1) + \frac{36}{n-1} \le 2\sqrt{5(n-1) \cdot \frac{36}{n-1}}</math>, with equality coming when <math>5(n-1) = \frac{36}{n-1}</math>, so <math>n-1 \approx 3</math>. Substituting this result in gives an answer of <math>\boxed{947}</math>.
 +
 
 +
----
 +
 
 +
In less formal language, it quickly becomes clear after some trial and error that in our sample, there will be <math>n</math> values equal to one and <math>n-1</math> values each of <math>1000, 999, 998 \ldots</math>. It is fairly easy to find the [[maximum]]. Try <math>n=2</math>, which yields <math>924</math>, <math>n=3</math>, which yields <math>942</math>,  <math>n=4</math>, which yields <math>947</math>, and <math>n=5</math>, which yields <math>944</math>. The maximum difference occurred at <math>n=4</math>, so the answer is <math>947</math>.
 +
 
 +
== Notes ==
 +
*{{cite|1}} In fact, when <math>n = 2,3,4,5</math> (which some simple testing shows that the maximum will occur around), it turns out that <math>\frac{121-n}{n-1}</math> is an integer anyway, so indeed <math>k = \left\lfloor \frac{121-n}{n-1} \right\rfloor = \frac{121-n}{n-1}</math>.
  
 
== See also ==
 
== See also ==

Revision as of 17:35, 11 April 2008

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}$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1989_AIME_Problems/Problem_11&oldid=24662"