G検定（ジェネラリスト検定） 人工知能とその動向 練習問題 第24問: 3本の棒と、大きさの異なる5枚の円盤を使うハノイの塔を考える。はじめに5枚の円盤は、下から大きい順に1本の棒に積まれている。1回に1枚の円盤を動かし、小さい円盤

肢1が正解です。n枚の最小手数をh(n)とすると、いちばん大きい円盤を動かす前に上のn−1枚を別の棒へ移し（h(n−1)手）、いちばん大きい円盤を1手で移し、その上へn−1枚を移し直す（h(n−1)手）ので、h(n) = 2h(n−1) + 1、h(1) = 1 です。

Wolfram MathWorldの「Tower of Hanoi」の項は、これを解いた式を示しています。

h(n) = 2^n − 1

h(5) = 2^5 − 1 = 32 − 1

= 31

肢2の15は4枚のときの値（2^4 − 1）、肢3の25は5の2乗、肢4の32は最後の −1 を忘れた 2^5 です。円盤が1枚増えるごとに手数はほぼ倍になり、枚数に対して指数的に増えます。