ハノイの塔の「和」に関する数列

f:id:electrolysis:20210102232450p:plain

ハノイの塔というパズルゲームがある。これは 3 本の柱 $A,B,C$ と穴の開いた $n$ 枚の円盤から構成される。ゲーム開始状態では柱 $A$ にすべての円盤が刺さっている。これらのすべての円盤を以下のルールに従って、柱 $C$ に移動させるとゲームは完了する。

開始状態から一貫して、どの柱についても任意の円盤の上にはそれよりも小さい円盤だけがある
1 回の手順ではいずれかの柱の最上部の円盤 1 つを別のいずれかの柱に移動させる

これに従ってゲームを進めるとき、最短手順は $2^n-1$ 回であることが知られている。

また、この最短手順で攻略するための再帰的なアルゴリズムが知られている。

柱 $A$ の上部 $n-1$ 段を柱 $B$ に移動する
柱 $A$ に残った円盤 $n$ を柱 $C$ に移動する
柱 $B$ の $n-1$ 段を柱 $C$ に移動する

これを下に図示する。

f:id:electrolysis:20210102232217p:plain — ハノイの塔の再帰的解法

ja.wikipedia.org

問題
方針
解
- z 変換
- 逆 z 変換
別解
点数表
所感
続編

問題

上記の最短手順で $n$ 段のハノイの塔を攻略するとき、

$k$ 番目に小さい円盤を $k$ とする（最小の円盤が $1$ 、最大の円盤が $n$ ）
各手順について、円盤 $k$ の移動先の柱に点数 $k$ が加算される
最初の段階で各柱の点数は $0$ である

という条件のもとで攻略終了時の柱 $A, B, C$ の点数をそれぞれ $a_n, b_n, c_n$ として、それらを求めよ。

方針

柱 $A$ の上部 $n-1$ 段を柱 $B$ に移動する
柱 $A$ に残った円盤 $n$ を柱 $C$ に移動する
柱 $B$ の $n-1$ 段を柱 $C$ に移動する

以上の 3 段階に分割して考える。

ステップ 1 では、柱 $B$ と柱 $C$ の役割が入れ替わっているので、 $A$ に $a_{n-1}$ 点、 $B$ に $c_{n-1}$ 点、 $C$ に $b_{n-1}$ 点、それぞれ加算される。

ステップ 2 では $C$ に $n$ 点加算される。

ステップ 3 では、柱 $A$ と柱 $B$ の役割が入れ替わっているので、 $A$ に $b_{n-1}$ 点、 $B$ に $a_{n-1}$ 点、 $C$ に $c_{n-1}$ 点、それぞれ加算される。

これらを合算すると、

\begin{cases} \displaystyle a_n = a_{n-1}+b_{n-1} \\ \displaystyle b_n = a_{n-1}+c_{n-1} \\ \displaystyle c_n = b_{n-1}+c_{n-1}+n \end{cases}

という連立漸化式が得られる。また、 $a_0 = b_0 = c_0 = 0$ である。これを解けばよい。

解

z 変換

ja.wikipedia.org
$\mathcal{Z}[x_n] = X(z)$ に対して、 $\mathcal{Z}[x_{n-1}] = z^{-1} X(z)$ であることを利用して、先の連立漸化式の辺々を z 変換すると、

\begin{cases} A(z) = z^{-1} A(z) + z^{-1} B(z) \\ B(z) = z^{-1} A(z) + z^{-1} C(z) \\ C(z) = z^{-1} B(z) + z^{-1} C(z) + \mathcal{Z}[n] \end{cases}

である。これを変形すると、

\begin{cases} \displaystyle A(z) = \frac{1}{z-1} B(z) \\ \displaystyle B(z) = \frac{z}{(z+1) (z-2)} \mathcal{Z}[n] = \frac{z^2}{(z-1)^2 (z+1) (z-2)} \\ \displaystyle C(z) = A(z) + \frac{z}{z-1} \mathcal{Z}[n] \end{cases}

が得られる。

逆 z 変換

$B(z)$ の式の最右辺を部分分数分解してみる。

