ProjectEuler 497 Drunken Tower of Hano - 拼圖

497. Drunken Tower of Hanoi

https://projecteuler.net/problem=497

Bob對於有名的數學遊戲「河內塔」非常熟練。該遊戲由三個直立圓柱以及若干中間穿洞

且大小各異的圓盤組成，其中圓盤的洞都至少大到能穿進圓柱。一開始，所有n個圓盤都

穿在最左邊的圓柱上且由大至小往上堆疊。遊戲的目標是要將這些圓盤全數運到最右邊的

柱子上，但移動過程有下列幾個條件要遵守：

　1. 一次只能移動一個圓盤。
　2. 一次移動是指把一個柱子最上面的圓盤移到另一個柱子上。
　3. 比較大的圓盤不能堆放在比較小的圓盤上。

現在考慮這個遊戲的一個變形：現有一個長條狀的房間排著k個瓷磚，並由左而右編號為

1到k。三個圓柱安置在編號a、b、c的瓷磚上。圓盤則一開始都放在編號a瓷磚的圓柱上。

Bob一開始站在b的位置上，並打算用河內塔的規則把圓盤都移到編號c的圓柱上。然而，

他只能在和柱子位於同一個位置時才可以撿起或放下圓盤。

不幸地，Bob喝醉了。在一次移動中，Bob會以相等的機率往左或往右移動一格，除非他

已經在端點上了，此時他就只會折返。然而，即使他移動不受控制，他移動圓盤仍然可以

遵照遊戲規則進行，也能正確判斷什麼時候該撿起或放下圓盤。

下面的動畫顯示了當n = 3、k = 7、a = 2、b = 4以及c = 6時的一種可能的情況。

https://projecteuler.net/project/images/p497_hanoi.gif

令E(n,k,a,b,c)表示Bob在最佳策略下，完成一次遊戲時走的格數的期望值。這裡的最佳策

略指的是圓盤撿起的次數為最少。

有趣的是，這個期望值一定是個整數。例如，E(2,5,1,3,5) = 60以及

E(3,20,4,9,17) = 2358。

請求出ΣE(n, 10^n, 3^n, 6^n, 9^n)對1≦n≦10000的和的末九位數。

--