ハノイの塔
以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。
3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。
n枚の円盤すべてを移動させるには最低 2 − 1 回の手数がかかる。
解は、次のように再帰的に考えることができる。塔を「一番下にある円盤」と「残りの円盤群」というように分けてみる。そして、まず「残りの円盤群」を移動させ、次に「一番下にある円盤」を移動し、その上にまた「残りの円盤群」を動かせばよい。
解が再帰的な構造をしているということから、この解の手順を表示させるという問題は、再帰的なコンピュータ・プログラムの単純な例題として多用されている。ただし支配数がメルセンヌ数なので、同じく再帰の例題として多用されるフィボナッチ数のように、nが大きくなると結果も膨大となる。
初期状態から n 回動かした状態は、n の2進数表記から、一意的に求めることができる。
すべて左端の棒にある状態からすべて右端の棒に移動させる場合、各円盤の位置は以下のように求められる。
n を2進数で書き表す。
最上位が一番大きい円盤、以下順に対応し1の位が一番小さい円盤に対応する。
最上位が0のとき、一番大きい円盤がまだ動いておらず、1の時には移動済みである。
各桁の数字を一つ上の位と比べる。 同じ値の場合 その円盤は一回り大きい円盤の上に乗っている(同じ棒上にある)。 異なっている場合 その数字が0の場合 下から奇数番目の場合、一回り大きい物の右隣にある。 下から偶数番目の場合、一回り大きい物の左隣にある。 その数字が1の場合 下から奇数番目の場合、一回り大きい物の左隣にある。 下から偶数番目の場合、一回り大きい物の右隣にある。
ただし、左端の棒の左隣は右端、右端の棒の右隣は左端とする。
2進数の演算を利用すると、n 番目の移動を簡単に表記することができる。C言語の表記を用いると n 番目の移動は、「(n&(n-1))%3 番目の棒にある円盤を ((n|(n-1))+1)%3 番目の棒に移動する」となる。
なお、メルセンヌ数は二進数では全ての桁の位を占める数が1になるから、前述の二進数演算による解析は、全ての棒に与えられた枚数n分の二進メルセンヌ数桁との因果関係を明らかにしている。これは次項のパリティとグレイ・コード解法にも大きく関与しているといえる。