Skip to main content

2009 AMC 12A Problem 24

Problem 24 of 25HarderAlgebra

The tower function of twos is defined recursively as follows: T(1)=2T(1) = 2 and T(n+1)=2T(n)T(n + 1) = 2^{T(n)} for n1.n \ge 1. Let A=(T(2009))T(2009)A = (T(2009))^{T(2009)} and B=(T(2009))A.B = (T(2009))^A. What is the largest integer kk such that log2log2log2log2kB\underbrace{\log_2 \log_2 \log_2 \ldots \log_2}_{k} B is defined?

Answer choices

Show solution

Solution

Since log2T(n+1)=T(n),\log_2 T(n + 1) = T(n), each application of log2\log_2 strips one 22 off the top of a tower of twos. Write Tj=T(j),T_j=T(j), and let LjL_j be the result of applying log2\log_2 to BB exactly jj times. The first two results are L1=AT2008,L2=T2009T2008+T2007. \begin{aligned} L_1 &= A\,T_{2008}, \\ L_2 &= T_{2009}T_{2008}+T_{2007}. \end{aligned} For the lower bound, L3>log2(T2009T2008)=T2008+T2007>T2008. \begin{aligned} L_3 &\gt \log_2(T_{2009}T_{2008}) \\ &= T_{2008}+T_{2007} \\ &\gt T_{2008}. \end{aligned} Repeatedly taking logarithms gives Lk+3>T2008kL_{k+3} \gt T_{2008-k} for 0k2007.0\le k\le 2007. In particular, L2010>2,L_{2010}\gt2, so L2011>1L_{2011}\gt1 and L2012>0.L_{2012}\gt0. Thus L2013L_{2013} is defined. For the upper bound, T2007<T2008T2009,T_{2007}\lt T_{2008}T_{2009}, so L3<1+T2007+T2008<2T2008,L4<1+T2007<T2008. \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 Lk+4<T2008kL_{k+4}\lt T_{2008-k} for 0k2007.0\le k\le2007. Hence L2011<2.L_{2011}\lt2. Together with the lower bound, this yields 0<L2012<1,0\lt L_{2012}\lt1, so L2013<0.L_{2013}\lt0. Therefore L2014L_{2014} is undefined, and the largest possible kk is 2013.2013. Thus, the correct answer is E.

More practice

Concepts: recursion · logarithm · exponent

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