1998 AIME Problems/Problem 8

From AoPSWiki

Problem

Except for the first two terms, each term of the sequence $1000, x, 1000 - x,\ldots$ is obtained by subtracting the preceding term from the one before that. The last term of the sequence is the first negative term encounted. What positive integer $x$ produces a sequence of maximum length?

Solution

The best way to start is to just write out some terms.

0	1	2	3	4	5	6
$\quad 1000 \quad$ aa	$\quad x \quad$ aaa	$1000 - x$	$2x - 1000$ a	$2000 - 3x$	$\displaystyle 3000 - 5x$	$8x - 5000$

By now its obvious that the numbers are related to the Fibonacci numbers.

Thus,

Solution 1

We can start to write out some of the inequalities now:

And in general,

It is apparent that the bounds are slowly closing in on $x$ , so we can just calculate $x$ for some large value of $n$ (randomly, 10, 11):

$\displaystyle x < \frac{F_{9}}{F_{10}} \cdot 1000 = \frac{34}{55} \cdot 1000 = 618.\overline{18}$

$\displaystyle x > \frac{F_{10}}{F_{11}} \cdot 1000 = \frac{55}{89} \cdot 1000 \approx 617.977$

Thus the sequence is maximized when $x = 618$ .

Solution 2

It is well known that $\displaystyle \displaystyle \lim_{n\rightarrow\infty} \frac{F_{n-1}}{F_n} = \phi - 1 = \displaystyle \frac{1 + \sqrt{5}}{2} -...$ , so $1000 \cdot \frac{F_{n-1}}{F_n}$ approaches $x = 618$ .

1998 AIME (Problems • Resources)
Preceded by Problem 7	Followed by Problem 9
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Personal tools

Navigation

Search

Toolbox