ハノイの塔は、高校数学(数学B)の漸化式や、数学的帰納法の題材として、教科書や入試問題によく出てきます。この記事では、例題を解きながら考え方を練習します。円盤には小さい順に1、2、3…と番号を付け、n枚の塔を移す最少手数を aₙ と書きます。

例題1 漸化式を立てる

問題: 3本の棒A・B・Cがあり、Aに大きさの違うn枚の円盤が、大きい順に積まれている。円盤を1回に1枚ずつ動かし、小さい円盤の上に大きい円盤を置かないようにして、すべての円盤をCへ移す。最少の手数を aₙ とするとき、aₙ₊₁ を aₙ で表せ。

解き方: いちばん大きい円盤(n+1番)に注目します。この円盤をCへ動かすには、その瞬間、上のn枚がすべてBに積まれていなければなりません。

  1. 上のn枚をAからBへ移す … 最少で aₙ 手
  2. n+1番の円盤をAからCへ動かす … 1手
  3. Bのn枚をCへ移す … 最少で aₙ 手

この手順でn+1枚を移せるので aₙ₊₁ ≦ 2aₙ + 1 です。逆に、どんな手順でも1〜3の手数は必ずかかるので aₙ₊₁ ≧ 2aₙ + 1 です。よって、

aₙ₊₁ = 2aₙ + 1(a₁ = 1)

入試では「≦」と「≧」の両方を示して、等号を言い切ることが求められることがあります。くわしい説明は最少手数の公式にあります。

例題2 一般項を求める

問題: a₁ = 1、aₙ₊₁ = 2aₙ + 1 で定められる数列の一般項を求めよ。

解き方: aₙ₊₁ = paₙ + q の形の漸化式は、α = 2α + 1 を満たす α を使って変形します。α = −1 なので、両辺に1を足して、

aₙ₊₁ + 1 = 2(aₙ + 1)

となります。数列 aₙ + 1 は、初項 a₁ + 1 = 2、公比2の等比数列です。よって aₙ + 1 = 2 · 2ⁿ⁻¹ = 2ⁿ で、

aₙ = 2ⁿ − 1

検算として、a₁ = 1、a₂ = 3、a₃ = 7 が漸化式と合うことを確かめておきましょう。

例題3 数学的帰納法で証明する

問題: n枚の円盤を移す最少手数が 2ⁿ − 1 であることを、数学的帰納法で証明せよ。

解き方:

  1. n = 1 のとき、円盤1枚は1手で移せ、それより少なくはできないので、最少手数は 1 = 2¹ − 1 で成り立つ。
  2. n = k のとき、最少手数が 2ᵏ − 1 であると仮定する。n = k+1 のとき、例題1の考え方から最少手数は 2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1 となり、n = k+1 のときも成り立つ。
  3. 1、2より、すべての自然数nについて成り立つ。

例題1の「≦と≧の両方」を、帰納法の2の段階で使っているのがポイントです。

例題4 隣の棒にしか動かせない場合

問題: 棒A・B・Cが一列に並び、円盤はAとB、BとCのあいだでしか動かせない(AからCへ直接は動かせない)とする。n枚の円盤をAからCへ移す最少手数 bₙ を求めよ。

解き方: いちばん大きい円盤nは、A → B → C と2回動かす必要があります。

  1. 上のn−1枚をAからCへ移す … bₙ₋₁ 手(nをBへ動かすには、Bを空けておく必要がある)
  2. 円盤nをAからBへ … 1手
  3. n−1枚をCからAへ移す … bₙ₋₁ 手(nをCへ動かすには、Cを空けておく必要がある)
  4. 円盤nをBからCへ … 1手
  5. n−1枚をAからCへ移す … bₙ₋₁ 手

よって bₙ = 3bₙ₋₁ + 2(b₁ = 2)。α = 3α + 2 から α = −1 なので、bₙ + 1 = 3(bₙ₋₁ + 1)。数列 bₙ + 1 は初項3、公比3の等比数列なので、

bₙ = 3ⁿ − 1

1〜6枚について、すべての置き方を調べる計算でも、この手数が最少であることを確かめています。おもしろいことに、3ⁿ − 1 手のあいだに、3ⁿ通りあるすべての置き方を1回ずつ通ります(置き方の数は規則性の記事)。

例題5 練習問題

最後に、自分で解いてみましょう。答えは下にあります。

  1. 円盤が10枚のときの最少手数を求めよ。
  2. 最少手数が1000手を超えるのは、円盤が何枚以上のときか。
  3. 最少手順で円盤n枚を移すとき、いちばん小さい円盤は何回動くか。

答え: 1. 2¹⁰ − 1 = 1023手。2. 2ⁿ − 1 > 1000 より 2ⁿ > 1001、2⁹ = 512、2¹⁰ = 1024 なので10枚以上。3. 2ⁿ⁻¹回(理由は規則性の記事の「円盤ごとの動く回数」)。