問題１１(2006早稲田中) - すぐる学習会 -

解答　(1)　３５通り　　(2)　８９通り　　(3)　２６通り

解説

(1)

　２段上がり３回で，２×３＝６(段)を昇ったことになりますから，
　残り１０－６＝４(段)は，１段上がりで４回昇ったことになります。
　「２段上がりで３回，１段上がりで４回」昇ったわけです。
　このような昇り方は，何通りあるのでしょうか。

　実はこの問題は，次の問題と同じ意味なのです。
　「右のようなごばんの目の形をした道を，家から学校まで，最も短い道のりで行く方法は何通りありますか。」
　家から学校までには，たての道が３本，横の道が４本あります。
　この，たての道を「２段上がり」，横の道を「１段上がり」だと考えれば，
　「２段上がりが３回，１段上がりが４回」という意味になります。

　たとえば，右の図のような階段の昇り方をしたとしまょう。
　この昇り方は，「１段，２段，１段，２段，２段，１段，１段」となっています。
　２段上がりが「たて」，１段上がりが「横」という道の進み方だとすれば，
　「横，たて，横，たて，たて，横，横」となり，
　下の図のような道の通り方になるわけです。

　家から学校までの通り方を調べるために，右の図のようにア～ケの記号をつけてみます。
　家からエまでの通り方は，もちろん１通りです。
　家からオまでの通り方も，家→エ→オ，という通り方しかないので，１通りです。
　家からカまでの通り方も，家→エ→オ→カ，という通り方しかないので，１通りです。
　このように考えると，ア～キのいずれの場合も，通り方は１通りしかないことがわかります。
　では，クまでの通り方は何通りになるでしょうか。
　クを通るためには，その前にウかエを通っていなければなりません。
　ウまでは１通り，エまでも１通りですから，クまでの通り方は，
　１＋１＝２(通り) となります。
　同じように考えると，ケまでの道のりは，クまでの２通りと，オまでの１通りを合わせて，３通りになります。

　このように考えていくと，右の図のようになり，家から学校までの通り方は３５通りであることがわかります。
　よって，階段の昇り方も，３５通りです。

(2)

　１度に１段のぼる方法を「ちょっとだけのぼる」という意味で「チ」，
　　１度に２段のぼる方法を「ジャンプするようにのぼる」という意味で「ジ」とします。

　　すると，１段の階段ののぼり方は，もちろん「チ」だけの１通りです。

　　２段の階段ののぼり方は，「チチ」と「ジ」の２通りです。

　　３段の階段ののぼり方は，「チチチ」「チジ」「ジチ」の３通りです。

　　４段の階段ののぼり方は，「チチチチ」「チチジ」「チジチ」「ジチチ」「ジジ」の５通りです。
　　この５通りの場合を，それぞれ図１・図２・図３・図４・図５とします。

　　この５通りの図を，４段をのぼり切る直前にどこにいたかによって，場合分けしてみます。
　　図１・図３・図４では，４段をのぼり切る直前には，３段目にいました。
　　図２・図５では，４段をのぼり切る直前に，２段目にいました。

　　図１・図３・図４は，３段目までののぼり方が３通りあるので，３つの図になりました。
　　図２・図５では，２段目までののぼり方が２通りあるので，２つの図になりました。
　　したがって，４段の階段ののぼり方を求めるときには，

３段目までののぼり方である「３通り」と，２段目までののぼり方である「２通り」を，加えればよい。

　　ということになります。

　　同じように考えると，５段の階段ののぼり方を求めるときには，４段目までののぼり方である「５通り」と，３段目までののぼり方である「３通り」を加えて，８通りになります。

　　６段の階段では，５段目までののぼり方である「８通り」と，４段目までののぼり方である「５通り」とを加えて，１３通りになります。

　　このように考えていくと，階段の昇り方は，次のようなフィボナッチ数列になっていることがわかります。

　　１，２，３，５，８，１３，…

　　７段以降もさらに計算していくと，次のようになります。

　　１，２，３，５，８，１３，２１，３４，５５，８９，…

　　よって，１０段の階段の昇り方は，全部で８９通りになります。

(3)

　７段目を踏まないということは，６段目から８段目までジャンプする，ということです。

　６段目までの昇り方は，(2)で求めたように１３通りあります。
　８段目から１０段目までの昇り方は，「チチ」か「ジ」のどちらかなので，２通りです。
　よって，
　８段目から１０段目までを，「チチ」と昇る方法は，(６段目までをどう昇るかによって)１３通りあるし，
　８段目から１０段目までを，「ジ」と昇る方法も，(６段目までをどう昇るかによって)１３通りあることになります。
　したがって，７段目を踏まないで昇る方法は，１３×２＝２６(通り)になります。　