ハノイの塔の一般公式は、ｎ枚の円盤のとき、２^ｎー１で与えられますが、棒の本数を４本
にしたときにも簡単な公式ができそうです。１，3，5，9，13，17，・・・から一般公式ができそう
ですが、原理的な面から考えないといけないので苦戦中です。どうでしょうか？
（→　類題「円板の移動」）


　カルピスさんからのコメントです。（平成２７年３月２０日付け）

　パズルの中でも、「公式」を考えてしまうのは、数学を専門とする人の特有の癖みたいなも
のなのでしょうか。私は、ハノイの塔が好きですが、最小手数の公式があることさえ知りませ
んでした。


　ＧＡＩ さんからのコメントです。（平成２７年３月２０日付け）

　「A007664」を参考にしてみて下さい。


　ＤＣＯさんからのコメントです。（平成２７年３月２１日付け）

　まだ、まとまりきっていないのですが、棒の本数を４本にしたときの最小手順a[n]は、

　m(m+1)≦n-1<(m+1)(m+2)　となる自然数mを求めて、a[n]=(n-（m²+m+2)/2)・2^m+1+1

を計算すれば出てくる気がします。

n=1のとき、m=-1 で、　a[1]=1
n=2のとき、m=0 で、　a[2]=3
n=3のとき、m=0 で、　a[3]=5
n=4のとき、m=1 で、　a[4]=9
n=5のとき、m=1 で、　a[5]=13
n=6のとき、m=1 で、　a[6]=17
n=7のとき、m=2 で、　a[7]=25
・・・・・

　これであってるでしょうか・・・？おそらくもっと簡単に表せると思いますが．．．。
根拠はないわけではないのですが、短時間では僕の能力では説明できそうにないです…。


　ＧＡＩ さんが検証されました。（平成２７年３月２１日付け）


　ＤＣＯさんからのコメントです。（平成２７年３月２２日付け）

　失礼いたしました。mの決定法を間違えていたようです。m(m+1)/2<n≦(m+1)(m+2)/2 を
満たすmを定め、a[n]=(n-(m²-m+2)/2)・2^m +1　を計算すれば出てくる模様です。
Excelによる計算結果　・・・　さしあたり30項までは一致している様子。

　ちなみに漸化式ですが、無理やり書こうとすると、

　　　a[n+2]=1 + 2 * min[1≦k≦n](a[k]+b[n-k+1])

但し、b[n]は棒が3本の時のハノイの塔の最小手数で、b[n]=2ⁿ-1

という形になりました。(工夫次第でもっと簡単に表せると思います)

　たとえば、　a[7]=1+2*min[k=1,2,3,4,5](a[k]+b[5-k+1])

a[1]+b[5]=1+31=32　、a[2]+b[4]=3+15=18　、a[3]+b[3]=5+7=12　、a[4]+b[2]=9+3=12
a[5]+b[1]=13+1=14

より、　a[7]=1+2*12=25.


　ＧＡＩ さんからのコメントです。（平成２７年３月２２日付け）

　この式で処理したら、確かに、ｎ≦100　までは正確に表示されました。


（コメント）　ＤＣＯさんは、a[7]=25、ＧＡＩさんは、a[7]=21、「A007664」は、a[7]=25　と齟齬が
　　　　　　あったので、計算してみた。（平成２７年３月２１日付け）

　１２３４５６７のうち、まず４本の棒を使って１２３を他所に移す場合の数は、a[3]=5（通り）
次に、４５６７を１２３がある棒以外の３本の棒で他所に移す場合の数は、2⁴−１=15（通り）
最後に、４本の棒を使って１２３を４５６７の棒に移す場合の数は、a[3]=5（通り）

　以上から、求める場合の数は、　５＋１５＋５＝２５（通り）　となり、　a[7]=25　が正しい。

　操作の手順を踏まえて、漸化式　a[1]=1、a[2]=3、a[n+2]=2a[n]+3　が得られる。

　Excel さんにお世話になれば、すべてのa[n]が得られるだろう。ただ、この漸化式から得られ
る a[n] は最短手数を表していないという現実がある。

　実際に、ｎ＝７のときの最短手数は、25手なのだが、漸化式から得られる a[7] は、29手である。

　やはり、一つの漸化式で全ての現象を説明することは困難なのだろうか？

　上記の漸化式は３項間漸化式なので、その解法により、一般項が簡単な計算で求められる。
その手数以内で確実にできるという上限を示しているという点で、それはそれで存在意義はある
だろう。

　　a[n]=（3+2)^n-2+（3-2)(-)^n-2-3

