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