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 "2002 AIME I Problems/Problem 8"

m
Line 11: Line 11:
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
From <math>(2)</math>, <math>a_9=</math> <math>a_8+a_7=2a_7+a_6=3a_6+2a_5=5a_5+3a_4=8a_4+5a_3=13a_3+8a_2=21a_2+13a_1</math> <math>=k</math>
 +
 
 +
Suppose that <math>a_1=x_0</math> is the smallest possible value for <math>a_1</math> that yields a good sequence, and <math>a_2=y_0</math> in this sequence. So, <math>13x_0+21y_0=k</math>.
 +
 
 +
Since <math>\gcd(13,21)=1</math>, the next smallest possible value for <math>a_1</math> that yields a good sequence is <math>a_1=x_0+21</math>. Then, <math>a_2=y_0-13</math>.
 +
 
 +
By <math>(1)</math>, <math>a_2 \ge a_1 \Rightarrow y_0-13 \ge x_0+21 \Rightarrow y_0 \ge x_0+34 \ge 35</math>. So the smallest value of <math>k</math> is attained when <math>(x_0,y_0)=(1,35)</math> which yields <math>(a_1,a_2)=(1,35)</math> or <math>(22,22)</math>.
 +
 
 +
Thus, <math>k=13(1)+21(35)=\boxed{748}</math> is the smallest possible value of <math>k</math>.
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2002|n=I|num-b=7|num-a=9}}
 
{{AIME box|year=2002|n=I|num-b=7|num-a=9}}

Revision as of 22:14, 29 June 2008

Problem

Find the smallest integer $k$ for which the conditions

(1) $a_1,a_2,a_3\cdots$ is a nondecreasing sequence of positive integers

(2) $a_n=a_{n-1}+a_{n-2}$ for all $n>2$

(3) $a_9=k$

are satisfied by more than one sequence.

Solution

From $(2)$, $a_9=$ $a_8+a_7=2a_7+a_6=3a_6+2a_5=5a_5+3a_4=8a_4+5a_3=13a_3+8a_2=21a_2+13a_1$ $=k$

Suppose that $a_1=x_0$ is the smallest possible value for $a_1$ that yields a good sequence, and $a_2=y_0$ in this sequence. So, $13x_0+21y_0=k$.

Since $\gcd(13,21)=1$, the next smallest possible value for $a_1$ that yields a good sequence is $a_1=x_0+21$. Then, $a_2=y_0-13$.

By $(1)$, $a_2 \ge a_1 \Rightarrow y_0-13 \ge x_0+21 \Rightarrow y_0 \ge x_0+34 \ge 35$. So the smallest value of $k$ is attained when $(x_0,y_0)=(1,35)$ which yields $(a_1,a_2)=(1,35)$ or $(22,22)$.

Thus, $k=13(1)+21(35)=\boxed{748}$ is the smallest possible value of $k$.

See also

2002 AIME I (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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2002_AIME_I_Problems/Problem_8&oldid=26818"