Difference between revisions of "1998 AIME Problems/Problem 8"
(Problem / Solution) |
|||
| Line 1: | Line 1: | ||
== Problem == | == 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 == | == 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 \approx 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 == | == See also == | ||
| − | + | {{AIME box|year=1998|num-b=7|num-a=9}} | |
| + | |||
| + | [[Category:Intermediate Number Theory Problems]] | ||
Revision as of 21:11, 7 September 2007
Problem
Except for the first two terms, each term of the sequence 
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 
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 |
 aa |
 aaa |
 |
 a |
 |
 |
|
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 , so we can just calculate for some large value of 
(randomly, 10, 11):
Thus the sequence is maximized when 
.
Solution 2
It is well known that 
, so 
approaches .
See also
| 1998 AIME (Problems • Answer Key • Resources) | ||
| 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 | ||
