Difference between revisions of "2006 AIME I Problems/Problem 15"

Revision as of 19:27, 10 October 2007

Problem

Given that a sequence satisfies $x_0=0$ and $|x_k|=|x_{k-1}+3|$ for all integers $k\ge 1,$ find the minimum possible value of $|x_1+x_2+\cdots+x_{2006}|.$

Solution

Solutio 1

Suppose $b_{i} = \frac {a_{i}}3$ We have \[ \sum_{i = 1}^{2006}b_{i}^{2} = \sum_{i = 0}^{2005}(b_{i} + 1)^{2} = \sum_{i = 0}^{2005}(b_{i}^{2} + 2b_{i} + 1) \] So \[ \sum_{i = 0}^{2005}b_{i} = \frac {b_{2006}^{2} - 2006}2 \] Now \[ \sum_{i = 1}^{2006}b_{i} = \frac {b_{2006}^{2} + 2b_{2006} - 2006}2 \] Therefore \[ |\sum_{i = 1}^{2006}b_{i}| = |\frac {(b_{2006} + 1)^{2} - 2007}2|\geq \frac {2025 - 2007}{2} = 9 \] So \[ |\sum_{i = 1}^{2006}a_{i}|\geq 27 \]

Solution 2

First, we state that iff $x_{i - 1}\ge0$ , $|x_i| = |x_{i - 1}| + 3$ and iff $x_{i - 1} < 0$ , $|x_i| = |x_{i - 1}| - 3$ . Now suppose $x_i = x_j$ for some $0\le i < j\le2006$ . Now, this means that $|x_i| = |x_j|$ , and so the number of positive numbers in the set $\{x_i,x_{i + 1},\ldots,x_{j - 1}\}$ equals the number of negative numbers. Now pair the numbers in this list up in the following way: Whenever a positive and a negative number are adjacent in this progression, pair them up and remove them from this list. We claim that every pair will sum to -3.

If the positive number comes first, then the negative number will have a magnitude three greater, so this is true. If the negative number comes first, then the positive number will have magnitude three smaller, and this will also be true. Now let us examine what happens when we remove those two from the sequence. WLOG, let the numbers be $x_k$ and $x_{k + 1}$ . Since one is positive and the other is negative, $|x_{k + 2}| = |x_{k + 1}|\pm3 = |x_k|\pm3\mp3 = |x_k| = |x_{k - 1} + 3|$ . So the new sequence works under the same criteria as the old one. In this way, we can pair all of the numbers up in this subsequence so the sums of the pairs are -3. Thus, the average of these numbers will be -3/2 for all subsequences that start and end with the same number (not including one of those).

Now, take all of the repeating subsequences out of the original sequence. The only thing that will be left will be a sequence $\{0,3,6,9,\cdots,3k\}$ for some even $k$ . Since we started with 2006 terms, we removed $2006 - k$ (an even number) with an average of -3/2. Thus, the sum of both this remaining sequence and the removed stuff is $(2006 - k)( - 3/2) + \sum_{i = 1}^k3k = (3/2)(k - 2006 + k(k + 1)) = 3/2(k^2 + 2k - 2006)$ . This must be minimized, so we find the roots: $k^2 + 2k = 2006\implies (k + 1)^2 = 2007$ and $44^2 = 1936 < 2007 < 2025 = 45^2$ . Plugging in $k = 44$ yields $(3/2)(2025 - 2007) = 27$ (and $k = 42$ yields $- 237$ , a worse result). Thus, $\fbox{027}$ is the closest to zero this sum can get.

Solution 3

We know $|x_k| = |x_{k - 1} + 3|$ . We get rid of the absolute value by squaring both sides: ${x_k}^2 = {x_{k - 1}}^2 + 6{x_{k - 1}} + 9\Rightarrow {x_k}^2 - {x_{k - 1}}^2 = 6{x_{k - 1}} + 9$ . So we set this up:

$\begin{eqnarray*} {x_1}^2 - {x_0}^2 & = & 6{x_0} + 9 \\ {x_2}^2 - {x_1}^2 & = & 6{x_1} + 9 \\ & \vdots & \\ {x_{2007}}^2 - {x_{2006}}^2 & = & 6{x_{2006}} + 9 \end{eqnarray*}$ (Error compiling LaTeX. Unknown error_msg)

There are $2007$ equations. Sum them. We get: ${x_{2007}}^2 = 6\left(x_1 + x_2 + \cdots + x_{2006}\right) + 9\cdot{2007}$

So $|x_1 + x_2 + \cdots + x_{2006}| = \frac {\left|{x_{2007}}^2 - 9\cdot{2007}\right|}{6}$

We know $3\ |\ x_{2007}$ and we want to minimize $\left|{x_{2007}}^2 - 9\cdot{2007}\right|$ , so $x_{2007}$ must be $3\cdot{45}$ for it to be minimal ( $45^2 = 2025$ which is closest to $2007$ ).

This means that $|x_1 + x_2 + \cdots + x_{2006}| = \left|\frac {9(2025 - 2007)}{6}\right| = \boxed{27}$

@@ Line 2: / Line 2: @@
 Given that a sequence satisfies <math> x_0=0 </math> and <math> |x_k|=|x_{k-1}+3| </math> for all integers <math> k\ge 1, </math> find the minimum possible value of <math> |x_1+x_2+\cdots+x_{2006}|. </math>
+__TOC__
 == Solution ==
