Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1998 AIME Problems/Problem 8"
 
(10 intermediate revisions by 7 users not shown)
Line 10: Line 10:
 
| 0 || 1 || 2 || 3 || 4 || 5 || 6
 
| 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>3000 - 5x</math> || <math>8x - 5000</math>
+
| <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>5x - 3000</math> || <math>5000 - 8x</math>
 
|}
 
|}
  
−
By now its obvious that the numbers are related to the [[Fibonacci number]]s.
+
It is now apparent that each term can be written as
  
−
Thus,
 
 
*<math>n \equiv 0 \pmod{2}\quad\quad F_{n-1}\cdot 1000-F_n\cdot x</math>  
 
*<math>n \equiv 0 \pmod{2}\quad\quad F_{n-1}\cdot 1000-F_n\cdot x</math>  
 
*<math>n \equiv 1 \pmod{2}\quad\quad F_{n}\cdot 1000-F_{n-1}\cdot x</math>
 
*<math>n \equiv 1 \pmod{2}\quad\quad F_{n}\cdot 1000-F_{n-1}\cdot x</math>
 +
 +
where the <math> F_{n}</math> are [[Fibonacci number]]s. This can be proven through induction.
  
 
=== Solution 1 ===
 
=== Solution 1 ===
Line 25: Line 26:
 
#<math>1000 - x > 0 \Longrightarrow x < 1000</math>
 
#<math>1000 - x > 0 \Longrightarrow x < 1000</math>
 
#<math>2x - 1000 > 0 \Longrightarrow x > 500</math>
 
#<math>2x - 1000 > 0 \Longrightarrow x > 500</math>
−
#<math>3000 - 2x > 0 \Longrightarrow x < 666.\overline{6}</math>
+
#<math>2000 - 3x > 0 \Longrightarrow x < 666.\overline{6}</math>
 
#<math>5x - 3000 > 0 \Longrightarrow x > 600</math>
 
#<math>5x - 3000 > 0 \Longrightarrow x > 600</math>
  
Line 35: Line 36:
 
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):
 
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>x < \frac{F_{9}}{F_{10}} \cdot 1000 = \frac{34}{55} \cdot 1000 = 618.\overline{18}</math>
+
<math>x < \frac{F_{7}}{F_{8}} \cdot 1000 = \frac{13}{21} \cdot 1000 = 618.\overline{18}</math>
  
−
<math>x > \frac{F_{10}}{F_{11}} \cdot 1000 = \frac{55}{89} \cdot 1000 \approx 617.977</math>
+
<math>x > \frac{F_{8}}{F_{9}} \cdot 1000 = \frac{21}{34} \cdot 1000 \approx 617.977</math>
  
−
Thus the sequence is maximized when <math>x = 618</math>.
+
Thus the sequence is maximized when <math>x = \boxed{618}.</math>
  
 
=== Solution 2 ===
 
=== Solution 2 ===
−
It is well known that <math>\lim_{n\rightarrow\infty} \frac{F_{n-1}}{F_n} = \phi - 1 =\frac{1 + \sqrt{5}}{2} - 1 \approx .61803</math>, so <math>1000 \cdot \frac{F_{n-1}}{F_n}</math> approaches <math>x = 618</math>.
+
It is well known that <math>\lim_{n\rightarrow\infty} \frac{F_{n-1}}{F_n} = \phi - 1 =\frac{1 + \sqrt{5}}{2} - 1 \approx .61803</math>, so <math>1000 \cdot \frac{F_{n-1}}{F_n}</math> approaches <math>x = \boxed{618}.</math>
  
 
== See also ==
 
== See also ==

Latest revision as of 12:11, 25 November 2024

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$ $5x - 3000$ $5000 - 8x$

It is now apparent that each term can be written as

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

where the $F_{n}$ are Fibonacci numbers. This can be proven through induction.

Solution 1

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

  1. $x > 0$
  2. $1000 - x > 0 \Longrightarrow x < 1000$
  3. $2x - 1000 > 0 \Longrightarrow x > 500$
  4. $2000 - 3x > 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):

$x < \frac{F_{7}}{F_{8}} \cdot 1000 = \frac{13}{21} \cdot 1000 = 618.\overline{18}$

$x > \frac{F_{8}}{F_{9}} \cdot 1000 = \frac{21}{34} \cdot 1000 \approx 617.977$

Thus the sequence is maximized when $x = \boxed{618}.$

Solution 2

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

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1998_AIME_Problems/Problem_8&oldid=235567"