Problem:
Let S be the set of all ordered triples of integers (a1​,a2​,a3​) with 1≤a1​,a2​,a3​≤ 10. Each ordered triple in S generates a sequence according to the rule an​= an−1​⋅∣an−2​−an−3​∣ for n≥4. Find the number of such sequences for which an​=0 for some n.
Solution:
Note that if ak−1​=ak​, then ak+2​=0, and if ∣ak​−ak−1​∣=1, then ak+2​=ak+1​, and ak+4​=0. Therefore the sequence contains a term of 0 if (a1​,a2​,a3​) has one of the forms (j,j,k),(j,k,k),(j,j+1,k),(j,k,k+1),(j,j−1,k), or (j,k,k−1). There are 100 triples with each of the first two forms and 90 triples with each of the other four forms, for a total of 2⋅100+4⋅90=560. However, the 10 triples of the form (j,j,j), the 9 triples of each of the forms (j,j,j+1),(j,j+1,j), (j,j+1,j+1),(j,j,j−1),(j,j−1,j), and (j,j−1,j−1), and the 8 triples of each of the forms (j,j+1,j+2) and (j,j−1,j−2) have each been counted twice, so there are 560−10−6⋅9−2⋅8=480 triples of one of these forms.
In addition, if (a1​,a2​,a3​)=(j,j+2,1) or (j,j−2,1), then a4​=2,a4​−a3​=1, and a8​=0. There are 8 triples of each of these forms, but (3,1,1) and (4,2,1) have already been counted. Thus there are at least 480+8+6=494 sequences that contain a term of 0.
To see that there are no other possibilities, note first that if ∣a2​−a1​∣≥2, ∣a3​−a2​∣≥2, and a3​≥2, then a4​≥2a3​>a3​, and ∣a4​−a3​∣≥a3​≥2. The same argument then establishes that ak​>ak−1​ for k≥4, so akâ€‹î€ =0 for all k. Further, if ∣a2​−a1​∣=m≥3,∣a3​−a2​∣≥2, and a3​=1, then a4​=m≥3 and ∣a4​−a3​∣=m−1≥2. As above, ak​>ak−1​ for k≥4. Therefore the number of sequences that contain a term of 0 is 494​.
The problems on this page are the property of the MAA's American Mathematics Competitions