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