みなさん、こんにちは。受験Dr.の桑田陽一です。
6月の講師ブログをお届けします。

今回は、前回の続き。
紹介した京都大学の入試問題を、今回は別の見方で考えてみます。

問題はこんな感じでした。

 

問題(改)

1歩で1段または2段のいずれかで10段の階段を昇ります。
(1)階段の昇り方は全部で何通りありますか。
(2)1歩で2段昇ることを連続しないものとしたとき、昇り方は全部で何通りありますか。
2007年　京都大学理系　改

前回は、「1段昇る」ことと「2段昇る」ことの並べ方を、場合分けして計算する解法で答えを出しました。

ただ、(1)には見覚えのあるという人も多かったはず。
そう、面倒な場合分けをしなくても、「フィボナッチ数列」の考え方が使えるのでは？と思った人もいるでしょう。

その通り、実際、(1)は6年前期までのテキストで触れることの多い、以下のような考え方で解決できます！

 

解答　その2

(1)階段の昇り方は全部で何通りありますか。

10段の階段を、1歩で「1段」の「2段」いずれかで昇ります。
特に、最後の1歩に注目してみると、当然ながら「1段」または「2段」昇っていますね。

最後に1段昇ったときは、それまでに10-1＝9段昇ってきています。
最後に2段昇ったときは、それまでに10-2＝8段昇ってきています。

ということは、10段の階段を昇る場合の数は…、

①9段昇ってきて、最後に1段昇る→要は9段の昇り方と同じ場合の数！
②8段昇ってきて、最後に2段昇る→要は8段の昇り方と同じ場合の数！

この2つを合わせれば求められますね。

つまり、

(10段の昇り方)＝(9段の昇り方)＋(8段の昇り方)

というわけです。

さて、同じように考えると、

(9段の昇り方)＝(8段の昇り方)＋(7段の昇り方)
(8段の昇り方)＝(7段の昇り方)＋(6段の昇り方)
(7段の昇り方)＝(6段の昇り方)＋(5段の昇り方)
…
…
…
(3段の昇り方)＝(2段の昇り方)＋(1段の昇り方)

このように、表すことができますね！
(1段の昇り方)は、明らかに1通り。(2段の昇り方)は、「1段、1段」と昇るか、「2段」一気に昇るかの2通りです。
ということは、
(3段の昇り方)＝(2段の昇り方)＋(1段の昇り方)＝2＋1＝3通り。
(4段の昇り方)＝(3段の昇り方)＋(2段の昇り方)＝3＋2＝5通り。
…
…
のように、実際に足し算を進めていけば、10段であろうが20段であろうが、答えを求められます！
念のため、続きを求めておきましょう。

(5段の昇り方)＝5＋3＝8通り。
(6段の昇り方)＝8＋5＝13通り。
(7段の昇り方)＝13＋8＝21通り。
(8段の昇り方)＝21＋13＝34通り。
(9段の昇り方)＝34＋21＝55通り。
(10段の昇り方)＝55＋34＝89通り。

無事、前回と同じ答えにたどり着きました！

1，2，3，5，8，13，21，…

のように、前の2つの数を足し合わせた数が次の数になるような数列を「フィボナッチ数列」と呼びます。
階段昇りの問題では「フィボナッチ数列」を使うんだ！と覚えていた人もいるでしょう。

でも…

(2)1歩で2段昇ることを連続しないものとしたとき、昇り方は全部で何通りありますか。

こちらはどうしたら良いでしょう？
「階段昇りはフィボナッチ！」とただ覚えているだけではどうしようもなさそうです。
でも、仕組みをきちんと理解している人であれば、実は同じような考え方で正解できるのです！

(1)と同じように、最後の1歩が「1段」のときと「2段」のときに分けてみるとどうでしょう？
余裕のある人は、ここで少し考えてみましょう！

…
…
…

①最後に「1段」昇るとき
これは、(1)と変わりません。
9段昇ってきた後、最後に「1段」昇っているはずですね。

②最後に「2段」昇るとき
(1)と異なり、「2段」昇ることを連続しないという条件がついています。
ということは…。
最後に「2段」昇る直前の1歩では必ず「1段」昇っているはずです。
つまり、10-2-1＝7段昇ってきた後に、「1段」⇒「2段」と昇ったことになるのです！

まとめれば、

①9段昇ってきて、最後に1段昇る→要は9段の昇り方と同じ場合の数！
②7段昇ってきて、最後に1段⇒2段と昇る→要は7段の昇り方と同じ場合の数！

すなわち、

(10段の昇り方)＝(9段の昇り方)＋(7段の昇り方)

と表すことができます。

(1段の昇り方)＝1通り、(2段の昇り方)＝2通り。
そして(3段の昇り方)は、1-1-1、1-2、2-1の3通りですね。

この後は、

(4段の昇り方)＝(3段の昇り方)＋(1段の昇り方)＝3＋1＝4通り。
(5段の昇り方)＝(4段の昇り方)＋(2段の昇り方)＝4＋2＝6通り。
(6段の昇り方)＝(5段の昇り方)＋(3段の昇り方)＝6＋3＝9通り。
(7段の昇り方)＝(6段の昇り方)＋(4段の昇り方)＝9＋4＝13通り。
(8段の昇り方)＝(7段の昇り方)＋(5段の昇り方)＝13＋6＝19通り。
(9段の昇り方)＝(8段の昇り方)＋(6段の昇り方)＝19＋9＝28通り。
(10段の昇り方)＝(9段の昇り方)＋(7段の昇り方)＝28＋13＝41通り。

やはり、順に足し算して答えが出ました！フィボナッチ数列と違って、1つ前と3つ前の数を足すことになるので、ミスには注意が必要ですね！

単に解法を覚えるだけでなく、きちんとその仕組みを理解しておくことで、少しひねられた問題にも対応できることが分かりました。

前回の冒頭で紹介したように、実際に京都大学で出題された元の問題はこんな形でした。

1歩で1段または2段のいずれかで階段を昇るとき、1歩で2段昇ることは連続しないものとする。15段の階段を昇る昇り方は何通りあるか。

ここまで読んでくれたみなさんなら、もう答えが出せますね。
前回の方法でも今回の方法でも、お好みの方でチャレンジしてみてください。
答えは277通りです。

今回はここまで。