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