中学受験算数　必須知識【ハノイの塔】

【問題１　出題校：大宮開成中学】

下の図のようにA、B、Cの3本の棒が立てられていて、Aの棒には上から小さい順にいくつかの円板が重ねられています。

次の①〜③のルールにしたがって、Aの棒に重ねられている円板をA以外の1本の棒にすべて移動します。
① 他の棒に移すときに１回と数えます。
② １回に１枚だけ移すことができます。
③ すでに置かれている円板の上には、より小さい円板しか重ねることができません。

次の各問いに答えなさい。
⑴ Aの棒にある円板が３枚のとき、最も少ない移動回数は何回ですか。
⑵ Aの棒にある円板が５枚のとき、最も少ない移動回数は何回ですか。

今回は、「ハノイの塔」と呼ばれる有名問題であり、最も少ない移動回数が問われます。
一見すると非常に面倒な問題に見えますが、以下のPOINTを押さえることで１分程度で解けます！
POINTを是非チェックしてみてください。

【POINT】

ハノイの塔で円板の枚数がN枚のときの最少の移動回数
２×２×２×・・・×2（２をN回かけたもの）－１

【解説】

（１）円板が３枚ですので、２を３回かけます。
　　　２×２×２－１＝７回
　　　※最後に１を引くのを忘れないこと！
（２）今回は円板が５枚ですので、２を５回かけます。
　　　２×２×２×２×２－１＝３１回
　　　※最後に１を引くのを忘れないこと！

今回は、ハノイの塔と呼ばれる有名問題を紹介しました。
この問題ですが、円盤ではなく、カードに変えて出題されるケースもあります。
芝中学で出題された以下の問題を紹介します。

【問題２　出題校：芝中学（一部省略）】

A、B、Cの３つの箱があります。箱Aには１から順に１、２、３・・・と整数が書かれているカードが上から小さい順に重ねられています。

（例）

そのカードを、次のルールでなるべく少ない回数で箱Aから箱Cに移動します。
ルール１：１回に移動するカードは重ねられた一番上の１枚だけです。
ルール２：移動するカードは、空の箱か、移動するカードの数字より大きいカードの上にしか移動できません。
ルール３：A、B、Cのどの箱のカードもA、B、Cのどの箱にでも移動することができます。
（問）箱Aに６枚入っている場合、６枚のカードは何回で移動できますか。

【解説】
円盤からカードに変更になりましたが、仕組みは「ハノイの塔」と同じです。以下のPOINTを押さえておけば一瞬です！

【POINT】

ハノイの塔で円板の枚数がN枚のときの最少の移動回数
２×２×２×・・・×2（２をN回かけたもの）－１

今回はカードが６枚ですので、まずは２を６回かけます。
２×２×２×２×２×２－１＝６３回
よって６３回で移動できます。
※今回も最後に１を引くのを忘れないこと！

最後に

いかがでしたか。
中学受験の算数では有名な問題が多数出題されており、有名問題には明確な解法があるケースが多いです。
解法のPOINTを暗記することで本番でも確実に得点が見込めるので、是非確実に身に付けてください。