ちょいとパズルにも数学的帰納法を

2-1．ハノイの塔とは何ぞや？

図 2-1

　ここに３本の杭が立っている。
　そのうちの一本、左端の杭に円盤がはまっている。
　その円盤たちは下から大きい順に重なっていて、外観は円錐形のように見える。

　ここから、この円盤たちを右端の杭にすべて移し替えたい。
　しかし、次のルールを守らねばならない。

• 円盤は一度に１枚しか動かしてはならない。
• 小さい円盤の上に大きな円盤を載せてはならない。
• 円盤は必ずどれかの杭にはめなければならない。

　さて、どうやって全部移し替えよう……？

　これが『ハノイの塔』というパズルです。
　これは円盤の枚数が多くなるほど手数がバケモノじみていくという驚異のパズルでして、そのあたりの話も最後にチョロっとしてみようかなと思います。
　最初から一般的な話をしてもわかりにくいから、まずは円盤２枚の小さな塔から話を始めましょう。

2-2．小さな塔で考えよう

　まず最初に、ちょいと用語を作っておきます。
　円盤 \(n\) 枚の塔を \(\boldsymbol{n}\) 枚塔 と簡単に言うことにしましょう。
　『ハノイの塔』とは、左端にある \(n\) 枚塔を右端にそっくり移し替えるパズルです。

　まずは、円盤２〜４枚の小さな塔で考えてみましょう。
　塔を左端から右端へ移し替えるのに何手かかるかな？

図 2-2

　まずは２枚塔。円盤２枚の小さな塔です。
　左端の塔を右端に移し替えるにはどうするか？
　次の手順を踏めばＯＫです。

1. 小円盤を真ん中に移す。
2. 大円盤を右端に移す。
3. 小円盤を右端に移す。

　はい、できあがり。
　３手でしたね。
　ちなみに、この手数は \(\boldsymbol{3=2^2-1}\) と表せます。
　\(2\) の右肩に乗っている小さな数字「\(2\)」、２枚塔の「２」と同じですね。

　２枚塔は簡単でしたね。
　では、３枚塔だとどうでしょう？

図 2-3

　３枚の円盤を小さい方からＡ, Ｂ, Ｃとしましょう。
　次の手順で移転完了です。

1. Ａを右端に移す。
2. Ｂを真ん中に移す。
3. Ａを真ん中に移す。
4. Ｃを右端に移す。
5. Ａを左端に移す。
6. Ｂを右端に移す。
7. Ａを右端に移す。

　今度は７手でした。
　ちなみに、この手数は \(\boldsymbol{7=2^3-1}\) と表せます。
　\(2\) の右肩に乗っている小さな数字「\(3\)」、３枚塔の「３」と同じですね。

図 2-4

　実は、円盤が１枚多くなった時、うまい考え方があるんです。
　円盤を「一番下」と「それ以外」の２つに分けてしまう。
　そうすることで、塔の移転を簡潔に捉えることができます。
　例えば、前図2-3 の７手はこう捉えましょう。

1. Ａ, Ｂの２枚を真ん中に退避させる。（３手）
2. Ｃを右端に移す。（１手）
3. 退避させた２枚を右端に移す。（３手）

　３枚塔を移し替えるためには、どこかで円盤Ｃを右端に動かす必要が出てきます。
　だけど、最も大きい円盤を他の円盤の上に載せてはいけないから、右端は完全に空けておかなきゃいけない。そのため、Ｃ以外の円盤（つまりＡとＢ）をすべて真ん中に退避させなきゃいけません。
　その「２枚Ａ, Ｂの退避」、実は「２枚塔の移し替え」と本質的には同じ作業なんです。

　ということは、２枚塔の知識があれば３枚塔の理解は簡単！
　２枚塔の３手を一括りにして上記の a. b. c. へと簡略化しちゃえばいいんです。

　４枚塔も理屈はまったく同じです。
　３枚塔の知識を利用して、こういう手順をたどりましょう！

1. 上３枚の円盤を真ん中に退避させる。（７手）
2. 一番下の円盤を右端に移す。（１手）
3. 退避させた３枚を右端に移す。（７手）

　４枚塔は 7＋1＋7＝15手です。
　ちなみに、この「15」は \(\boldsymbol{15=2^4-1}\) と表せます。
　\(2\) の右肩に乗っている小さな数字「\(4\)」、４枚塔の「４」と同じですね。

