映画 猿の惑星：創世記（ジェネシス） Rise of the Planet of the Apes

ハノイの塔 Tower of Hanoi (=Lucas Tower)　

薬剤の投与で賢くなった猿が「ハノイの塔」（映画の中ではLucas Tower）というパズルをすばやく仕上げる場面があり、ディスクが4枚のときの最小移動回数は15回という内容の台詞がありました。

n枚のディスクを移動させるには、n-1枚をまず他の場所に移動させて、次に最下部の1枚を目的の場所に移動させ、いったん移動させたn-1枚をもう一度最下部の上に移動させなければならないので、n枚のときの最小移動回数をa(n)とすると、

a(n+1)=a(n)+1+a(n) すなわち a(n+1)=2a(n)+1

という簡単な漸化式が成り立ちます。これを解くと、

a(n)=2^n-1

となるので、n=4の場合の最小移動回数は2^4-1=15となります。

余談ですが、猿の保護施設職員で猿をいじめる役があのハリーポッターのドラコ･マルフォイ役の俳優であることを知らなかったので、見ているときに気付いたときは驚きました。