最新記事 2019年01月11日

テーマ: 算数

みんなで遊ぼう!【ハノイの塔】

みなさん、こんにちは。 受験ドクターの坂井です。

6年生のみなさん、最後のひと踏ん張りです。がんばってください。

残りの時間はどっしりと構えて、毎日規則正しい受験生活を送ってください。
ポイントとしては、
① 特別にがんばる日を作る必要はないこと。ここまで頑張ってこれたことを残り20日間同じように過ごしてください。
② 体調が悪くなったら、思い切って休養すること。ここまで頑張ってこれたことが1日休養して実力が下がるはずがない!
③ 前日は勉強を早く切り上げて早めに寝ること。ここまで頑張ってきたからこそ緊張はするでしょう。でも適度な緊張は実力を発揮できるベストな状態です!
以上3点です。

ドクターの先生たちは君たちを最後まで伴走していきます!!

さて、今日はちょっとした息抜きにブログにたちよってくれた受験生も、来年受験を迎える5年生もみんなでゲーム感覚で楽しめるお話を1つ。

【ハノイの塔】のお話をしようと思います。

ハノイの塔の由来は、フランスの数学者エドゥアール・リュカが1883年に発売したゲーム「ハノイの塔」によるものです。

ハノイの塔1

まず、どんなルールのゲームなのかをご紹介します。
図のように円盤が棒に刺さっている状態から、すべての円盤を他の棒に移動させるというものです。
動かすときのルールは以下のようになります。

1.1回に1枚しか動かしてはならない。
2.小さな円盤の上にそれより大きな円盤を乗せてはならない。
3.すべてこの3本の棒を使って移すこと。棒以外のところに円盤を置いてはならない。

さらに、円盤の枚数を増やしたときに、移動し終わるのに最低何回の操作が必要なのかを考えていきます。

<円盤が2枚のとき>

1回目:円盤aを右の棒に移します。
2回目:円盤bを真ん中の棒に移します。
3回目:最後に円盤bの上に円盤aを移します。
最小3回の移動で円盤を移動させることができます。

ハノイの塔2

ハノイの塔3

ハノイの塔4

ハノイの塔5

<円盤が3枚のとき>

ハノイの塔21

ここまでの操作は、円盤が2枚のときと同じです。

4回目:円盤cを右の棒に移します。ハノイの塔7

ここからは、円盤a, 円盤bを右の棒に移動させることになるので、このあと円盤2枚のときと同様3回の移動が必要になります。

ハノイの塔22

最小7回の移動で円盤を移動させることができました。

ハノイの塔9

ハノイの塔10

ハノイの塔11

ハノイの塔20

ハノイの塔13

ハノイの塔14

ハノイの塔15

ハノイの塔16

ここで勘のよい人は、お気付きになったのではないでしょうか。

円盤の枚数を4枚にしたときは、最低何回の操作で他の棒に移すことができるか分かった人もいるでしょう。そうです。15回の操作で移動させることができるのです。

こんな風に考えます。

円盤が4枚のとき
円盤a, 円盤b,円盤cを真ん中または右の棒に移します。
円盤3枚のときの移し方ですから、7回の操作が必要になります。円盤a, 円盤b,円盤cを右の棒に移したとすると、真ん中の棒が空いているので、円盤dを真ん中の棒に移します。そのあと真ん中の棒に右の棒に刺さっている3枚の円盤、円盤a, 円盤b,円盤を真ん中の棒に移すのであと7回の操作が必要になります。よって7+1+7=15回の操作が必要だとわかります。

以上をまとめると次の表のようになります。

ハノイの塔17

1枚少ないときの必要最小の操作回数を2倍して1を加えた回数が必要になります。
たとえば、円盤4枚のときは、1枚少ない3枚のときの7回の2倍に1を加えた15回になります。
10枚のときも順番に計算していくと1023回と求めることができます。

このハノイの塔は中学受験においてもたびたび入試で登場してくるお話ですので、ぜひ1度遊んでみてください。

では、みなさん、またお会いしましょう。