ヨーキョクデイ

多趣味で器用貧乏なブログ(j は虚数単位)

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

f:id:electrolysis:20210102232450p:plain

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

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

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

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

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

これを下に図示する。

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

ja.wikipedia.org

問題

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

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

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

方針

  1.  A の 上部  n-1 段を柱  B に移動する
  2.  A に残った円盤  n を柱  C に移動する
  3.  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

所感

別解はロジックはエレガントなものの、いざやってみると手計算がつらすぎるので実用的ではない気がした。また、ハノイの塔が門松の竹柱と鏡餅のセットに似ている気がするので、縁起のよい正月遊びとして推していきたい。