Problem:
Let a1,a2,… be a sequence of integers determined by the rule an=an−1/2 if an−1 is even and an=3an−1+1 if an−1 is odd. For how many positive integers a1≤2008 is it true that a1 is less than each of a2,a3, and a4?
Answer Choices:
A. 250
B. 251
C. 501
D. 502
E. 1004
Solution:
If a1 is even, then a2=(a1/2)<a1, so the required condition is not met. If a1≡1(mod4), then a2=3a1+1 is a multiple of 4 , so a3= (3a1+1)/2, and a4=(3a1+1)/4≤a1. Hence the required condition is also not met in this case. If a1≡3(mod4), then a2 is even but not a multiple of 4 . It follows that a3=(3a1+1)/2>a1, and a3 is odd, so a4=3a3+1>a3>a1. Because 2008 is a multiple of 4 , a total of 42008=502 possible values of a1 are congruent to 3(mod4). These 502 values of a1 meet the required condition.
Note: It is a famous unsolved problem to show whether or not the number 1 must be a term of this sequence for every choice of a1.
The problems on this page are the property of the MAA's American Mathematics Competitions