『オンボロ階段の問題』解答


◆静岡県 ヨッシー さんからの解答。

まず、5段目、10段目に関係なく、15段の階段を上る方法を数えます。

1段の階段を上る方法は、1通りだけです。

2段の階段を上る方法は、
 1+1 と 2 の2通りです。

3段の階段を上る方法は、
 1+1+1 と 1+2 と 2+1 と 3 の4通りです。

4段以上の階段については以下のように考えます。

n(>3)段の階段の上り方をCn 通りとすると、
n の内訳は、

 最後の1歩を1段で上った。・・・Cn-1 通り
 最後の1歩を2段で上った。・・・Cn-2 通り
 最後の1歩を3段で上った。・・・Cn-3 通り

なので、Cn=Cn-3+Cn-2+Cn-1

という関係にあります。
これを表にすると、以下の通りです。

段数上り方
13
24
44
81
149
10274
11504
12927
131705
143136
155768

15段まで上る5768通りのうち、5段目を踏む上り方は、
5段目までを13通りで上り、
そこから15段目までの10段を274通りで上るので、
 13×274=3562 通り

同様に、10段目を踏む上り方は、
 274×13=3562 通り

5段目も10段目も踏む上り方は
 13×13×13=2197 通り

よって、5段目も10段目も踏まない上り方は、
 5768−3562−3562+2197=841 通り


◆広島県 清川 育男 さんからの解答。

フィボナッチ数列とトリボナッチ数列の組み合わせでよいのではないでしょうか。
5段と10段を0とすれば結局トリボナッチ数列とも考えられます。

段数上り方
11
18
29
58
10
1187
12145
13232
14464
15841


 『オンボロ階段の問題』へ

 数学の部屋へもどる