\begin{align} B(z) &= \frac{z^2}{(z-1)^2 (z+1) (z-2)} \\ &= z \left[ \frac{z}{(z-1)^2 (z+1) (z-2)} \right] \\ &= z \left[ -\frac{1}{2} \frac{1}{(z-1)^2} -\frac{3}{4} \frac{1}{z-1} + \frac{1}{12}\frac{1}{z+1} + \frac{2}{3}\frac{1}{z-2} \right] \\ &= -\frac{1}{2} \frac{z}{(z-1)^2} -\frac{3}{4} \frac{z}{z-1} + \frac{1}{12}\frac{z}{z+1} + \frac{2}{3}\frac{z}{z-2}\ \\ \end{align}

この両辺を逆 z 変換する。

\begin{align} \mathcal{Z}^{-1}[B(z)] &= \mathcal{Z}^{-1} \left [-\frac{1}{2} \frac{z}{(z-1)^2} -\frac{3}{4} \frac{z}{z-1} + \frac{1}{12} \frac{z}{z+1} + \frac{2}{3} \frac{z}{z-2} \right] \\ &= -\frac{1}{2} n -\frac{3}{4} 1^n + \frac{1}{12} (-1)^n + \frac{2}{3} 2^n \end{align}

これが $b_n$ に等しいので、

\displaystyle b_n = \frac{1}{12} \left( -6n-9+(-1)^n+2^{n+3} \right)

となる。また、

\displaystyle A(z) = \frac{1}{z-1} B(z)

の両辺を逆 z 変換する。

$u(n)$ は単位ステップ関数とすると、

\displaystyle \frac{z}{z-1} = \mathcal{Z}[u(n)]

であり、

\displaystyle \frac{1}{z-1} = z^{-1} \mathcal{Z}[u(n)] = \mathcal{Z}[u(n-1)]

であることを考慮すると、畳み込みを直接計算することで、

\begin{align} a_n &= \mathcal{Z}^{-1} \left[ \frac{1}{z-1} B(z) \right] \\ &= \mathcal{Z}^{-1} \left[ \frac{1}{z-1} \right] * \mathcal{Z}^{-1}[B(z)] \\ &= u(n-1) * b_n \\ &= \sum_{m=0}^\infty u(m-1) b_{n-m} \\ &= \sum_{m=1}^{n-1} b_{n-m} \\ &= \sum_{k=1}^{n-1} b_k \\ &= \frac{1}{12} \sum_{k=1}^{n-1} \left( -6k-9+(-1)^k+2^{k+3} \right) \\ &= \frac{1}{24} \left( -6n^2-12n-15-(-1)^n+2^{n+4} \right) \end{align}

である。また、 $C(z)$ の逆変換について、

\begin{align} c_n &= a_n + \mathcal{Z}^{-1} \left[ \mathcal{Z}[u(n)] \mathcal{Z}[n]\right] \\ &= a_n + u(n)*n \\ &= a_n + \sum_{m=0}^\infty u(m) (n-m) u (n-m) \\ &= a_n + \sum_{k=1}^n k \\ &= a_n + \frac{1}{2}n(n+1) \\ &= \frac{1}{24} \left( -6n^2-12n-15-(-1)^n+2^{n+4} \right) + \frac{1}{2}n(n+1) \\ &= \frac{1}{24} \left( 6n^2-15-(-1)^n+2^{n+4} \right) \end{align}

となる。

以上をまとめると、

\begin{cases} \displaystyle a_n = \frac{1}{24} \left( -6n^2-12n-15-(-1)^n+2^{n+4} \right) \\ \displaystyle b_n = \frac{1}{12} \left( -6n-9+(-1)^n+2^{n+3} \right) \\ \displaystyle c_n = \frac{1}{24} \left( 6n^2-15-(-1)^n+2^{n+4} \right) \end{cases}

が解である。

別解

連立漸化式の行列表記

先の連立漸化式

\begin{cases} \displaystyle a_n = a_{n-1}+b_{n-1} \\ \displaystyle b_n = a_{n-1}+c_{n-1} \\ \displaystyle c_n = b_{n-1}+c_{n-1}+n \end{cases}

を行列を用いて表すことにすると、

