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