Problem 497

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 ∑_{1≤n≤10000} E(n,10ⁿ,3ⁿ,6ⁿ,9ⁿ).

醉酒汉诺塔

鲍勃非常熟悉著名的数学谜题汉诺塔：这个游戏包含了三根竖直的柱子和能够串在柱子上的不同大小的盘子。游戏的开始状态是n个盘子按从大到小的顺序依次串在最左边的柱子上；游戏的目标是在以下的限制条件下，把所有的盘子都串到最右边的柱子上：

一次只能移动一个盘子。
一个有效的移动包括拿起一堆盘子最顶上的一个以及把它放在另一堆盘子的顶端（或者一个空的柱子上）。
每个盘子都不能放在比它小的盘子上。

现在我们来玩这个游戏的一个变种，在一间k单位长并依次标上了1至k的房间里，三根柱子方别被摆在了标有a、b和c的位置，在a位置的柱子上有n个盘子。

鲍勃从位置b开始进行游戏，他的目标是像汉诺塔那样把所有盘子移动到位置c的柱子上，但是他只能在有柱子的地方捡起或放下盘子。

不幸的是，鲍勃喝醉了，每当他要移动的时候，他将以相同的概率向左或向右走一步，除非他是在房间的某个尽头，只能往另一个方向走。不过，Bob即使是在喝醉的状态下，依然能够按照游戏的规则来合理选择何时应该捡起或放下盘子。

下面的动画是一个简单游戏的侧面演示，这个游戏中n = 3，k = 7，a = 2，b = 4，c = 6：

记E(n,k,a,b,c)是Bob按照最优的方式完成游戏所需要走过的路程的期望值，在这里“最优”的衡量标准是捡起盘子的次数最少。

非常有趣的是，计算结果总是一个整数，例如，E(2,5,1,3,5) = 60以及E(3,20,4,9,17) = 2358。

求∑_{1≤n≤10000} E(n,10ⁿ,3ⁿ,6ⁿ,9ⁿ)的最后九位数字。