China Western Mathematical Olympiad

Let $n=2009$. Then we have the following three cases:

(1) If $x_n=7^{5^{x_{n-2}}}$, then $x_n\equiv 7(\mathrm{mod}100)$. Since both $5$ and $7$ are odd, $x_k$ ($1\le k\le n$) all are odd. $5^{x_{n-2}}\equiv 1(\mathrm{mod}4)$, i.e. $5^{x_{n-2}}=4k+1$ for some positive integer $k$. If $k,m\ge 0$, it follows from mathematical induction that $$7^{4k+m}\equiv 7^m(\mathrm{mod}100),$$ and hence $$x_n=7^{5^{x_{n-2}}}=7^{4k+1}\equiv 7(\mathrm{mod}100).$$

(2) If $x_n=7^{7^{x_{n-2}}}$, then $x_n\equiv 43(\mathrm{mod}100)$. $$7^{x_{n-2}}\equiv (-1{)}^{x_{n-2}}\equiv -1\equiv 3(\mathrm{mod}4),$$ so $7^{x_{n-2}}=4k+3$, for some positive integer $k$. Hence, $$x_n=7^{7^{x_{n-2}}}=7^{4k+3}\equiv 7^3\equiv 43(\mathrm{mod}100).$$

(3) If $x_n=5^{x_{n-1}}$, then $x_n\equiv 25(\mathrm{mod}100)$. It follows from mathematical induction that if $n\ge 2$, then $5^n\equiv 25(\mathrm{mod}100)$. It is obvious that $x_{n-1}>2$, and hence $x_n=5^{x_{n-1}}\equiv 25(\mathrm{mod}100)$.

Therefore, the possible cases of the last two digits of $x_{2009}$ are $07$, $25$, $43$.