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://webptt.com/m.aspx?n=bbs/puzzle/M.1421269768.A.5BC.html