ヨーキョクデイ

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

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

前回の問題を一般化することにした。
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{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}+f(n)
\end{cases}

という連立漸化式を解く。前回と同様、 a_0 = b_0 = c_0 = 0 である。

解・改

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}[f(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}[f(n)] \\
\displaystyle C(z) = A(z) + \frac{z}{z-1} \mathcal{Z}[f(n)]
\end{cases}

が得られる。ここまでは前回と同様のアプローチ。さらに整理して、右辺を  z \mathcal{Z}[f(n)] で表すと、

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

となる。部分分数分解しておくと、

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

が得られる。

逆 z 変換

 \mathcal{Z}[f(n)] の係数に注目したい。

 A(z), B(z), C(z) それぞれについて  \mathcal{Z}[f(n)] の係数の逆 z 変換を  a'_n, b'_n, c'_n とすると、

 \begin{cases}
\displaystyle a'_n = \frac{1}{6} \left[ (-1)^n - 3 + 2^{n+1} \right] = \frac{1}{6} \left[ 2^{n+1} - (-1)^{n+1} - 3 \right] \\
\displaystyle b'_n = \frac{1}{3} \left[ -(-1)^n+ 2^n \right] = \frac{1}{3} \left[ 2^n - (-1)^n \right] \\
\displaystyle c'_n = \frac{1}{6} \left[ (-1)^n + 3 + 2^{n+1} \right] = \frac{1}{6} \left[ 2^{n+1} - (-1)^{n+1} + 3 \right]
\end{cases}

Jacobsthal 数

Jacobsthal 数  J_n は以下で表される数列らしい。

\displaystyle  J_n = \frac{1}{3} \left[ 2^n - (-1)^n \right]

en.wikipedia.org
まさに  b'_n = J_n である。さらに  a'_n, c'_n J_n で表すことができて、

 \begin{cases}
\displaystyle a'_n = \frac{1}{2} (J_{n+1} - 1) \\
\displaystyle b'_n = J_n \\
\displaystyle c'_n = \frac{1}{2} (J_{n+1} + 1)
\end{cases}

となる。

続・逆 z 変換

これまでの結果から、

 \begin{cases}
\displaystyle A(z) = \mathcal{Z}[a'_n] \mathcal{Z}[f(n)] \\
\displaystyle B(z) = \mathcal{Z}[b'_n] \mathcal{Z}[f(n)] \\
\displaystyle C(z) = \mathcal{Z}[c'_n] \mathcal{Z}[f(n)]
\end{cases}

の辺々を逆 z 変換することで、

 \begin{cases}
\displaystyle a_n = a'_n * f(n) = \frac{1}{2} (J_{n+1} - 1) * f(n) \\
\displaystyle b_n =b'_n * f(n) = J_n * f(n) \\
\displaystyle c_n = c'_n * f(n) = \frac{1}{2} (J_{n+1} + 1) * f(n)
\end{cases}

となることがわかる。

例題

 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 な理論展開ができた気がする。