以前の記事の続きです。
中学入試でたまに取り上げられるマニアックなテーマとして「ハノイの塔」もあります。遊んだことがある人に多少有利だったかもしれませんが、たとえば次のような問題が出されています。
ハノイの塔①（日出学園2018）
太郎さんは3本の柱(A、B、Cとします)と、大きさがことなる数枚の円板を用いたパズルで遊んでいます。この円板は中央に穴が開いており、最初は柱Aに図1(a)のように全て重ねられています(図は円板が2枚の例です)。全ての円板を最少の移動回数で柱Cに移動することが目標です。その時には次のきまりを守らなければいけません。
<きまり>
① 1回には1枚の円板だけを移動する
② 移動する円板は柱以外に置けない
③ 小さい円板の上には大きい円板は置けない
例えば、円板の枚数が2枚の時は図1(b)のようにA→B、A→C、B→Cの3回で移動することができます。このときのとき、次の問いに答えなさい。
⑴ 円板が3枚の場合、移動は最少で何回かかりますか。また、その移動の流れを問題文の下線部にならって、すべて書きなさい。
7回。A→C、A→B、C→B、A→C、B→A、B→C、A→C
⑵ 円板が6枚の場合、移動回数は63回です。図2はその途中の様子を記録したものです。太郎さんはこの図2を見て、あるきまりに気づくことができました。6枚の移動回数が63回であることを利用すると、円板が7枚の場合の移動は最少で何回かかりますか。
図2をみると、①6枚のうち上の5枚をまずA→Bに移動させ、②残った一番下の1枚をA→Cに移動させ、③Bにある5枚をCに移動させている。②は移動回数1回、①と③は同じ動きなので移動回数も同じ（31回ずつ）で合計63回となっている。
円板が7枚の場合もやり方は一緒で枚数が変わるだけ。こんどは①円板6枚をA→Bに移動させ（ここで63回）、②1枚をA→Cに移動させ（1回）、③円板6枚をB→Cに移動させる（ここも63回）ことから合計127回が最少
ハノイの塔で円板の枚数がN枚のとき、最少の移動回数は
2×2×…×2（2をN回かけたもの）－1
となることが知られています。
ハノイの塔②（大宮開成2020）
下の図のようにA、B、Cの3本の棒が立てられていて、Aの棒には上から小さい順にいくつかの円板が重ねられています。
次の①〜③のルールにしたがってAの棒に重ねられている円板をA以外の1本の棒にすべて移動します。
① 他の棒に移すときに1回と数えます。
② 1回に1枚だけ移すことができます。
③ すでに置かれている円板の上には、より小さい円板しか重ねることができません。
次の各問いに答えなさい。
⑴ Aの棒にある円板が3枚のとき、最も少ない移動回数は何回ですか。
2×2×2－1＝7回
⑵ Aの棒にある円板が5枚のとき、最も少ない移動回数は何回ですか。
2×2×2×2×2－1＝31回
ハノイの塔の計算方法（覚えるのも簡単）を知っていると上のように秒殺できてしまうため、バレないように次のようにカードに変えて出されるケースもあります。
ハノイの塔③（芝中2022第2回）
A、B、Cの3つの箱があります。箱Aには1から順に1、2、3…と整数が書かれているカードが上から小さい順に重ねられています。そのカードを次のルールでなるべく少ない回数で箱Aから箱Cに移動します。
ルール1．1回に移動するカードは重ねられた一番上の1枚だけです。
ルール2．移動するカードは空の箱か、移動するカードの数字より大きいカードの上にしか移動できません。
ルール3．A、B、Cのどの箱のカードもA、B、Cのどの箱にでも移動することができます。
以上のようにして、3枚のカードは7回で移動できます。
⑴ 箱Aに4枚入っている場合を考えます。まず、1、2、3のカードを(例)と同様にして箱Bに7回で移動します。次に4のカードを箱Aから箱Cに移動した後、箱Bの3枚を(例)と同様にして箱Cに移動すると、4枚のカードは▢回で移動ができます。
ハノイの塔と同じしくみなので 2×2×2×2－1＝15回
⑵ 箱Aに6枚入っている場合、6枚のカードは▢回で移動できます。
2×2×2×2×2×2－1＝63回 
