前回の問題を一般化することにした。
e10s.hateblo.jp
問題・改
前回の問題と同様の最短手順で $n$ 段のハノイの塔を攻略するとき、
- $k$ 番目に小さい円盤を $k$ とする（最小の円盤が $1$、最大の円盤が $n$）
- 各手順について、円盤 $k$ の移動先の柱に点数 $f(k)$ が加算される
- 最初の段階で各柱の点数は $0$ である
という条件のもとで攻略終了時の柱 $A, B, C$ の点数をそれぞれ $a_n, b_n, c_n$ として、それらを求めよ。
つまり、加算される点数が $k$ ではなく、$f(k)$ になった。
方針・改
ステップ 2 では $C$ に $f(n)$ 点加算されることに注意。すなわち、$$
\begin{empheq}[left=\empheqlbrace]{align}
a_n &= a_{n-1}+b_{n-1} \\
b_n &= a_{n-1}+c_{n-1} \\
c_n &= b_{n-1}+c_{n-1}+f(n)
\end{empheq}
$$という連立漸化式を解く。前回と同様、$a_0 = b_0 = c_0 = 0$ である。
解・改
z 変換
先の連立漸化式の辺々を z 変換すると、$$
\begin{empheq}[left=\empheqlbrace]{align}
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}[f(n)]
\end{empheq}
$$である。これを変形すると、$$
\begin{empheq}[left=\empheqlbrace]{align}
A(z) &= \frac{1}{z-1} B(z) \\
B(z) &= \frac{z}{(z+1) (z-2)} \mathcal{Z}[f(n)] \\
C(z) &= A(z) + \frac{z}{z-1} \mathcal{Z}[f(n)]
\end{empheq}
$$が得られる。ここまでは前回と同様のアプローチ。さらに整理して、右辺を $z$ と $\mathcal{Z}[f(n)]$ で表すと、$$
\begin{empheq}[left=\empheqlbrace]{align}
A(z) &= \frac{z}{(z+1)(z-1)(z-2)} \mathcal{Z}[f(n)] \\
B(z) &= \frac{z}{(z+1)(z-2)} \mathcal{Z}[f(n)] \\
C(z) &= \qty[ \frac{z}{(z+1)(z-1)(z-2)} + \frac{z}{z-1} ] \mathcal{Z}[f(n)]
\end{empheq}
$$となる。部分分数分解しておくと、$$
\begin{empheq}[left=\empheqlbrace]{align}
A(z) &= \frac{1}{6} \qty[ \frac{z}{z+1} - \frac{3z}{z-1} + \frac{2z}{z-2} ] \mathcal{Z}[f(n)] \\
B(z) &= \frac{1}{3} \qty[ -\frac{z}{z+1} + \frac{z}{z-2} ] \mathcal{Z}[f(n)] \\
C(z) &= \frac{1}{6} \qty[ \frac{z}{z+1} + \frac{3z}{z-1} + \frac{2z}{z-2} ] \mathcal{Z}[f(n)]
\end{empheq}
$$が得られる。
逆 z 変換
$\mathcal{Z}[f(n)]$ の係数に注目したい。
$A(z), B(z), C(z)$ それぞれについて $\mathcal{Z}[f(n)]$ の係数の逆 z 変換を $a'_n, b'_n, c'_n$ とすると、$$
\begin{empheq}[left=\empheqlbrace]{align}
a'_n &= \frac{1}{6} \qty[ (-1)^n - 3 + 2^{n+1} ] = \frac{1}{6} [ 2^{n+1} - (-1)^{n+1} - 3 ] \\
b'_n &= \frac{1}{3} \qty[ -(-1)^n+ 2^n ] = \frac{1}{3} [ 2^n - (-1)^n ] \\
c'_n &= \frac{1}{6} \qty[ (-1)^n + 3 + 2^{n+1} ] = \frac{1}{6} [ 2^{n+1} - (-1)^{n+1} + 3 ]
\end{empheq}$$
Jacobsthal 数
Jacobsthal 数 $J_n$ は以下で表される数列らしい。
$$J_n = \frac{1}{3} [ 2^n - (-1)^n ]$$
まさに $b'_n = J_n$ である。さらに $a'_n, c'_n$ も $J_n$ で表すことができて、$$
\begin{empheq}[left=\empheqlbrace]{align}
a'_n &= \frac{1}{2} (J_{n+1} - 1) \\
b'_n &= J_n \\
c'_n &= \frac{1}{2} (J_{n+1} + 1)
\end{empheq}$$となる。
続・逆 z 変換
これまでの結果から、$$
\begin{empheq}[left=\empheqlbrace]{align}
A(z) &= \mathcal{Z}[a'_n] \mathcal{Z}[f(n)] \\
B(z) &= \mathcal{Z}[b'_n] \mathcal{Z}[f(n)] \\
C(z) &= \mathcal{Z}[c'_n] \mathcal{Z}[f(n)]
\end{empheq}
$$の辺々を逆 z 変換することで、$$
\begin{empheq}[left=\empheqlbrace]{align}
a_n &= a'_n * f(n) = \frac{1}{2} (J_{n+1} - 1) * f(n) \\
b_n &= b'_n * f(n) = J_n * f(n) \\
c_n &= c'_n * f(n) = \frac{1}{2} (J_{n+1} + 1) * f(n)
\end{empheq}$$となることがわかる。
例題
$n$ 段のハノイの塔の最短手順が $2^n-1$ 回であることを確かめよ。
解
$$f(n) = u(n-1) = \begin{cases}
1 & (n \geq 1) \\
0 & (otherwise) \\
\end{cases}
$$としたときの、$a_n+b_n+c_n$ を求めればよい。
$$\begin{align}a_n+b_n+c_n
&= \frac{1}{2} (J_{n+1} - 1) * u(n-1) + J_n * u(n-1) + \frac{1}{2} (J_{n+1} + 1) * u(n-1) \\
&= (J_{n+1} + J_n) * u(n-1) \\
&= 2^n * u(n-1) \\
&= \sum_{m=0}^\infty 2^m u(n-m-1) \\
&= \sum_{m=0}^{n-1} 2^m \\
&= 2^n-1
\end{align}$$
おわり。
所感
前回よりも sophisticated な理論展開ができた気がする。