+=== Solutio 1 ===
+Suppose <math>b_{i} = \frac {a_{i}}3</math>
+We have
+\[
+\sum_{i = 1}^{2006}b_{i}^{2} = \sum_{i = 0}^{2005}(b_{i} + 1)^{2} = \sum_{i = 0}^{2005}(b_{i}^{2} + 2b_{i} + 1)
+\]
+So
+\[
+\sum_{i = 0}^{2005}b_{i} = \frac {b_{2006}^{2} - 2006}2
+\]
+Now
+\[
+\sum_{i = 1}^{2006}b_{i} = \frac {b_{2006}^{2} + 2b_{2006} - 2006}2
+\]
+Therefore
+\[
+|\sum_{i = 1}^{2006}b_{i}| = |\frac {(b_{2006} + 1)^{2} - 2007}2|\geq \frac {2025 - 2007}{2} = 9
+\]
+So
+\[
+|\sum_{i = 1}^{2006}a_{i}|\geq 27
+\]
-Since we may phrase the sequence as <math> x_{4n}=0 </math>, <math> x_{4n+1}= \pm 3 </math>, <math> x_{4n+2}=0 </math>, and <math> x_{4n+3}= \mp 3 </math>, the sun of these 4 terms is 0. Since <math> {2006} \equiv {2} modulo {4} </math>, <math> |0 \pm 3|  = 3</math>.
+=== Solution 2 ===
+First, we state that iff <math>x_{i - 1}\ge0</math>, <math>|x_i| = |x_{i - 1}| + 3</math> and iff <math>x_{i - 1} < 0</math>, <math>|x_i| = |x_{i - 1}| - 3</math>. Now suppose <math>x_i = x_j</math> for some <math>0\le i < j\le2006</math>. Now, this means that <math>|x_i| = |x_j|</math>, and so the number of positive numbers in the set <math>\{x_i,x_{i + 1},\ldots,x_{j - 1}\}</math> equals the number of negative numbers. Now pair the numbers in this list up in the following way: Whenever a positive and a negative number are adjacent in this progression, pair them up and remove them from this list. We claim that every pair will sum to -3.
-Therefore, the minimum possible value of <math> |x_1+x_2+\cdots+x_{2006}| = 3 .</math>
+If the positive number comes first, then the negative number will have a magnitude three greater, so this is true. If the negative number comes first, then the positive number will have magnitude three smaller, and this will also be true. Now let us examine what happens when we remove those two from the sequence. WLOG, let the numbers be <math>x_k</math> and <math>x_{k + 1}</math>. Since one is positive and the other is negative, <math>|x_{k + 2}| = |x_{k + 1}|\pm3 = |x_k|\pm3\mp3 = |x_k| = |x_{k - 1} + 3|</math>. So the new sequence works under the same criteria as the old one. In this way, we can pair all of the numbers up in this subsequence so the sums of the pairs are -3. Thus, the average of these numbers will be -3/2 for all subsequences that start and end with the same number (not including one of those).
+Now, take all of the repeating subsequences out of the original sequence. The only thing that will be left will be a sequence <math>\{0,3,6,9,\cdots,3k\}</math> for some even <math>k</math>. Since we started with 2006 terms, we removed <math>2006 - k</math> (an even number) with an average of -3/2. Thus, the sum of both this remaining sequence and the removed stuff is <math>(2006 - k)( - 3/2) + \sum_{i = 1}^k3k = (3/2)(k - 2006 + k(k + 1)) = 3/2(k^2 + 2k - 2006)</math>. This must be minimized, so we find the roots: <math>k^2 + 2k = 2006\implies (k + 1)^2 = 2007</math> and <math>44^2 = 1936 < 2007 < 2025 = 45^2</math>. Plugging in <math>k = 44</math> yields <math>(3/2)(2025 - 2007) = 27</math> (and <math>k = 42</math> yields <math>- 237</math>, a worse result). Thus, <math>\fbox{027}</math> is the closest to zero this sum can get.
+=== Solution 3 ===
+We know <math>|x_k| = |x_{k - 1} + 3|</math>.  We get rid of the absolute value by squaring both sides: <math>{x_k}^2 = {x_{k - 1}}^2 + 6{x_{k - 1}} + 9\Rightarrow {x_k}^2 - {x_{k - 1}}^2 = 6{x_{k - 1}} + 9</math>. So we set this up:
+<math>\begin{eqnarray*} {x_1}^2 - {x_0}^2 & = & 6{x_0} + 9 \\
+{x_2}^2 - {x_1}^2 & = & 6{x_1} + 9 \\
+& \vdots & \\
+{x_{2007}}^2 - {x_{2006}}^2 & = & 6{x_{2006}} + 9 \end{eqnarray*}</math>
+There are <math>2007</math> equations. Sum them. We get:
+<math>{x_{2007}}^2 = 6\left(x_1 + x_2 + \cdots + x_{2006}\right) + 9\cdot{2007}</math>
+So <math>|x_1 + x_2 + \cdots + x_{2006}| = \frac {\left|{x_{2007}}^2 - 9\cdot{2007}\right|}{6}</math>
+We know <math>3\ |\ x_{2007}</math> and we want to minimize <math>\left|{x_{2007}}^2 - 9\cdot{2007}\right|</math>, so <math>x_{2007}</math> must be <math>3\cdot{45}</math> for it to be minimal (<math>45^2 = 2025</math> which is closest to <math>2007</math>).
+This means that <math>|x_1 + x_2 + \cdots + x_{2006}| = \left|\frac {9(2025 - 2007)}{6}\right| = \boxed{27}</math>
 == See also ==
 {{AIME box|year=2006|n=I|num-b=14|after=Last Question}}

2006 AIME I (Problems • Answer Key • Resources)
Preceded by Problem 14	Followed by Last Question
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search