ドラマ スペシャリスト3

ハノイの塔

上からアルファベットの文字が"cosidemple"と書かれてある10段のハノイの塔の操作中、51手目の状態が"simple code"になり、これが事件解決ためのヒントになるという話です。

n段のハノイの塔の最小移動回数f(n)は2^n-1になりますが、まずこれを求める漸化式の解き方が画面に出ます。n段の移動には、①まずn-1段を移動する（f(n-1)手）、②一番下のn段目を移動する（1手）、③またn-1段を移動する（f(n-1)手）という操作になるので、漸化式はそれらの和で次のようになります。
f(n)=2f(n-1)+1
これを解くと、
f(n)=2^1(2f(n-2)+1)+1
=2^2(2f(n-3)+1)+2+1
=2^3f(n-3)+2^2+2+1
…
=2^(n-1)f(1)+2^(n-2)+2^(n-3)+…+2+1
=2^(n-1)+2^(n-1)-1
=2^n-1
よって、f(n)=2^n-1となりますが、ドラマでは主人公がこの式を知っていたようで、2^n-1から紙に書き始めます。
2^n-1
2^10-1=2×2×2×…×2×2-1
=1024-1
=1023
その後、なぜかいきなり
2^5+2^4+2^1+2^0
51
と計算して、「51手」とつぶやき、10段のハノイの塔を実際に操作して、51手目の状態が"simple code"になることに気がつきます。
ただ、これは実際に操作しなくても計算で次のように求めることができます。
f(1)=1, f(2)=3, f(3)=7, f(4)=15, f(5)=31, f(6)=63
ですから、51=f(6)の途中=f(5)+20=f(5)+1+19=f(5)+1+f(5)の途中=f(5)+1+f(4)+4=f(5)+1+f(4)+1+3=f(5)+1+f(4)+1+f(2)
すなわち、まず31手で上の5段を移し、次の1手（32手目）で6段目を移し、次の15手（47手目まで）で上の4段を移し、次の1手（48手目）で5段目を移し、あと3手（51手目まで）で上の2段を移します。これでどんな状態になるかを分かり易く右図にまとめてみました。（WolframAlphaで"Tower of Hanoi 10-disk 51 step"と入力したらちゃんと51手目の状態が表示されました。WolframAlphaはすごい！）

それにしても，主人公がなぜ2^5+2^4+2^1+2^0を理解したのかが疑問に残りました。