2010 AMC 12A Problems/Problem 22

Problem 22

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

Solution

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.

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 $\frac{1}{m}$ .

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

$\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$

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

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

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 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 $d$ , there will be $B/2$ boys such that she moves $d$ away from this boy. For each of the remaining boys, she moves at most $d$ 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 $B$ is even, we can place her 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, pick $x=\frac 1{84}$ . 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$ .

Page

Toolbox

Search