1998 AIME Problems/Problem 8

Revision as of 22:12, 7 September 2007 by Azjps (talk | contribs) (Solution 1: fix lines)

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,

  • $n \equiv 0 \pmod{2}\quad\quad F_{n-1}\cdot 1000-F_n\cdot x$
  • $\displaystyle n \equiv 1 \pmod{2}\quad\quad F_{n}\cdot 1000-F_{n-1}\cdot x$

Solution 1

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

  1. $\displaystyle x > 0$
  2. $1000 - x < 0 \Longrightarrow x < 1000$
  3. $\displaystyle 2x - 1000 < 0 \Longrightarrow x > 500$
  4. $3000 - 2x < 0 \Longrightarrow x < 666.\overline{6}$
  5. $5x - 3000 < 0 \Longrightarrow x > 600$

And in general,

  • $n \equiv 0 \pmod{2}\quad\quad x < \frac{F_{n-1}}{F_n} \cdot 1000$
  • $n \equiv 1 \pmod{2}\quad\quad x > \frac{F_{n-1}}{F_{n}} \cdot 1000$

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} - 1 \approx .61803 \displaystyle$, so $1000 \cdot \frac{F_{n-1}}{F_n}$ approaches $x = 618$.

See also

1998 AIME (ProblemsAnswer KeyResources)
Preceded by
Problem 7
Followed by
Problem 9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions