2008 AMC 12A Problem 17

Problem 17 of 25IntermediateAlgebra Number Theory

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?

Show solution

Solution

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.

More practice

Concepts: recursion · modular arithmetic · casework

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.