柱が３本のとき→４本のとき→ｎ本のときに一般化するのはもっと難しい問題になります．４本のときのハノイの塔について

　　一松信「整数と遊ぼう」日本評論社

の面白い記事がでていたので紹介します．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】柱を４本にしたときの手間

　あるとき，一松先生が熱心な中学生のグループから４本のときのハノイの塔について質問を受けたそうです．彼等が実験したところによると，その手間は

　　ｎ　　１　　２　　３　　４　　５　　６　　７　　８　　９　　10

　　ｂ　　１　　３　　５　　９　　13　　17　　25　　33　　41　　49

もちろん２^n−１に比べると桁違いに少ない回数です．

　差分をとってみると

　　２　　２　　４　　４　　４　　８　　８　　８　　８・・・

となって，その先は

　　１６　１６　１６　１６　１６　　３２　３２　３２　３２　３２　３２・・・（２^nがｎ＋１個続く）

　このことから，４本のときのハノイの塔でもやはり枚数ｎの増加とともなって指数関数的に手間が増加することがわかります．ただしその増加が３本のときのハノイの塔（２^n−１）と比べ，桁違いに遅いというわけです．柱をいくら増やしても板の枚数の増加とともに指数関数的に増加します．

　そして，記事の最後に一松先生は「ハノイの塔の柱を１本増やす」という発展問題を考えた中学生に改めて敬意を表していますが，確かにこうした発想をつまらないものとして芽を摘むのは最悪の教育でしょう．私も大学院生のとき，微量元素の分析に現れる曲線は何かと考えて，当時の教授から「つまらないことを考えるな」とどやしつけられたことがあり，そのことを思い出しました．その曲線とはいまにして思えばフォークト関数です．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