TMR

15段ある階段を1段か2段ずつで上るとき、何通りの上り方があるか？


深夜に放送していた北野武の某数学番組の中で出題された問題です。番組のテーマはフィボナッチ数列。暇な人は解いてみて。色々な解法があると思うが、やっぱりフィボナッチで解くと芸術的。あ〜数研なんてやってた頃が懐かしいなぁ。


解答例(Ctrl+A)

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

n段目に着く場合の数をa[n]とおく。
15段目に着くには、13段目から1段飛ばしで上るか、14段目から1段で上るかの2通りなので、a[15]=a[13]+a[14]となる。
よってa[15]はフィボナッチ数列の第16項に等しいので、a[15]=987通りとなる。

※フィボナッチ数列：1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,…

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -