Project Euler 497

发表于 分类于 阅读次数： 本文字数： 3.3k 阅读时长 ≈ 3 分钟

Project Euler 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:

  1. Only one disk can be moved at a time.

  2. A valid move consists of taking the top disk from one stack and placing it onto another stack (or an empty rod).

  3. 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 \(\sum_{1\le n\le10000} E(n,10^n,3^n,6^n,9^n)\).

解决方案

核心是把总期望拆成两部分：

  1. 最优汉诺塔过程中，各柱间有向移动会发生多少次；
  2. 随机游走从格子 \(x\) 走到格子 \(y\) 的期望步数。

线性期望把两者直接相乘求和即可。

首先计算随机游走时：从格子 \(x\) 到 \(y\) 的期望步数。记 \(e(x,y)\) 为 Bob 从格子 \(x\) 首次到达格子 \(y\) 的期望步数（左右端点反射）。

当\(x<y\)时，设 \(H_i\) 为从 \(i\) 到 \(y\) 的期望步数（\(1\le i\le y\)），那么有：\(H_y=0, H_1=1+H_2,H_i=1+\dfrac{H_{i-1}+H_{i+1}}2 (1<i<y).\)

令\(\Delta_i=H_i-H_{i+1}(1\le i<y).\)由递推得\(\Delta_i=\Delta_{i-1}+2, \Delta_1=1\)所以\(\Delta_i=2i-1.\)于是\(\displaystyle H_x=\sum_{i=x}^{y-1}\Delta_i=\sum_{i=x}^{y-1}(2i-1)=(y-1)^2-(x-1)^2.\)即

\[ e(x,y)=(y-1)^2-(x-1)^2, x<y. \]

当\(x>y\)时，把房间左右镜像（\(i\mapsto k+1-i\)）即可得到

\[ e(x,y)=(k-y)^2-(k-x)^2, x>y. \]

最少拿盘次数就是标准最优汉诺塔，盘子移动序列唯一。定义向量（子问题起点在源柱）：\(X_n=(AB_n,AC_n,BA_n,BC_n,CA_n,CB_n),\)表示：把 \(n\) 个盘从 \(A\) 移到 \(C\)（辅助柱 \(B\)），且 Bob 初始站在 \(A\) 时，这 6 种有向柱间移动各发生多少次。

显然\(X_1=(0,1,0,0,0,0).\)把 \(n+1\) 的过程拆成：先做 \(n\): \(A\to B\)；Bob 走 \(B\to A\)；最大盘 \(A\to C\)；Bob 走 \(C\to B\)；再做 \(n\): \(B\to C\)。可得递推（按 \((AB,AC,BA,BC,CA,CB)\) 顺序）：

\[ \begin{aligned} AB'&=AC+BA\\ AC'&=AB+BC+1\\ BA'&=AB+CA+1\\ BC'&=AC+CB\\ CA'&=BA+CB\\ CB'&=BC+CA+1. \end{aligned} \]

题目真实起点是 Bob 在 \(B\)，不是在 \(A\)。因此真实计数为\(F_n=(AB_n,AC_n,BA_n+1,BC_n,CA_n,CB_n),\)即额外加一次初始 \(B\to A\)。

设\(D_{AB}=e(a,b),D_{AC}=e(a,c),D_{BA}=e(b,a),D_{BC}=e(b,c),D_{CA}=e(c,a),D_{CB}=e(c,b).\)则

更进一步，将这个矩阵记为

\[ A=\begin{bmatrix} 0&1&1&0&0&0\\ 1&0&0&1&0&0\\ 1&0&0&0&1&0\\ 0&1&0&0&0&1\\ 0&0&1&0&0&1\\ 0&0&0&1&1&0 \end{bmatrix}. \]

那么有\(X_{n+1}=AX_n,\)所以\(X_n=A^{n-1}X_1,(n\ge 1).\)

因此最终有：

\[ E(n,k,a,b,c)=D_{BA}+X_n\cdot(D_{AB},D_{AC},D_{BA},D_{BC},D_{CA},D_{CB})^T. \]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import numpy as np

MOD = 10 ** 9
N = 10000

def solve(N):
    T = np.array([
        [0, 1, 1, 0, 0, 0],
        [1, 0, 0, 1, 0, 0],
        [1, 0, 0, 0, 1, 0],
        [0, 1, 0, 0, 0, 1],
        [0, 0, 1, 0, 0, 1],
        [0, 0, 0, 1, 1, 0],
    ], dtype=np.int64)

    bvec = np.array([0, 1, 1, 0, 0, 1], dtype=np.int64)
    x = np.array([0, 1, 0, 0, 0, 0], dtype=np.int64)

    k = a = b = c = 1
    ans = 0

    for _ in range(1, N + 1):
        k = k * 10 % MOD
        a = a * 3 % MOD
        b = b * 6 % MOD
        c = c * 9 % MOD

        eab = ((b - 1) * (b - 1) - (a - 1) * (a - 1)) % MOD
        eac = ((c - 1) * (c - 1) - (a - 1) * (a - 1)) % MOD
        eba = ((k - a) * (k - a) - (k - b) * (k - b)) % MOD
        ebc = ((c - 1) * (c - 1) - (b - 1) * (b - 1)) % MOD
        eca = ((k - a) * (k - a) - (k - c) * (k - c)) % MOD
        ecb = ((k - b) * (k - b) - (k - c) * (k - c)) % MOD

        e = np.array([eab, eac, eba, ebc, eca, ecb], dtype=np.int64)

        cur = (eba + int(e.dot(x) % MOD)) % MOD
        ans = (ans + cur) % MOD

        x = (T.dot(x) + bvec) % MOD
    return ans

print(solve(N))