（漸化式の解法）　a[n+3]=2a[n+1]+3　、a[n+2]=2a[n]+3　を辺々引いて、

　　　a[n+3]-a[n+2]=2（a[n+1]-a[n]）

b[n]=a[n+1]-a[n]　とおくと、　b[1]=a[2]-a[1]=3-1=2、b[2]=a[3]-a[2]=5-3=2　で、b[n+2]=2b[n]

よって、　b[n+2]-b[n+1]=（−）（b[n+1]-b[n]）　より、

　　　　　b[n+1]-b[n]=（−）^n-1（b[2]-b[1]）=（−）^n-1（2-2）

同様にして、　b[n+1]+b[n]=（）^n-1（b[2]+b[1]）=（）^n-1（2+2）　なので、

　　　　2b[n]=（）^n-1（2+2）-（−）^n-1（2-2）

すなわち、　b[n]=（）^n-2（1+）+（−）^n-2（1-）

　階差数列の公式により、ｎ≧2 のとき、

　a[n]=a[1]+Σ_k=1^n-1 b[k]

　　　=1+Σ_k=1^n-1 （（）^k-2（1+）+（−）^k-2（1-））

　　　=1+（3+2）（）^n-2-（3+2）/+（3-2）/+（3-2）（−）^n-2

　　　=（3+2）（）^n-2+（3-2）（−）^n-2-3

　この式は、n=1 のときも成り立つ。

　よって、一般項は、　a[n]=（3+2)^n-2+（3-2)(-)^n-2-3　　（終）


　ＫＳさんからのコメントです。（平成２７年３月２３日付け）

　おかげさまで、皆様のご協力のもと、Ａ(ｎ＋１)＝Ａ(ｎ)＋２^ｋ　の形になっていることがわか
ります。但し、ｎ(ｎ＋１)＜＝２ｋ＜＝ｎ(ｎ＋３)で与えられる。

　今までの結果が、三十まで可能なことがわかりましたが、それが本当に最小手数であるこ
とはまだ、つかめていません。帰納法で証明できるでしょうか？


　ＤＣＯさんからのコメントです。（平成２７年３月２３日付け）

　そうですね。私が少し前に示した漸化式

　a[n+2]=1 + 2 * min[1≦k≦n](a[k]+b[n-k+1])

　　　但し，b[n]は棒が3本の時のハノイの塔の最小手数で，b[n]=2ⁿ-1

が最小手数になることを示し、その一般項がその式で与えられることを示せばよいのだと思
います。というよりも、私は最小手数の条件から上の漸化式を導きだし、その漸化式を解い
て一般項を出しました。


（追記）　平成２７年５月２１日付け

　２０１５年６月号の数学セミナー（日本評論社）に、ハノイの塔問題の類題が「エレガントな
解答をもとむ」として出題されている。出題者は、横浜国立大学の根上生也氏。

　一番上から黒と白で交互に色分けされたｎ枚の円板が積み上げられたハノイの塔がある。
同じ色の円板が連続して上下に重なることなく、すべての円板を棒１から棒２に移動できるこ
とを示せ。ただし、次の条件に従うものとする。

（条件）　１．１回に１枚、他の棒に移動
　　　　　２．小さい円板の上に大きい円板を乗せてはならない

　一般の「ｎ」では難しそうなので、具体的に考えてみた。

　以下で、円板は順に上から　Ｂ1Ｗ2Ｂ3Ｗ4Ｂ5Ｗ6Ｂ7Ｗ8Ｂ9・・・・・　と並んでいるものとする。

（１）　ｎ＝１　のときは、明らかに１回の操作で移動は可能。

（２）　ｎ＝２　のとき、

（３）　ｎ＝３　のとき、

（４）　ｎ＝４　のとき、

　　　棒１にある４枚の円板を棒２に移動させるには、１５回の操作が必要

　ここまでは通常のハノイの塔と同じ手順数で、　２^ｎ−１（回）　が成り立つ。

　さて、根上先生の問題は、どこから違ってくるのだろう？

　さらに、実験を続けよう。

（５）　ｎ＝５　のとき、

　　　棒１にある５枚の円板を棒２に移動させるには、３１回の操作が必要

　問題の趣旨が「すべての円板を棒１から棒２に移動できることを示せ。」だから、示し方が
違ったかな？

　ｎ枚の円板のうち、下２枚を除いたｎ−２枚は、下２枚の上の円板とｎ−２枚の最下位の円
板の色が異なるので、３本の柱を自由に使って移動させることができる。

　ｎを偶数・奇数に分けて考えれば、必ず移動出来そう！