2-3．一般には何手かかるのか

　なんとな〜く、一般（ \(n\) 枚塔）の場合の手数が見えてきたかもしれませんね。
　もぅ正解を言っちゃいましょう。\(n\) 枚塔の場合は \((2^n-1)\) 手かかります。
　これを数学的帰納法で証明してみましょう！

　まずは、数学的帰納法のおさらい。
　証明すべきは次の２つでした。

【Ａ】

\(n=1\) のとき成り立つ。

【Ｂ】

\(n=k\) のとき成り立つなら、\(n=k+1\) のときも成り立つ。

　これをハノイの塔に適用しましょう。
　「 \(n\) 枚塔の移転に \((2^n-1\)) 手かかる」を数学的帰納法で証明したいなら、次の２つを証明しなきゃいけません。

【Ａ】

１枚塔の移転に \((2^1-1)\) 手かかる。

【Ｂ】

\(k\) 枚塔の移転に \((2^k-1)\) 手かかるなら、\((k+1)\) 枚塔は \((2^{k+1}-1)\) 手かかる。

　では、証明していきましょう！

　まず、【Ａ】は簡単ですね。
　１枚塔の移転は１手で済みます。
　そして、\(1=2^1-1\) です。
　よって【Ａ】は成り立ちます。

　【Ｂ】はどうでしょう？
　「 \(k\) 枚塔の移転に \((2^k-1)\) 手かかる」と仮定して話を進めてみます。

図 2-5

　そういえば、２枚塔の知識で３枚塔の手数がわかりましたよね。
　３枚塔の知識で４枚塔の手数がわかった。
　……どうやら \(k\) 枚塔の知識で \((k+1)\) 枚塔の手数がわかりそうな気がする！

1. 上ｋ枚の円盤を真ん中に退避。（仮定より \(2^k-1\) 手）
2. 一番下の円盤を右端に移す。（１手）
3. 退避させたｋ枚を右端に移す。（仮定より \(2^k-1\) 手）

　これで \((k+1)\) 枚塔の移転が完了します。
　さぁ、その合計手数は……？

\begin{align} \text{(手数)} &= (2^k-1) + 1 + (2^k-1) \\ &= 2^k + 2^k - 1 + 1 - 1 \\ &= 2\cdot2^k - 1 \\ &= 2^{k+1} - 1 \end{align}

　おぉ〜ピッタリ！
　見事、\((k+1)\) 枚塔は \((2^{k+1}-1)\) 手かかるということがわかったのです。
　これで【Ｂ】も証明された！

　さぁ、結論です。
　ハノイの塔について、数学的帰納法によりこれが証明されました。

• ハノイの塔において、左端の \(n\) 枚塔を右端に移転させるのに \((2^n-1)\) 手かかる。

2-4．この世が終わる !?

　最後に、ちょいと軽い小話をご紹介。

　ハノイの塔がこの世に生まれたのは1883年です。
　フランスの数学者・リュカによって子供向けのオモチャとして発明されました。
　リュカはイタリアの数学者・カルダーノの著書『微細なる事物について』(1550年) から着想を得て「ハノイの塔」を発明したのだそう。
　その書物にはこんな一節があります。

　この世が終わるだなんて、まぁ大げさな😅
　いや、まぁたしかに64枚は多いけどさ😅
　しかし、この後、これは大げさな話ではなかったのだとわかります。
　実は、この世が終わるどころの話ではないんです。

　神命通りに円盤の移し替えを終えるには、僧たちは円盤を \((2^{64}-1)\) 回も移動させなければなりません。
　はて、\(2^{64}-1\) ってどれほどの数なんだ？

\(2^{64}-1 = 18446744073709551615\)

　うわ〜😅
　1844京です😅
　どんくらいの数だかまったく想像つかねぇよ😅

　いやぁすごい数だ。
　円盤を１秒に１回動かしたとしても1844京秒かかるんだもの。
　この1844京秒、どれくらいの長さなんでしょう？
　「１年＝365日＝31,536,000秒」と閏年を無視して、およその年数に換算してみましょうか。

\(18446744073709551615 \div 31536000 = \text{約}\,584942417355\)

　5849億年😅
　そりゃぁこの世が終わるのも当然だ😅

