Problem:
A sequence a1,a2,… of non-negative integers is defined by the rule an+2= ∣an+1−an∣ for n≥1. If a1=999,a2<999, and a2006=1, how many different values of a2 are possible?
Answer Choices:
A. 165
B. 324
C. 495
D. 499
E. 660
Solution:
The condition an+2=∣an+1−an∣ implies that an and an+3 have the same parity for all n≥1. Because a2006 is odd, a2 is also odd. Because a2006=1 and an is a multiple of gcd(a1,a2) for all n, it follows that 1=gcd(a1,a2)= gcd(33⋅37,a2). There are 499 odd integers in the interval [1,998], of which 166 are multiples of 3,13 are multiples of 37 , and 4 are multiples of 3⋅37=111. By the Inclusion-Exclusion Principle, the number of possible values of a2 cannot exceed 499−166−13+4=324.
To see that there are actually 324 possibilities, note that for n≥3,an< max(an−2,an−1) whenever an−2 and an−1 are both positive. Thus aN=0 for some N≤1999. If gcd(a1,a2)=1, then aN−2=aN−1=1, and for n>N the sequence cycles through the values 1,1,0. If in addition a2 is odd, then a3k+2 is odd for k≥1, so a2006=1.
The problems on this page are the property of the MAA's American Mathematics Competitions