15段の階段があります

コマネチ大学の話。たまたま見かけたので考えてみた。

15段の階段があります。階段を一段づつ上ってもOK、一段飛ばしで上ってもOKとして、この階段の上り方が何通りあるか答えなさい。

数列の問題かな。ということで、セオリー通りに、まず

n段のときに c(n) 通りの上り方があるとする

ここから考えてみる。

n+1段のときの上り方は、

n段目まで上ってそのままn+1段に上がるのは、c(n)通り。

n-1段まで上って、n段目を飛ばしてn+1段に上がるのは、c(n-1)通り

他に上りようがないから、

c(n+1) = c(n) + c(n-1)

なんだフィボナッチじゃん。

フィボナッチ数列はいわゆる算数のおもしろ系の本に出てくるので、小学生でも知ってる人は知っている。当たり前か。知ってることだけ。

ていうか、ここまで考えるのに3分かかっていない。これ間違える要素あるの?　東大生が間違えたというのが信じられない。規則性って何しようとしたのかな…

一般項を出すのは面倒なので、15段なら足せばすぐだろ。ということでやってみる。

c(1) = 1
c(2) = 2
c(3) = 3
c(4) = 5
c(5) = 8
c(6) = 13
c(7) = 21
c(8) = 34
c(9) = 55
c(10) = 89
c(11) = 144
c(12) = 233
c(13) = 377
c(14) = 610
c(15) = 987

確かにこれ数えると間違いそうだというのは分かったような気がする。

*

ところで、身近に15段の階段ってあります?　探してみたのだが、12段、13段、14段は案外あって、15段がすぐに見つからない。

(ネタ元)

404 Blog Not Found:コマネチ大学を聴講してみた