本郷三丁目校からの挑戦状 ~解答・解説~ | 東進ハイスクール本郷三丁目校|東京都

校舎からのお知らせ

2016年 12月 2日 本郷三丁目校からの挑戦状 ~解答・解説~

 

皆さんこんにちは!

学校の前でチラシを見てくれた方に、その解答・解説を紹介させていただきたいと思います!

問題はこちら↓

「1歩で1段または2段のいずれかで階段を昇るとき,1歩で2段昇ることは連続しないものとする。15段の階段を昇る昇り方は何通りあるか(2007 京都大 理系)」

 

少し問題文が分かりづらいので書き直してみると、

「階段を、1歩につき1段か2段ずつ昇っていきます。ただし、1歩で2段昇った後には一段飛ばしで(=1歩で2段を)昇ってはいけないというルールがあるとき、15段の階段の昇り方は何通りありますか?」
ということです!

似た問題を解いたことがある人は、「ああ、あれね」とすぐに分かってしまったかもしれません。

分からない人は「単純化」して考えてみてください! 数学の大事な考え方だと思います!
(いきなりルールを付けて考えるのではなく制約がないとしたら何通りあるのか考えたり、例えば5段だったら何通りあるだろうと考えたり…)

以下から解答です!
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
《解答》
n段の階段を条件に従って昇る場合の数をan(通り)とする。

 

n=1,2,3について、a₁=1,a₂=2,a₃=3は明らかである。

n≧4のときを、最初の一歩で場合分けして考える。

(ⅰ)最初1段昇ったとき、残る(n-1)段の昇り方はa(n-1)通りである。

(ⅱ)最初2段昇ったとき、条件より次は1段昇るから残る(n-2)段の昇り方はa(n-3)通りである。

 

ここで、(ⅰ)(ⅱ)はいずれかの場合しか起こらず互いに排反であるから、n≧4について、an=a(n-1)+a(n-3)…① が成り立つ。

 

①を続けて利用していって、

a4=a3+a1=3+1=4

a5=a4+a2=4+2=6

a15=a14+a12=189+88=277

 

よって、277通り…(答)

☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
いかがだったでしょうか?

フィボナッチ数列は中学入試の問題としてもよく出題されるので、それを思い出す人もいるかもしれませんね(気になる人は調べてみてください!)
中学入試から大学入試にまで出題される面白い題材だと思ったので、今回紹介させてもらいました!

次回以降の「挑戦状」もお楽しみに。。

 

P.S.
今回はフィボナッチ数列の問題として捉えその解法を載せましたが、計算量的には順列の問題と捉えた方が楽に解けます。

(参考:東進 大学入試問題過去問データベース http://www.toshin-kakomon.com/)