Question

Let $a_1, a_2, \ldots$ be a sequence of integers determined by the rule $a_n = a_{n-1}/2$ if $a_{n-1}$ is even and $a_n = 3a_{n-1} + 1$ if $a_{n-1}$ is odd. For how many positive integers $a_1 \le 2008$ is it true that $a_1$ is less than each of $a_2, a_3,$ and $a_4?$

$250$

$251$

$501$

$502$

$1004$

Answer: D

Concepts:recursion modular arithmetic casework

Difficulty rating: 1870

Solution:

If $a_1$ is even, then $a_2 = a_1/2 \lt a_1,$ so the condition fails.

If $a_1 \equiv 1 \pmod 4,$ then $a_2 = 3a_1 + 1$ is a multiple of $4,$ so $a_3 = (3a_1 + 1)/2$ and $a_4 = (3a_1 + 1)/4 \le a_1,$ and again the condition fails.

If $a_1 \equiv 3 \pmod 4,$ then $a_2$ is even but not a multiple of $4,$ so $a_3 = (3a_1 + 1)/2 \gt a_1,$ and $a_3$ is odd, giving $a_4 = 3a_3 + 1 \gt a_3 \gt a_1.$ The condition holds.

Exactly $\tfrac{2008}{4} = 502$ values of $a_1 \le 2008$ satisfy $a_1 \equiv 3 \pmod 4.$

Thus, D is the correct answer.

2008 AMC 12A Problem 17

Answer: D

Difficulty rating: 1870

Solution:

Problem 17 in Other Years