　ちなみに、宇宙の誕生・ビッグバンはおよそ138億年前に起こったとされています。
　宇宙の歴史って、たった138億年しかないんだぜ！
　仮にビッグバンと同時に僧たちが円盤を動かしてきたとしても、皆さんが当ページを見ている時点では神命の 2.3％ほどしか進んでいないのです。
　64枚の移し替えがどれほど想像を絶する苦行なのか。形容する言葉はこの世にはなさそうだ。

　僧たちが神命を遂げた時、この世が終わることはおそらく間違いない。
　いや、「終わる」ではなく「終わっている」が正しいか。
　地球や太陽なんてとうの昔に宇宙の藻屑だ。宇宙そのものが終わっていても不思議ではないのです。

3-1．穴あきチェス盤の問題

図 3-1

　８×８マスのチェス盤がある。
　この盤には64マスあるが、そのうち１マスに穴が空いている。
　そして、このチェス盤と一緒にブロックがたくさん用意されている。
　そのブロックはＬ字型をしていて、ちょうどチェス盤の３マスを覆うことができる。

　今、このチェス盤にＬ字ブロックを敷き詰めたい。
　ただし、次のルールを守らねばならない。

• ブロックはマスに沿って置かなければならない。
• ブロックを重ねてはならない。
• ブロックで穴を塞いではならない。

　要は「穴以外の63マスをＬ字ブロック21個で覆い尽くせるだろうか？」という問題です。
　果たして、それは可能なんだろうか？
　それとも、穴の位置によっては不可能だったりするんだろうか？
　いや、どこに穴があっても可能なんだろうか……？

　もぅ正解を言っちゃいますが、実は、８×８盤面のどこに穴があってもＬ字ブロックを敷き詰めることは可能です。
　ただ、ここではさらに話を広げます。
　次のことを考えてみたい！

　「一辺が \(2^n\) マス」と話が広がりました。
　２×２, ４×４, ８×８, 16×16, 32×32, ……といった諸々のサイズの穴あきチェス盤を考えるわけですね。
　どのサイズでも、かつ、どこに穴があってもＬ字ブロックを敷き詰めることは可能なんだろうか？
　それを考察していきます。
　最初から一般的な話をしてもわかりにくいから、まずは小さなサイズから話を始めましょう。

3-2．小さなチェス盤で考えよう

図 3-2

　２×２サイズは言うまでもないので、４×４サイズから話をします。
　穴の空いた４×４チェス盤、Ｌ字ブロックでどう埋めればいいのか？
　次の手順を踏めばうまくいきます。

1. 盤面を２×２サイズの小領域に４等分する。
2. 穴のない３領域に跨がるようにＬ字ブロックを置く。
3. あとはブロックで埋めるだけ。

　実は、手順 2. が大きなカギです。
　これ１つだけで、もぅ４×４サイズは完全解決したも同然なんです。
　なぜかと言うと、こうなったから。

手順 2. で置いたブロックを穴だとみなすと、小領域はすべて「穴の空いた２×２チェス盤」になった。

　まるで 図3-2 の青色ブロックが穴の役割を果たしたかのよう。
　そのおかげで、あとは小領域それぞれの問題に帰着するんです。

　実は、穴がどの位置にあろうとも、上記 1.〜3. で済みます。
　よって、４×４の場合、穴の位置にかかわらずＬ字ブロックを敷き詰められるんです。

　４×４サイズは肯定的に解決できましたね。
　では、８×８サイズはどうでしょう？

図 3-3

　８×８の場合はこうしましょう。

1. 盤面を４×４サイズの小領域に４等分する。
2. 穴のない３領域に跨がるようにＬ字ブロックを置く。
3. あとはブロックで埋めるだけ。

　ここでも手順 2. は大きなカギです。
　これ１つだけで、８×８サイズも攻略完了です。
　なぜかと言うと、こうなったから。

手順 2. で置いたブロックを穴だとみなすと、小領域はすべて「穴の空いた４×４チェス盤」になった。

　４×４サイズについては 前図3-2 で説明したばかり。
　つまり、４つの小領域はすべてＬ字ブロックで埋めることができる。
　結果、８×８の場合も穴の位置にかかわらずＬ字ブロックを敷き詰められるんです。

　８×８サイズも肯定的に解決できましたね。

　さて、図3-2 と 図3-3 の解説を読んで、もぅ気付いた方々は多いかも知れませんね。
　そうです。話がまったく同じなんです。
　４等分して、Ｌ字ブロックが跨いで、残りを埋める。
　これだけ。

