2006 AIME I Problem 15

Question

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

Answer

Answer: 27

Concepts:recursion telescoping parity optimization

Difficulty rating: 3370

Small hint:

Square the recurrence:

x_k^2 = (x_{k-1} + 3)^2.

Summing over

k

telescopes into a formula for

x_1 + \cdots + x_{2006}.

Big hint:

Each

x_k

is a multiple of

3

with the parity of

k,

so choose

x_{2007}

with square as close as possible to

9 \cdot 2007

Solution:

Squaring the recurrence gives

x_k^2 = (x_{k-1} + 3)^2

= x_{k-1}^2 + 6 x_{k-1} + 9.

Summing for

k = 1

to

2007

telescopes:

x_{2007}^2 = x_0^2 + 6 \sum_{k=0}^{2006} x_k + 9 \cdot 2007,

so with

x_0 = 0,

\begin{aligned} &x_1 + x_2 + \cdots + x_{2006} \\ &= \frac{x_{2007}^2 - 18063}{6}. \end{aligned}

Induction shows each

x_k

is a multiple of

3

whose parity matches that of

k,

so

x_{2007}

is an odd multiple of

3.

To minimize

\left|x_{2007}^2 - 18063\right|,

take the odd multiple of

3

whose square is nearest

18063:

that is

\pm 135,

with

135^2 = 18225,

giving

\frac{18225 - 18063}{6} = 27

(the neighbors

129

and

141

give

237

and

303

).

This value is attained: take

x_k = 3k

for

k \le 45,

and thereafter alternate

x_k = -138

for even

k

and

x_k = 135

for odd

k;

then

x_{2007} = 135

and the sum is

27.

So the minimum is

27.