ハノイの塔と数学
原神やってたらハノイの塔を題材にした小噺が出てきたので、折角ならちょっと真面目に考えてみませんか？の回。数学は実験と仮説検証の繰り返しです。定番ではあるので調べるといくらでも転がってるんですけどね。そして中々数式を使い始めると解説が難しくなるジレンマ。
さて、ハノイの塔とはなんぞやという部分はwikipediaにでもぶん投げるとして、一般的な段数と手数の関係性をどうやって数えるのか、を考えてみます。
まずはn=1、すなわち塔が1段の場合（それは塔なのかはさておき）。この時は1手で済みますね。
それからn=2、すなわち塔が2段の場合。一段目を避難させてから二段目を移動して、移動した二段目に一段目を動かして3手。
それからは省略しますが、そうすると以下のような対応になります：
| 塔の段数 | 必要手数 |
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
これを見てピンとくる人は大分と数字に関するセンスが強い方です。ここでは愚直に考えていきましょう。
5段目の手数を考えてみます。しかし愚直に考えると大変なので、こうやって考えてみます：「5段目を動かせるようにするには上の4段を動かす必要がある。そして5段目を動かした後、また4段を5段目に動かす。そしてその4段を動かす手数は既に求めているのでは？」
そこで1～4段の様子を見てみましょう。
| 塔の段数 | 必要手数 | 必要手数の分解 |
| 1 | 1 | 1 |
| 2 | 3 | 1+1+1 |
| 3 | 7 | 3+1+3 |
| 4 | 15 | 7+1+7 |
どうやら予想は正しそうです。では一般化のために、n段の塔の手数をanと置いてみましょう。すると今回の式は$$a_1=1,\quad a_n=2a_{n-1}+1\quad (n>1)$$という風に書き表すことが出来ます。記号が出てきましたが、言っていることは変わりません。
さて、これを使えばn=5の時は$$a_5=2a_4+1=2(2a_3+1)+1=…$$とやれば計算できるんですが、面倒です。もうちょっといい方法が欲しいですね。ここで式に細工をします（なぜ細工するとうまくいくのかは数列と特性方程式の気持ちみたいなものがあるので割愛）。$$a_n=2a_{n-1}+1\quad (n>1)$$は$$a_n+1=2a_{n-1}+2\quad (n>1)$$と等しく、さらに$$a_n+1=2(a_{n-1}+1)\quad (n>1)$$となります。ここで$$b_n=a_n+1$$と置き換えてあげると、$$b_n=2b_{n-1}$$という式になります。これは前の数を二倍する数列ですから、$$b_n=2^n$$ということが分かります（これは指数法則と手計算からわかります）。翻って$$2^n=a_n+1$$ですから、移行して$$a_n=2^n-1$$が求まりました。確認してみましょう。
| 塔の段数 | 必要手数 | an=2n-1 |
| 1 | 1 | 2-1=1 |
| 2 | 3 | 4-1=3 |
| 3 | 7 | 8-1=7 |
| 4 | 15 | 16-1=15 |
ということで晴れて一般的な段数と手数の関係が求まりました。7段でも8段でも、すぐに答えられますね！重箱の隅はつつかないでいただけると助かります。
……みたいな話をしていたら、本当に手数を求められる選択肢（おまけに隠し実績付）だったのでちょっとびっくりしちゃいましたね。数学の小噺、ちょっとした計算テクなところもありますが、思考のお遊びが楽しかったりします。こういう面白さから数学の苦手意識とか、「どこで使うの」みたいなのが解消されると嬉しいのですが。
たまにはこんな話もいいよね、という回。またそのうちのんびり日記を書こうかな。