　ということは、16×16サイズも同じく解決できそうですね。

1. 盤面を８×８サイズの小領域に４等分する。
2. 穴のない３領域に跨がるようにＬ字ブロックを置く。
3. あとはブロックで埋めるだけ。

　８×８サイズについては 図3-3 で説明したばかり。
　これで16×16サイズもＯＫです！

3-3．一般のチェス盤の場合

　なんとな〜く、一般（サイズ \(2^n\)）の場合も攻略方法が見えてきたかもしれませんね。
　もぅ結論を言いましょう。どのサイズであっても、かつ、どこに穴があっても肯定的に解決できます。
　それを数学的帰納法で証明してみましょう！

　再び数学的帰納法のおさらい。
　証明すべきは次の２つでした。

【Ａ】

\(n=1\) のとき成り立つ。

【Ｂ】

\(n=k\) のとき成り立つなら、\(n=k+1\) のときも成り立つ。

　これを穴あきチェス盤に適用しましょう。
　「サイズ \(2^n\) のどんな穴あきチェス盤も必ずＬ字ブロックを敷き詰められる」を数学的帰納法で証明したいなら、次の２つを証明しなきゃいけません。

【Ａ】

サイズ \(2^1\) のどんな穴あきチェス盤も必ずＬ字ブロックを敷き詰められる。

【Ｂ】

サイズ \(2^k\) のどんな穴あきチェス盤も必ずＬ字ブロックを敷き詰められるなら、サイズ \(2^{k+1}\) にも敷き詰められる。

　では証明していきましょう！

図 3-4

　まず【Ａ】は明らかすぎて言うまでもありません。
　では【Ｂ】はどうでしょう？
　「サイズ \(2^k\) のどんな穴あきチェス盤も必ずＬ字ブロックを敷き詰められる」と仮定して話を進めます。

　そういえば、２×２サイズの知識で４×４サイズを解決できましたね。
　４×４の知識で８×８も解決できた。
　もしかしたら、サイズ \(2^k\) の知識でサイズ \(2^{k+1}\) を解決できそうかな？

1. サイズ \(2^{k+1}\) の盤面をサイズ \(2^k\) の小領域に４等分する。
2. 穴のない３領域に跨がるようにＬ字ブロックを置く。
3. あとはブロックで埋めるだけ。（仮定により必ず埋められる）

　仮定のおかげで、どの小領域もＬ字ブロックで埋められます。
　よって、サイズ \(2^{k+1}\) の盤面全体も埋まるんです。
　というわけで【Ｂ】も証明されました！

　さぁ、結論です。
　穴あきチェス盤について、数学的帰納法によりこれが証明されました。

• サイズ \(2^n\) のどんな穴あきチェス盤にも必ずＬ字ブロックを敷き詰められる。

　無事解決！

3-4．まるで石畳だね！

　最後に、「ちょっとやってみた」系の話を。

　あるサイズ \(2^n\) の穴あきチェス盤にＬ字ブロックを敷き詰めたいなら、その半分のサイズ \(2^{n-1}\) に遡ると良いでしょう。
　そのサイズのおかげで、サイズ \(2^n\) が解決できるわけですもんね。
　もちろん、サイズ \(2^{n-1}\) も同様で、さらに半分のサイズ \(2^{n-2}\) に遡ると良い。
　これを繰り返せば、最終的に２×２サイズにまで遡ります。
　そして、２×２サイズは簡単に敷き詰められる。
　その後、今度は倍々……と戻っていけばサイズ \(2^n\) が完成しますね。

　どのサイズ \(2^n\) も可能だとわかった今、実際に敷き詰めてみたいと考えるのが人情というもの（？）
　というわけで、とあるサイズに挑戦してみました。

　64×64サイズ！
　どうですか！　この1365個のブロックたち！
　どっかの広場とかに行けば、こんな石畳がありそうだ😅

　画像はわざとカラフルにしてみました。
　綺麗でしょう〜🥰
　いやぁもぅ、これだけブロックを敷き詰めたのなら『４色問題』を考えたくなるのさ！
　同じ色が辺で接しないよう色分けする。これもまたパズル。
　さらに頂点でも接しないように色分けしてみました。
　この画像を作っててメッチャ楽しかった😃