Difference between revisions of "1998 AIME Problems/Problem 8"

(Solution 2)
m (Problem)
(2 intermediate revisions by one other user not shown)
Line 2: Line 2:
 
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?
 
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>5x - 3000</math> || <math>5000 - 8x</math>
 
|}
 
  
It is now apparent that each term can be written as
 
  
*<math>n \equiv 0 \pmod{2}\quad\quad F_{n-1}\cdot 1000-F_n\cdot x</math>
+
Solutions were removed
*<math>n \equiv 1 \pmod{2}\quad\quad F_{n}\cdot 1000-F_{n-1}\cdot x</math>
+
__TOC__
 
where the <math> F_{n}</math> are [[Fibonacci number]]s. This can be proven through induction.
 
 
 
=== Solution 1 ===
 
We can start to write out some of the inequalities now:
 
 
 
#<math>x > 0</math>
 
#<math>1000 - x > 0 \Longrightarrow x < 1000</math>
 
#<math>2x - 1000 > 0 \Longrightarrow x > 500</math>
 
#<math>2000 - 3x > 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>x < \frac{F_{7}}{F_{8}} \cdot 1000 = \frac{13}{21} \cdot 1000 = 618.\overline{18}</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 = \boxed{618}.</math>
+
Help why is there no solution
  
 
== See also ==
 
== See also ==

Revision as of 21:09, 18 October 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?



Solutions were removed

Contents

 [hide


Help why is there no solution

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

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