『第三の理』のホームページ

第三の理／補足◎

チャレンジ問題

　本編中で読者のチャレンジ問題として残しておいた問題の解答を記しておこう．実際にそれにチャレンジした人は自分の解答とそれを比較してほしい．

定理1 　与えられた手数において，移動する板の番号は，その手数の 2 進数表現を末尾から数えていき，初めて 1 が現れたところの桁数と一致する．

証明　与えられた手数を m とし，移動する板の番号を l とする． m の 2 進法表現の末尾を 1 桁目と数えることにすると， 1 桁目から l-1 桁までが 0 であり， l 桁目が 1 であることを示せばよい．

　本編で示したアルゴリズムに従えば， m の 2 進法表現の n 桁目から始めて 1 つずつビットを右に見ていき， l 桁目になった時点で板 l の位置が決定する． m-1 手目と m 手目のハノイの塔の状態では板 l の位置のみが異なり，同じ手順で板の位置が決定されるのだから， m-1 の 2 進法表現の l 桁目よりも左のビットはすべて m の 2 進法表現と同じになっているはずである．さらに，板 l の位置が異なるのだから， l 桁目も異ならなければならない．つまり， m-1 < m なのだから， m-1 の 2 進法表現では 0 ， m の 2 進法表現では 1 にならざるをえない．また， m-1 に 1 を足すと m になるのだから， l 桁目の 0 から 1 への変化は 1 桁目から繰り上がりが繰り返した結果だということになる．したがって， m-1 と m の 2 進法表現は，例えば次のようになっている．

: m-1 = 101100111111
: m = 101101000000

ただし， 0 と1 がそれぞれの l 桁目である． ■　

定理2 　板 l は， 2^l-1 手目に移動した後， 2^l 手目ごとに移動する．

解答　定理1からわかるように， m の 2 進数表現の l 桁目が 0 から 1 に変わるたびに，板 l が移動する．その l 桁目は 2^l-1 に対応する桁だから，初回は 1 から数えて 2^l-1 手目で 0 が 1 に変わる．次は，

のように， 2^l-1 手後にいったん l 桁目の 1 が 0 に戻り，さらに 2^l-1 手経過したときにその 0 が 1 に変わる．つまり，最初の板 l の移動の後から数えて 2^l-1 + 2^l-1 = 2^l 手目で次の移動が起こる．以後，このパターンが繰り返されるので，初回以外は 2^l 手目ごとに板 l の移動が起こる．■　

定理3 　棒 1 ，棒 2 ，棒 3 を時計回りに三角形状に並べたとすると，どの板も時計回り，または反時計回りに， 1 つずつ棒を移動する．特に， n が偶数ならば，偶数番の板は時計回り，奇数番の板は反時計回りに移動し， n が奇数ならば，それぞれ逆回りをする．

解答　まず，板 n の動きだけに注目すると，それは 1 から 2 に移動する．つまり，時計回りに 1 つだけ移動する．その間に板 n-1 は棒 3 に待避させられた後に棒 2 に移動する．つまり，反時計回りに 2 つ移動して，板 n の上に乗る．板 n を無視すれば，この手順は n-1 段のハノイの塔を 1 から 3 へ， 3 から 2 へと移動したことに他ならない．

　したがって，上と同様に考えれば，板 n-1 が反時計回りに 1 つ進む間に，板 n-2 は時計回りに 2 つ進んで板 n-1 の上に乗る．さらに，この関係が繰り返されて，板 l が時計回り（反時計回り）に 1 つ進む間に，板 l-1 が反時計回り（時計回り）に 2 つ進んで板 l の上に乗ることがわかるだろう．つまり，板は 1 つおきに同じ方向に回転する．特に，板の番号の偶奇性が n と同じならば時計回り，そうでなければ反時計回りとなる． ■　

　このように考えていくと，ハノイの塔の移動過程のしくみがかなり具体的な形で見えてくる．さらに， 2 進数と 2 進木の関係を考察すると，以下のような公式に至る．ただし， [b_nb_n-1 … b₁] は n 桁の 2 進数を表すものとする．例えば，

である．また，式表現を簡単にするために，棒の番号 1 , 2 , 3 を順に 0 , 1 , 2 に改めた．

定理4 　ハノイの塔の m 手目の状態におけて，板 i が刺さっている棒の番号（ 0 , 1 , 2 ）を x_i とおくと，

^n-i

_n-1

_i+1

となる．ただし， m = [b_nb_n-1 … b₁] である．

　この定理はハノイの塔の状態をずばりと表現しているように見えるが，段数が大きくなると，人力で実行するにはかなり手間の掛かる公式である．

　それと比べると，次の漸化式を使えば，大きな値を扱うこともなく，手数の 2 進数表現だけからハノイの塔の状態を簡便に決定できてしまう．

定理5 　上と同じ記号を使うと，次の漸化式が成り立つ．ただし，便宜的に x_n+1 = 0 , b_n+1 = 0 とおき， i は n から 1 ずつ小さくしていくものとする．

_i+1

^n-i

_i+1

　逆に， x₁, … x_n に適当に 0 , 1 , 2 を割り振ったときに，それはハノイの塔の何手目の状態に対応するかという問題も，この漸化式を用いて簡単に解ける．つまり，上の漸化式を b₁, …, b_n に関する方程式だと思えばよいわけだ．もちろん，どの b_i も 2 進数表現に現れる数なのだから， 0 か 1 でなければならない．ということは，その方程式の解の中に 1 つでも 2 が含まれれば，それに対応する状態はハノイの塔の移動過程には現れないことになる．

　実は，この漸化式は本編で考案したアルゴリズムと実質的に同じ働きをする．ここではその対応関係を説明しないが，それを理解するには，あなたと第三の理のより強力な結合が必要だろう…．

　いずれにせよ，定理 4 と定理 5 の証明は，読者へのさらなるチャレンジ問題として残しておこう．

negami@edhs.ynu.ac.jp [1998/5/1]