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"

m (→‎Solution: ->tex)
(→‎Solution 1)
 
(12 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== 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 <math>D^{}_{}</math> be the difference between the mode and the arithmetic mean of the sample. What is the largest possible value of <math>\lfloor D^{}_{}\rfloor</math>? (For real <math>x^{}_{}</math>, <math>\lfloor x^{}_{}\rfloor</math> is the greatest integer less than or equal to <math>x^{}_{}</math>.)
+
A sample of 121 [[integer]]s is given, each between 1 and 1000 inclusive, with repetitions allowed. The sample has a unique [[mode]] (most frequent value). Let <math>D</math> be the difference between the mode and the [[arithmetic mean]] of the sample. What is the largest possible value of <math>\lfloor D\rfloor</math>? (For real <math>x</math>, <math>\lfloor x\rfloor</math> is the [[floor function|greatest integer]] less than or equal to <math>x</math>.)
 +
__NOTOC__
 +
== Solution 1 ==
 +
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
 +
<cmath>\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*}</cmath>
 +
As <math>S</math> is essentially independent of <math>x</math>, it follows that we wish to minimize or maximize <math>x</math> (in other words, <math>x \in [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]], 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>.
  
−
== 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
−
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>.
+
<cmath>\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*}</cmath>
 +
Expanding (ignoring the constants, as these do not affect which <math>n</math> yields a maximum) and 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} \ge 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 and some arithmetic 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>.
 +
 
 +
== Solution 2 ==
 +
With the same reasoning as Solution 1, in order to get largest possible value of D, we can construct that our set of numbers as <math>\underbrace{1,1,1...1,}_\text{n times}\underbrace{2,2,2...2,}_\text{n times}\underbrace{3,3,3...3,}_\text{n times}........\underbrace{1000,1000,1000....}_\text{n+1  times}</math> And, we need to find the value of n that makes the sum as low as possible. And, we can create a formula to make it easier. It isn't hard to find the sum. The numbers which are not 1000, average to <math>\frac{120}{2n}</math> or <math>\frac{60}{n}</math>, and there are <math>120-n</math> of them. So, they sum to <math>\frac{60}{n}(120-n)</math>. And, the sum of the numbers that are 1000 is <math>1000(n+1)</math> so, our total sum gets us <math>1000(n+1)+120/2n(120-n)</math> We want to minimize it, since the mode will always be 1000. And, testing the values n = 1, n = 2, n = 3, n = 4, we get these results.
 +
 
 +
<math>n = 1: 2000+60*119 = 9140</math>
 +
 
 +
<math>n = 2: 3000+30*118 = 6540</math>
 +
 
 +
<math>n = 3: 4000+20*117 = 6340</math>
 +
 
 +
<math>n = 4: 5000+15*116 = 6740</math>
 +
 
 +
And, as n grows larger and larger from 4, the values will start increasing. Thus, the lowest possible sum is 6340. Dividing by 121, the lowest possible mean is 52.396...., and thus, the highest possible value of <math>D</math> is 947.604, and the floor of that is <math>\boxed{947}</math>
 +
 
 +
- AlexLikeMath
 +
 
 +
== Notes ==
 +
*{{note|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 ==
−
* [[1989 AIME Problems/Problem 12|Next Problem]]
+
{{AIME box|year=1989|num-b=10|num-a=12}}
−
* [[1989 AIME Problems/Problem 10|Previous Problem]]
+
 
−
* [[1989 AIME Problems]]
+
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 17:01, 28 December 2022

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 1

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, 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)\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, 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. 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$.

Solution 2

With the same reasoning as Solution 1, in order to get largest possible value of D, we can construct that our set of numbers as $\underbrace{1,1,1...1,}_\text{n times}\underbrace{2,2,2...2,}_\text{n times}\underbrace{3,3,3...3,}_\text{n times}........\underbrace{1000,1000,1000....}_\text{n+1 times}$ And, we need to find the value of n that makes the sum as low as possible. And, we can create a formula to make it easier. It isn't hard to find the sum. The numbers which are not 1000, average to $\frac{120}{2n}$ or $\frac{60}{n}$, and there are $120-n$ of them. So, they sum to $\frac{60}{n}(120-n)$. And, the sum of the numbers that are 1000 is $1000(n+1)$ so, our total sum gets us $1000(n+1)+120/2n(120-n)$ We want to minimize it, since the mode will always be 1000. And, testing the values n = 1, n = 2, n = 3, n = 4, we get these results.

$n = 1: 2000+60*119 = 9140$

$n = 2: 3000+30*118 = 6540$

$n = 3: 4000+20*117 = 6340$

$n = 4: 5000+15*116 = 6740$

And, as n grows larger and larger from 4, the values will start increasing. Thus, the lowest possible sum is 6340. Dividing by 121, the lowest possible mean is 52.396...., and thus, the highest possible value of $D$ is 947.604, and the floor of that is $\boxed{947}$

- AlexLikeMath

Notes

  • ^ 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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1989_AIME_Problems/Problem_11&oldid=185105"