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 "2010 AMC 12A Problems/Problem 22"

m (hmm need more case-testing)
 
(21 intermediate revisions by 13 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
What is the minimum value of <math>\left|x-1\right| + \left|2x-1\right| + \left|3x-1\right| + \cdots + \left|119x - 1 \right|</math>?
+
What is the minimum value of <math>f(x)=\left|x-1\right| + \left|2x-1\right| + \left|3x-1\right| + \cdots + \left|119x - 1 \right|</math>?
  
 
<math>\textbf{(A)}\ 49 \qquad \textbf{(B)}\ 50 \qquad \textbf{(C)}\ 51 \qquad \textbf{(D)}\ 52 \qquad \textbf{(E)}\ 53</math>
 
<math>\textbf{(A)}\ 49 \qquad \textbf{(B)}\ 50 \qquad \textbf{(C)}\ 51 \qquad \textbf{(D)}\ 52 \qquad \textbf{(E)}\ 53</math>
  
−
== Solution ==
+
== Solution 1 ==
−
=== Solution 1 ===
+
If we graph each term separately, we will notice that all of the zeros occur at <math>\frac{1}{m}</math>, where <math>m</math> is any integer from <math>1</math> to <math>119</math>, inclusive: <math>|mx-1|=0\implies mx=1\implies x=\frac{1}{m}</math>.
−
If we graph each term separately, we will notice that all of the zeros occur at <math>\frac{1}{m}</math>, where <math>m</math> is any integer from <math>1</math> to <math>119</math>, inclusive.
 
  
−
The minimum value occurs where the sum of the slopes is at a minimum, since it is easy to see that the value will be increasing on either side. That means the minimum must happen at some <math>\frac{1}{m}</math>.
+
The minimum value of <math>f(x)</math> occurs where the absolute value of the sum of the slopes is at a minimum <math>\ge 0</math>, since it is easy to see that the value will be increasing on either side. That means the minimum must happen at some <math>\frac{1}{m}</math>.
  
−
 
+
The sum of the slopes at <math>x = \frac{1}{m}</math> is
−
The sum of the slope at <math>x = \frac{1}{m}</math> is
 
  
 
<cmath>\begin{align*}&\sum_{i=m+1}^{119}i - \sum_{i=1}^{m}i\\
 
<cmath>\begin{align*}&\sum_{i=m+1}^{119}i - \sum_{i=1}^{m}i\\
Line 21: Line 19:
 
We can now verify that both <math>x=\frac{1}{84}</math> and <math>x=\frac{1}{85}</math> yield <math>\boxed{49\ \textbf{(A)}}</math>.
 
We can now verify that both <math>x=\frac{1}{84}</math> and <math>x=\frac{1}{85}</math> yield <math>\boxed{49\ \textbf{(A)}}</math>.
  
−
=== Solution 2 ===
+
You can also think of the slopes playing 'tug of war', where the slope of each absolute function upon passing its <math>x</math>-intercept is negated, positively tugging on the remaining negative slopes.
 +
 
 +
The sum of the slopes is <math>1+2+3+4\dots 119=\sum_{m=1}^{119}m=\frac{119\cdot 120}{2}=60\cdot 119=7140</math>
 +
 
 +
So we need to find the least integer <math>a</math> such that <math>1+2+3+\dots a=\sum_{n=1}^an=\frac{a(a+1)}{2}\ge \frac{7140}{2}=3570:</math>
 +
 
 +
<cmath>a(a+1)\ge 7140\implies a^2+a-7140\ge 0\rightarrow a=84\text{ exactly!}</cmath>
 +
This "exactly" means that the slope is ZERO between the whole interval <math>x\in\left(\frac{1}{85},\frac{1}{84}\right)</math>. We can explicitly evaluate both to check that they are both equal to the desired minimum value of <math>f(x)</math>:
 +
 
 +
<cmath>\frac{84+83+\dots+2+1+1+2+\dots+33+34}{85}=\frac{84(85)/2+34(35)/2}{85}=\frac{85(14+84)/2}{85}=49</cmath>
 +
 
 +
<cmath>\frac{83+82+\dots+2+1+1+2+\dots+34+35}{84}=\frac{83(84)/2+35(36)/2}{84}=\frac{84(15+83)/2}{84}=49</cmath>
 +
 
 +
Thus the minimum value of <math>f(x)</math> is <math>49</math>.
 +
 
 +
== Solution 2 ==
 
Rewrite the given expression as follows:
 
Rewrite the given expression as follows:
 
<cmath> 1|x-1| + 2\left|x-\frac 12\right| + \cdots + 119\left|x-\frac 1{119}\right|</cmath>
 
<cmath> 1|x-1| + 2\left|x-\frac 12\right| + \cdots + 119\left|x-\frac 1{119}\right|</cmath>
−
Imagine the real line. For each <math>n\in\{1,\dots,119\}</math> imagine that there are <math>n</math> boys standing at the coordinate <math>\frac 1n</math>. We now need to place a girl on the real line in such a way that the sum of her distances from all the boys is minimal, and we need to compute this sum.
+
Imagine the real line. For each <math>n\in\{1,\dots,119\}</math> imagine that there are <math>n</math> boys standing at the coordinate <math>\frac 1n</math>. We now need to place a donut on the real line in such a way that the sum of its distances from all the boys is minimal, and we need to compute this sum.
  
 
Note that there are <math>B=1+2+\cdots+119 = 119\cdot 60=7140</math> boys in total. Let's label them from 1 (the only boy placed at <math>1</math>) to <math>B</math> (the last boy placed at <math>\frac 1{119}</math>.
 
Note that there are <math>B=1+2+\cdots+119 = 119\cdot 60=7140</math> boys in total. Let's label them from 1 (the only boy placed at <math>1</math>) to <math>B</math> (the last boy placed at <math>\frac 1{119}</math>.
  
−
Clearly, the minimum sum is achieved if the girl's coordinate is the median of the boys' coordinates. To prove this, place the girl at the median coordinate. If you now move her in any direction by any amount <math>d</math>, there will be <math>B/2</math> boys such that she moves <math>d</math> away from this boy. For each of the remaining boys, she moves at most <math>d</math> closer, hence the total sum of distances does not decrease.
+
Clearly, the minimum sum is achieved if the donut's coordinate is the median of the boys' coordinates. To prove this, place the donut at the median coordinate. If you now move it in any direction by any amount <math>d</math>, there will be <math>B/2</math> boys such that it moves <math>d</math> away from this boy. For each of the remaining boys, it moves at most <math>d</math> closer, hence the total sum of distances does not decrease.
  
−
Hence the optimal solution is to place the girl at the median coordinate. Or, more precisely, as <math>B</math> is even, we can place her anywhere on the segment formed by boy <math>B/2</math> and boy <math>(B/2)+1</math>: by extending the previous argument, anywhere on this segment the sum of distances is the same.
+
Hence the optimal solution is to place the donut at the median coordinate. Or, more precisely, as <math>B</math> is even, we can place it anywhere on the segment formed by boy <math>B/2</math> and boy <math>(B/2)+1</math>: by extending the previous argument, anywhere on this segment the sum of distances is the same.
  
 
By trial and error, or by solving the quadratic equation <math>z(z+1)/2 = 7140/2</math> we get that boy number <math>B/2</math> is the last boy placed at <math>\frac 1{84}</math> and the next boy is the one placed at <math>\frac 1{85}</math>. Hence the given expression is minimized for any <math>x\in\left[ \frac 1{85}, \frac 1{84} \right]</math>.
 
By trial and error, or by solving the quadratic equation <math>z(z+1)/2 = 7140/2</math> we get that boy number <math>B/2</math> is the last boy placed at <math>\frac 1{84}</math> and the next boy is the one placed at <math>\frac 1{85}</math>. Hence the given expression is minimized for any <math>x\in\left[ \frac 1{85}, \frac 1{84} \right]</math>.
Line 36: Line 49:
 
=== Common part of both solutions ===
 
=== Common part of both solutions ===
  
−
To find the minimum, pick <math>x=\frac 1{84}</math>. Note that the terms <math>x-1</math> to <math>83x-1</math> are negative, and the terms <math>85x-1</math> to <math>119x-1</math> are positive. Hence we get:
+
To find the minimum, we want to balance the expression so that it is neither top nor bottom heavy. <math>\frac{119(120)}{2(2)}=\frac{7140}{2}=3570=\frac{84(85)}{2}=\frac{119(120)}{2}-\frac{84(85)}{2}</math>.
 +
 
 +
Now that we know that the sum of the first 84 <math>x</math>'s is equivalent to the sum of <math>x</math>'s 85 to 119, we can plug either <math>\frac{1}{84}</math> or <math>\frac{1}{85}</math> to find the minimum.
 +
 
 +
Note that the terms <math>x-1</math> to <math>83x-1</math> are negative, and the terms <math>85x-1</math> to <math>119x-1</math> are positive. Hence we get:
 
<cmath>
 
<cmath>
 
\begin{align*}
 
\begin{align*}
Line 69: Line 86:
 
</cmath>
 
</cmath>
 
Hence the total sum of distances is <math>\frac{83}2 + \frac{15}2 = 49</math>.
 
Hence the total sum of distances is <math>\frac{83}2 + \frac{15}2 = 49</math>.
 +
 +
== Solution 3 ==
 +
By the triangle inequality,<math>|x-1|+|2x-1|+|3x-1|+\cdots + |119x-1| \geq |(x-1)+(2x-1)+\cdots+(119x)-1|.</math>
 +
However, we may change signs of some of these terms to cancel out the <math>x</math>'s.
 +
Since the minimum exists, we want all the <math>x</math>s to cancel out. Thus, we want to find some <math>n</math> such that <cmath>1+2+3+...+n=(n+1)+(n+2)+(n+3)+...+119</cmath> <cmath>\frac{n(n+1)}{2}=\frac{119\cdot120}{2}-\frac{n(n+1)}{2}</cmath> <cmath>n^2+n-7140=0</cmath> <cmath>n=84</cmath>
 +
 +
Then, <math>x=\frac{1}{n}= \frac{1}{84}</math>. The answer(expression's value) is then <math>84*1+(119-85+1)*(-1)</math> , which becomes <math>84-35=\boxed{49}</math>.
 +
 +
==Video Solution by mop 2024==
 +
https://youtu.be/lu4jlTNUYrQ
 +
 +
~r00tsOfUnity
  
 
== See also ==
 
== See also ==
Line 74: Line 103:
  
 
[[Category:Intermediate Geometry Problems]]
 
[[Category:Intermediate Geometry Problems]]
 +
{{MAA Notice}}

Latest revision as of 22:22, 24 July 2023

Problem

What is the minimum value of $f(x)=\left|x-1\right| + \left|2x-1\right| + \left|3x-1\right| + \cdots + \left|119x - 1 \right|$?

$\textbf{(A)}\ 49 \qquad \textbf{(B)}\ 50 \qquad \textbf{(C)}\ 51 \qquad \textbf{(D)}\ 52 \qquad \textbf{(E)}\ 53$

Solution 1

If we graph each term separately, we will notice that all of the zeros occur at $\frac{1}{m}$, where $m$ is any integer from $1$ to $119$, inclusive: $|mx-1|=0\implies mx=1\implies x=\frac{1}{m}$.

The minimum value of $f(x)$ occurs where the absolute value of the sum of the slopes is at a minimum $\ge 0$, since it is easy to see that the value will be increasing on either side. That means the minimum must happen at some $\frac{1}{m}$.

The sum of the slopes at $x = \frac{1}{m}$ is

\begin{align*}&\sum_{i=m+1}^{119}i - \sum_{i=1}^{m}i\\ &=\sum_{i=1}^{119}i - 2\sum_{i=1}^{m}i\\ &=-m^2-m+7140\end{align*}

Now we want to minimize $-m^2-m+7140$. The zeros occur at $-85$ and $84$, which means the slope is $0$ where $m = 84, 85$.

We can now verify that both $x=\frac{1}{84}$ and $x=\frac{1}{85}$ yield $\boxed{49\ \textbf{(A)}}$.

You can also think of the slopes playing 'tug of war', where the slope of each absolute function upon passing its $x$-intercept is negated, positively tugging on the remaining negative slopes.

The sum of the slopes is $1+2+3+4\dots 119=\sum_{m=1}^{119}m=\frac{119\cdot 120}{2}=60\cdot 119=7140$

So we need to find the least integer $a$ such that $1+2+3+\dots a=\sum_{n=1}^an=\frac{a(a+1)}{2}\ge \frac{7140}{2}=3570:$

\[a(a+1)\ge 7140\implies a^2+a-7140\ge 0\rightarrow a=84\text{ exactly!}\] This "exactly" means that the slope is ZERO between the whole interval $x\in\left(\frac{1}{85},\frac{1}{84}\right)$. We can explicitly evaluate both to check that they are both equal to the desired minimum value of $f(x)$:

\[\frac{84+83+\dots+2+1+1+2+\dots+33+34}{85}=\frac{84(85)/2+34(35)/2}{85}=\frac{85(14+84)/2}{85}=49\]

\[\frac{83+82+\dots+2+1+1+2+\dots+34+35}{84}=\frac{83(84)/2+35(36)/2}{84}=\frac{84(15+83)/2}{84}=49\]

Thus the minimum value of $f(x)$ is $49$.

Solution 2

Rewrite the given expression as follows: \[1|x-1| + 2\left|x-\frac 12\right| + \cdots + 119\left|x-\frac 1{119}\right|\] Imagine the real line. For each $n\in\{1,\dots,119\}$ imagine that there are $n$ boys standing at the coordinate $\frac 1n$. We now need to place a donut on the real line in such a way that the sum of its distances from all the boys is minimal, and we need to compute this sum.

Note that there are $B=1+2+\cdots+119 = 119\cdot 60=7140$ boys in total. Let's label them from 1 (the only boy placed at $1$) to $B$ (the last boy placed at $\frac 1{119}$.

Clearly, the minimum sum is achieved if the donut's coordinate is the median of the boys' coordinates. To prove this, place the donut at the median coordinate. If you now move it in any direction by any amount $d$, there will be $B/2$ boys such that it moves $d$ away from this boy. For each of the remaining boys, it moves at most $d$ closer, hence the total sum of distances does not decrease.

Hence the optimal solution is to place the donut at the median coordinate. Or, more precisely, as $B$ is even, we can place it anywhere on the segment formed by boy $B/2$ and boy $(B/2)+1$: by extending the previous argument, anywhere on this segment the sum of distances is the same.

By trial and error, or by solving the quadratic equation $z(z+1)/2 = 7140/2$ we get that boy number $B/2$ is the last boy placed at $\frac 1{84}$ and the next boy is the one placed at $\frac 1{85}$. Hence the given expression is minimized for any $x\in\left[ \frac 1{85}, \frac 1{84} \right]$.

Common part of both solutions

To find the minimum, we want to balance the expression so that it is neither top nor bottom heavy. $\frac{119(120)}{2(2)}=\frac{7140}{2}=3570=\frac{84(85)}{2}=\frac{119(120)}{2}-\frac{84(85)}{2}$.

Now that we know that the sum of the first 84 $x$'s is equivalent to the sum of $x$'s 85 to 119, we can plug either $\frac{1}{84}$ or $\frac{1}{85}$ to find the minimum.

Note that the terms $x-1$ to $83x-1$ are negative, and the terms $85x-1$ to $119x-1$ are positive. Hence we get: \begin{align*} & |x-1| + |2x-1| + \cdots + |83x-1| \\ =~ & (1-x) + (1-2x) + \cdots + (1-83x) \\ =~ & 83 - x(1+2+\cdots+83) \\ =~ & 83 - \frac 1{84} \cdot \frac{83\cdot 84}2 \\ =~ & 83 - \frac{83}2 \\ =~ & \frac{83}2 \end{align*} and \begin{align*} & |85x-1| + |86x-1| + \cdots + |119x-1| \\ =~ & (85x-1) + (86x-1) + \cdots + (119x-1) \\ =~ & x(85+86+\cdots+119) - (119-84) \\ =~ & \frac 1{84} \cdot \frac{84\cdot 85}2 - 35 \\ =~ & \frac{85}2 - 35 \\ =~ & \frac{15}2 \end{align*} Hence the total sum of distances is $\frac{83}2 + \frac{15}2 = 49$.

Solution 3

By the triangle inequality,$|x-1|+|2x-1|+|3x-1|+\cdots + |119x-1| \geq |(x-1)+(2x-1)+\cdots+(119x)-1|.$ However, we may change signs of some of these terms to cancel out the $x$'s. Since the minimum exists, we want all the $x$s to cancel out. Thus, we want to find some $n$ such that \[1+2+3+...+n=(n+1)+(n+2)+(n+3)+...+119\] \[\frac{n(n+1)}{2}=\frac{119\cdot120}{2}-\frac{n(n+1)}{2}\] \[n^2+n-7140=0\] \[n=84\]

Then, $x=\frac{1}{n}= \frac{1}{84}$. The answer(expression's value) is then $84*1+(119-85+1)*(-1)$ , which becomes $84-35=\boxed{49}$.

Video Solution by mop 2024

https://youtu.be/lu4jlTNUYrQ

~r00tsOfUnity

See also

2010 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 21 		Followed by
Problem 23
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 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=2010_AMC_12A_Problems/Problem_22&oldid=196060"