第186問の解答
1.問題 [場合の数]
左図のように、碁盤目状の道路があります。
どの道路も南から北方向、西から東方向への一方通行で、かつ「西から東に向かう車が交差点に差し掛かった場合、必ず左折しなくてはならない」という決まりがあります。(1)Aから8区間動いてBに進む方法は何通りありますか。
(2)Aを出発して8区間動く方法は全部で何通りありますか。
2.解答例1(Taroさん、sodoさん、長野美光さん、Gouさん、ミミズクはくず耳さん、杉本未来さん、mhayashiさん、パリンさん、他 多数)
各交差点に、そこまでに至る方法の数を順次書き込んでいきます。
図1
図2
Aからまっすぐ北へ進む場合は、各交差点とも1通り。
Aからまっすぐ東へ進むと、すぐ右隣は1通りですが、それより東へは行けませんので0通りとなります。「東へ進むと次は必ず北へ進まなければならない」という条件がなければ、各交差点では、西隣と南隣の交差点上の数を加えればOKです。
この条件より、東から来るのは、南西の交差点から進む場合となるので、結局南西および南の交差点上の数を加えていけば良いことになります。(図1)
結果は、図2のとおりとなるので、
(1)AからBへ進むのは、21通り
(2)Aから8区間進むのは、Bを含む対角線上の交差点の数を加えて、
1+8+21+20+5=55通り
となります。答:(1)21通り (2)55通り
以上
3.解答例2(トトロ@Nさん、中村明海さん、他)
東西を進む道路を決めれば経路は一意的に決まります。
(1)AからBへ至る経路は、東西の7本の道路から通行する2本を選ぶ場合
の数=7C2=21通りです。
(2)同様に、9C0+8C1+7C2+6C3+5C4
=1+8+21+20+5=55通りです。
4.解答例3(Michaelさん、有無相生さん 、他)
解答例1の図2を見ると、東西の道路にある交差点上の数字は、下から順に
1、1
1、2、1
1、3、3、1
1、4、6、4、1
・・・となり、(x+1)nの係数を並べたもの、いわゆるパスカル三角形をなしていることが分かります。
これは、各交差点上の数字が、すぐ南の道路の隣合う交差点上の数字の和となっているからです。従って、n番目の対角線上の交差点の数字の和fnは、
fn=fn-1+fn-2
という関係が成り立つのでフィボナッチ数列になります。
8区画進む場合の数は、f9=55となります。(参考)
方角を無視すれば、
北へ1区画進むのを、階段を1つ上る
東へ進み、北へ進むのを、階段2つ上る
とみなして、「階段を1段、または2段ずつ進む場合の数」と同じになることが分かります。
n段の場合を、fnとおけば、
最後を1段上るとき:fn-1
最後を2段上るとき:fn-2
の2ケースに分けられるので、fn=fn-1+fn-2が成り立つことが分かります。