Project Euler Problem 497
Bob is very familiar with the famous mathematical puzzle/game, "Tower of Hanoi," which consists of three upright rods an
Solution
Answer: 684901360
Let
$$H_k(x,y)$$
denote the expected number of steps for Bob’s drunk walk to go from square $x$ to square $y$ in a corridor of length $k$ with reflecting endpoints.
A standard gambler’s-ruin calculation gives
$$H_k(x,y)=|x-y|,(2k-|x-y|).$$
For the problem data
$$k=10^n,\qquad a=3^n,\qquad b=6^n,\qquad c=9^n,$$
we therefore have
$$H(a,b)=H(b,c)=3^n(2\cdot 10^n-3^n),$$
and
$$H(a,c)=6^n(2\cdot 10^n-6^n).$$
The optimal Tower-of-Hanoi strategy is unique (up to symmetry), so the total expected distance satisfies a linear recurrence.
Writing
$$E_n = E(n,10^n,3^n,6^n,9^n),$$
the Hanoi decomposition yields
$$E_n = 2E_{n-1} + H(a,c) + 2H(a,b),$$
which simplifies to
$$E_n = 2E_{n-1} + 2\cdot 6^n(10^n-3^n) + 2\cdot 3^n(2\cdot 10^n-3^n).$$
Reducing modulo $10^9$ and summing from $n=1$ to $10000$ can then be done in $O(N)$ time using modular exponentiation.
A direct implementation gives
$$\sum_{n=1}^{10000} E(n,10^n,3^n,6^n,9^n) \equiv 684901360 \pmod{10^9}.$$
Therefore the last nine digits are:
Answer: 684901360