2005 AMC 12A Problem 20

Question

For each

x

in

[0, 1],

define

f(x) = \begin{cases} 2x, & 0 \le x \le \tfrac{1}{2},\\ 2 - 2x, & \tfrac{1}{2} \lt x \le 1. \end{cases}

Let

f^{[2]}(x) = f(f(x)),

and

f^{[n+1]}(x) = f^{[n]}(f(x))

for each integer

n \ge 2.

For how many values of

x

in

[0, 1]

is

f^{[2005]}(x) = \tfrac{1}{2}?

0

2005

4010

2005^2

2^{2005}

Let

g(n)

be the number of solutions of

f^{[n]}(x) = \tfrac{1}{2};

find a recursion for

g(n)

Because

f

maps each of

[0, \tfrac12]

and

[\tfrac12, 1]

onto all of

[0, 1],

each solution splits into two, giving

g(n) = 2\,g(n-1)

Let

g(n)

count the solutions of

f^{[n]}(x) = \tfrac{1}{2}

in

[0, 1].

Since

f

maps each of the two halves

[0, \tfrac12]

and

[\tfrac12, 1]

onto all of

[0, 1],

every solution of

f^{[n-1]}(y) = \tfrac12

comes from two values of

x

(one in each half).

The boundary value

x = \tfrac12

satisfies

f^{[n]}(\tfrac12) = f^{[n-1]}(1) = 0 \ne \tfrac12,

so no solutions are lost, giving

g(n) = 2\,g(n-1).

Since

g(1) = 2,

we conclude

g(2005) = 2^{2005}.

Thus, the correct answer is E.

Problem 20 in other years