2008 AMC 12A Problem 17

Question

Let

a_1,

a_2,

\ldots

be a sequence of integers determined by the rule

a_n = \frac{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

If

a_1

is even then

a_2 \lt a_1,

so

a_1

must be odd

Split the odd case according to whether

a_1 \equiv 1

or

a_1 \equiv 3 \pmod 4

If

a_1

is even, then

a_2 = \frac{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 = \frac{3a_1 + 1}{2}

and

a_4 = \frac{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 = \frac{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.

Problem 17 in other years