Problem:
Find the smallest integer k for which the conditions
(1) a1​,a2​,a3​,… is a nondecreasing sequence of positive integers
(2) an​=an−1​+an−2​ for all n>2
(3) a9​=k
are satisfied by more than one sequence.
Solution:
Suppose a1​=xi​ and a2​=xi​+hi​ for i=1,2, with x2​>x1​>0 and h1​>h2​≥0, so
a9​=34x1​+21h1​=k=34x2​+21h2​
If h2​ were greater than zero, then k would not be the smallest integer for which the equation 34x+21h=k has a non-unique solution, since 34x1​+21(h1​−h2​)=34x2​ would yield a smaller k. Thus,
34x1​+21h1​=34x2​, that is, 21h1​=34(x2​−x1​)
so h1​ must be a positive multiple of 34, and x2​ and x1​ must differ by a multiple of 21. The smallest possible values of h1​,h2​,x1​,x2​, and a9​ that satisfy these conditions and those of the problem are thus h1​=34,h2​=0,x1​=1,x2​=22, and a9​=34⋅22+21⋅0=748. Note that the sequences
1,35,36,71,107,178,285,463,748,…22,22,44,66,110,176,286,462,748,…​
both have k=748​ as their ninth term.
OR
Note that a9​=13a1​+21a2​, so the requested value of k is the least positive integer k such that 13x+21y=k has more than one solution (x,y) with 0<x≤y and x and y integers. If k has this property, then there are integers x,y,u and v with 0<x<u≤v<y and
13x+21y=k=13u+21v
Then 21(y−v)=13(u−x) which implies that u−x is divisible by 21. Thus u−x≥21 and v≥u≥22. Now
k=13u+21v≥13⋅22+21⋅22=748​
To demonstrate that 13x+21y=748 has more than one solution, rewrite the equation as 13(x+y)+8y=57⋅13+7, and conclude that 13 must be a divisor of (8y−7). A few trials reveal that y=9 satisfies this condition. Thus (43,9),(43− 21,9+13)=(22,22), and (43−2⋅21,9+2⋅13)=(1,35) are solutions. Note that (22,22) and (1,35) yield the previously mentioned sequences, and (43,9) yields a sequence that satisfies conditions (2) and (3), but not (1).
The problems on this page are the property of the MAA's American Mathematics Competitions