View source

== Problem ==
Except for the first two terms, each term of the sequence <math>1000, x, 1000 - x,\ldots</math> 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 <math>x</math> produces a sequence of maximum length?

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

{| class="wikitable"
|-
| 0 || 1 || 2 || 3 || 4 || 5 || 6
|-  
| <math>\quad 1000 \quad</math><font color="white">aa</font> || <math>\quad x \quad</math><font color="white">aaa</font> || <math>1000 - x</math> || <math>2x - 1000</math><font color="white">a</font> || <math>2000 - 3x</math> || <math>\displaystyle 3000 - 5x</math> || <math>8x - 5000</math>
|}

By now its obvious that the numbers are related to the [[Fibonacci number]]s.

Thus, 
*<math>n \equiv 0 \pmod{2}\quad\quad F_{n-1}\cdot 1000-F_n\cdot x</math> 
*<math>\displaystyle n \equiv 1 \pmod{2}\quad\quad F_{n}\cdot 1000-F_{n-1}\cdot x</math>

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

#<math>\displaystyle x > 0</math>
#<math>1000 - x < 0 \Longrightarrow x < 1000</math>
#<math>\displaystyle 2x - 1000 < 0 \Longrightarrow x > 500</math>
#<math>3000 - 2x < 0 \Longrightarrow x < 666.\overline{6}</math>
#<math>5x - 3000 < 0 \Longrightarrow x > 600</math>

And in general,

*<math>n \equiv 0 \pmod{2}\quad\quad x < \frac{F_{n-1}}{F_n} \cdot 1000</math> 
*<math>n \equiv 1 \pmod{2}\quad\quad x > \frac{F_{n-1}}{F_{n}} \cdot 1000</math>

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

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

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

Thus the sequence is maximized when <math>x = 618</math>.

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

== See also ==
{{AIME box|year=1998|num-b=7|num-a=9}}

[[Category:Intermediate Number Theory Problems]]