Drunken Tower of Hanoi

Bob is very familiar with the famous mathematical puzzle/game, “Tower of Hanoi,” which consists of three upright rods and disks of different sizes that can slide onto any of the rods. The game begins with a stack of $n$ disks placed on the leftmost rod in descending order by size. The objective of the game is to move all of the disks from the leftmost rod to the rightmost rod, given the following restrictions:
Only one disk can be moved at a time.
A valid move consists of taking the top disk from one stack and placing it onto another stack (or an empty rod).
No disk can be placed on top of a smaller disk.
Moving on to a variant of this game, consider a long room $k$ units (square tiles) wide, labeled from $1$ to $k$ in ascending order. Three rods are placed at squares $a$, $b$, and $c$, and a stack of $n$ disks is placed on the rod at square $a$.
Bob begins the game standing at square $b$. His objective is to play the Tower of Hanoi game by moving all of the disks to the rod at square $c$. However, Bob can only pick up or set down a disk if he is on the same square as the rod/stack in question.
Unfortunately, Bob is also drunk. On a given move, Bob will either stumble one square to the left or one square to the right with equal probability, unless Bob is at either end of the room, in which case he can only move in one direction. Despite Bob’s inebriated state, he is still capable of following the rules of the game itself, as well as choosing when to pick up or put down a disk.
The following animation depicts a side-view of a sample game for $n = 3$, $k = 7$, $a = 2$, $b = 4$, and $c = 6$:

Let $E(n, k, a, b, c)$ be the expected number of squares that Bob travels during a single optimally-played game. A game is played optimally if the number of disk-pickups is minimized.
Interestingly enough, the result is always an integer. For example, $E(2,5,1,3,5) = 60$ and $E(3,20,4,9,17) = 2358$.
Find the last nine digits of $\sum_{1\le n \le 10000} E(n,10^n,3^n,6^n,9^n)$.

To solve this problem, we can use dynamic programming to calculate the expected number of squares traveled by Bob in a single optimally-played game.

First, let’s define a function `calculate_moves` that takes the number of disks `n`, the width of the room `k`, and the positions of the rods `a`, `b`, `c`, and returns the expected number of squares traveled by Bob in an optimal game.

“`python
def calculate_moves(n, k, a, b, c):
memo = {} # memoization dictionary to store calculated values

def dp(n, b):
# Base case: if there are no disks left, no moves are needed
if n == 0:
return 0

# Check if the sub-problem has already been solved
if (n, b) in memo:
return memo[(n, b)]

# Calculate the expected number of moves for the sub-problem
expected_moves = float(‘inf’) # start with a large value

# Calculate number of moves if Bob picks up a disk from rod ‘b’
for a_or_c in [a, c]:
# Calculate the number of squares required to reach rod ‘a/c’ from rod ‘b’
squares_required = abs(b – a_or_c)

# Calculate the number of picks required to move the top disk from rod ‘b’ to rod ‘a/c’
picks_required = dp(n – 1, a_or_c)

# Total number of moves required for this move
total_moves = squares_required + picks_required

# Update the expected minimum moves
expected_moves = min(expected_moves, total_moves)

# Calculate number of moves if Bob puts down a disk onto rod ‘b’
for a_or_c in [a, c]:
# Calculate the number of squares required to reach rod ‘b’ from rod ‘a/c’
squares_required = abs(b – a_or_c)

# Calculate the number of picks required to move the top disk from rod ‘a/c’ to rod ‘b’
picks_required = dp(n – 1, b)

# Total number of moves required for this move
total_moves = squares_required + picks_required

# Update the expected minimum moves
expected_moves = min(expected_moves, total_moves)

# Memoize the result
memo[(n, b)] = expected_moves

return expected_moves

return dp(n, b)
“`

Now, we can calculate the sum

“`python
s = 0 # stores the sum of last nine digits
for n in range(1, 10001):
moves = calculate_moves(n, 10 ** n, 3 ** n, 6 ** n, 9 ** n)
s += moves

# Get the last nine digits of the sum
result = s % int(1e9)
“`

The variable `result` will store the last nine digits of the required sum.

Note: Since the recursive solution involves overlapping subproblems, the dynamic programming approach with memoization allows us to efficiently solve larger instances of the problem. However, computing the sum for `n = 10000` might take a while as it involves a large number of calculations.

More Answers: