2009 AMC 12A Problem 24

Question

The tower function of twos is defined recursively as follows:

T(1) = 2

and

T(n + 1) = 2^{T(n)}

for

n \ge 1.

Let

A = (T(2009))^{T(2009)}

and

B = (T(2009))^A.

What is the largest integer

k

such that

\underbrace{\log_2 \log_2 \log_2 \ldots \log_2}_{k} B

is defined?

2009

2010

2011

2012

2013

Answer: E

Concepts:recursion logarithm exponent

Difficulty rating: 2650

Small hint:

Repeatedly applying

\log_2

peels one level off a tower:

\log_2 T(n + 1) = T(n)

Big hint:

Track how many logs

B = (T(2009))^A

can survive before the value drops below

1

Solution:

Since

\log_2 T(n + 1) = T(n),

each application of

\log_2

strips one

2

off the top of a tower of twos.

Write

T_j=T(j),

and let

L_j

be the result of applying

\log_2

to

B

exactly

j

times. The first two results are

\begin{aligned} L_1 &= A\,T_{2008}, \\ L_2 &= T_{2009}T_{2008}+T_{2007}. \end{aligned}

For the lower bound,

\begin{aligned} L_3 &\gt \log_2(T_{2009}T_{2008}) \\ &= T_{2008}+T_{2007} \\ &\gt T_{2008}. \end{aligned}

Repeatedly taking logarithms gives

L_{k+3} \gt T_{2008-k}

for

0\le k\le 2007.

In particular,

L_{2010}\gt2,

so

L_{2011}\gt1

and

L_{2012}\gt0.

Thus

L_{2013}

is defined.

For the upper bound,

T_{2007}\lt T_{2008}T_{2009},

so

\begin{aligned} L_3 &\lt 1+T_{2007}+T_{2008} \\ &\lt 2T_{2008}, \\ L_4 &\lt 1+T_{2007} \lt T_{2008}. \end{aligned}

Repeating the last comparison gives

L_{k+4}\lt T_{2008-k}

for

0\le k\le2007.

Hence

L_{2011}\lt2.

Together with the lower bound, this yields

0\lt L_{2012}\lt1,

so

L_{2013}\lt0.

Therefore

L_{2014}

is undefined, and the largest possible

k

is

2013.

Thus, the correct answer is E.