\begin{bmatrix} a_n \\ b_n \\ c_n \end{bmatrix} = \begin{bmatrix} 1&1&0 \\ 1&0&1 \\ 0&1&1 \end{bmatrix} \begin{bmatrix} a_{n-1} \\ b_{n-1} \\ c_{n-1} \end{bmatrix} + \begin{bmatrix} 0 \\ 0 \\ n \end{bmatrix}

となる。ここで、

\boldsymbol{x}_n=\begin{bmatrix} a_n \\ b_n \\ c_n \end{bmatrix}, M=\begin{bmatrix} 1&1&0 \\ 1&0&1 \\ 0&1&1 \end{bmatrix}, \boldsymbol{y}_n=\begin{bmatrix} 0 \\ 0 \\ n \end{bmatrix}

とおくと、

\boldsymbol{x}_n = M \boldsymbol{x}_{n-1} + \boldsymbol{y}_n, \boldsymbol{x}_0 = \boldsymbol{0}

という漸化式になる。

漸化式の展開

\left\{\begin{align} \boldsymbol{x}_1 &= M \boldsymbol{x}_{0} + \boldsymbol{y}_1 \\ &= \boldsymbol{y}_1 \\ \boldsymbol{x}_2 &= M \boldsymbol{x}_{1} + \boldsymbol{y}_2 \\ &= M \boldsymbol{y}_1 + \boldsymbol{y}_2 \\ \boldsymbol{x}_3 &= M \boldsymbol{x}_{2} + \boldsymbol{y}_3 \\ &= M (M \boldsymbol{y}_1 + \boldsymbol{y}_2) + \boldsymbol{y}_3 \\ &= M^2 \boldsymbol{y}_1 + M \boldsymbol{y}_2 + \boldsymbol{y}_3 \\ &\vdots \\ \boldsymbol{x}_n &= M \boldsymbol{x}_{n-1} + \boldsymbol{y}_n \\ &= M (M \boldsymbol{x}_{n-2} + \boldsymbol{y}_{n-1}) + \boldsymbol{y}_n \\ &= M (M (M \boldsymbol{x}_{n-3} + \boldsymbol{y}_{n-2}) + \boldsymbol{y}_{n-1}) + \boldsymbol{y}_n \\ &= \cdots \\ &= M^{n-1} \boldsymbol{y}_{1} + M^{n-2} \boldsymbol{y}_{2} + M^2 \boldsymbol{y}_{n-2} + M \boldsymbol{y}_{n-1} + \boldsymbol{y}_n \\ &= \sum_{k=1}^n M^{n-k} \boldsymbol{y}_k \end{align} \right .

ここで、 $M^n$ の $k$ 列目を $\boldsymbol{m}^{(n)}_k$ と書くことにすると、

\begin{align} M^{n-k} \boldsymbol{y}_k &= \begin{bmatrix} \boldsymbol{m}^{(n-k)}_1 & \boldsymbol{m}^{(n-k)}_2 & \boldsymbol{m}^{(n-k)}_3 \end{bmatrix} \begin{bmatrix} 0 \\ 0 \\ k \end{bmatrix} \\ &= k \boldsymbol{m}^{(n-k)}_3 \end{align}

となるから、

\displaystyle \boldsymbol{x}_n = \sum_{k=1}^n k \boldsymbol{m}^{(n-k)}_3

となる。

対角化

$M$ を対角化することにより、 $M^n$ を求める。

例えば、

\displaystyle D=\begin{bmatrix} -1&0&0 \\ 0&1&0 \\ 0&0&2 \end{bmatrix}, P=\begin{bmatrix} 1&1&1 \\ -2&0&1 \\ -1&-1&1 \end{bmatrix}, P^{-1}= \frac{1}{6} \begin{bmatrix} 1&-2&1 \\ 3&0&-3 \\ 2&2&2 \end{bmatrix}

が得られ、

\begin{align} M^n &= P D^n P^{-1} \\ &= \frac{1}{6} \begin{bmatrix} 1&1&1 \\ -2&0&1 \\ -1&-1&1 \end{bmatrix} \begin{bmatrix} (-1)^n&0&0 \\ 0&1&0 \\ 0&0&2^n \end{bmatrix} \begin{bmatrix} 1&-2&1 \\ 3&0&-3 \\ 2&2&2 \end{bmatrix} \\ &=\frac{1}{6} \begin{bmatrix} \cdot&\cdot&-3+(-1)^n+2^{n+1} \\ \cdot&\cdot&-2(-1)^n+2^{n+1} \\ \cdot&\cdot&3+(-1)^n+2^{n+1} \end{bmatrix} \end{align}

となる。これにより、

\begin{align} \boldsymbol{x}_n &= \sum_{k=1}^n k \boldsymbol{m}^{(n-k)}_3 \\ &= \frac{1}{6} \sum_{k=1}^n k \begin{bmatrix} -3+(-1)^{n-k}+2^{n-k+1} \\ -2(-1)^{n-k}+2^{n-k+1} \\ 3+(-1)^{n-k}+2^{n-k+1} \end{bmatrix} \\ &= \frac{1}{6} \sum_{k=1}^n \begin{bmatrix} -3k+(-1)^n k (-1)^k+2^{n+1} k \left( \frac{1}{2} \right)^k \\ 2(-1)^{n+1} k (-1)^k +2^{n+1} k \left( \frac{1}{2} \right)^k \\ 3k+(-1)^n k (-1)^k+2^{n+1} k \left( \frac{1}{2} \right)^k \\ \end{bmatrix} \\ &= \frac{1}{6} \left( \begin{bmatrix} -3 \\ 0 \\ 3 \end{bmatrix} \sum_{k=1}^n k + \begin{bmatrix} (-1)^n \\ 2(-1)^{n+1} \\ (-1)^n \end{bmatrix} \sum_{k=1}^n k (-1)^k + \begin{bmatrix} 2^{n+1} \\ 2^{n+1} \\ 2^{n+1} \end{bmatrix} \sum_{k=1}^n k \left( \frac{1}{2} \right)^k \right) \end{align}

となる。

等差×等比タイプの和

$r \ne 1$ のとき、

\displaystyle S_n = \sum_{k=1}^n k r^k

とおくと、

\left\{\begin{align} S_n &= r + 2r^2 + 3r^3 + \cdots + n r^n \\ r S_n &= r^2 + 2r^3 + 3r^4 + \cdots + (n-1) r^n + n r^{n+1} \end{align} \right .

より、

\begin{align} (1-r) S_n &= r + r^2 + r^3 + \cdots + r^n - n r^{n+1} \\ &= \frac{r(1-r^n)}{1-r} - n r^{n+1} \end{align}

だから、

\displaystyle S_n = \frac{r(1-r^n)}{(1-r)^2} - \frac{n r^{n+1}}{1-r}

となる。

これにより、

\displaystyle \sum_{k=1}^n k(-1)^k = \frac{-1+(-1)^n}{4} - \frac{n (-1)^{n+1}}{2}

また、

\displaystyle \sum_{k=1}^n k \left(\frac{1}{2} \right)^k = 2 \left(1-\frac{1}{2^n} \right) - \frac{n}{2^n}

となる。

これらを利用して整理すると、

\displaystyle \boldsymbol{x}_n = \begin{bmatrix} \frac{1}{24} \left( -6n^2-12n-15-(-1)^n+2^{n+4} \right) \\ \frac{1}{12} \left( -6n-9+(-1)^n+2^{n+3} \right) \\ \frac{1}{24} \left( 6n^2-15-(-1)^n+2^{n+4} \right) \end{bmatrix}

という同様の解が得られる。

点数表

$n$	$a_n$	$b_n$	$c_n$
0	0	0	0
1	0	0	1
2	0	1	3
3	1	3	7
4	4	8	14
5	12	18	27
6	30	39	51
7	69	81	97
8	150	166	186
9	316	336	361
10	652	677	707
11	1329	1359	1395
12	2688	2724	2766
13	5412	5454	5503
14	10866	10915	10971
15	21781	21837	21901
16	43618	43682	43754
17	87300	87372	87453
18	174672	174753	174843
19	349425	349515	349615
20	698940	699040	699150
21	1397980	1398090	1398211
22	2796070	2796191	2796323
23	5592261	5592393	5592537