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的和的末九位數。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 206.196.186.173
※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1421269768.A.5BC.html