第170問の解答
1.問題 [場合の数]
左図のように2地点A、Bの間には太い道路と細い道路が通っています。
AからBまで遠回りをせずに行くとき、細い道路から太い道路にでた場合にはそのまま直進できず、必ず太い道路に曲がらなければなりません。では、このような道順は何通りあるでしょうか?
2.解答例1(杉本未来さん、長野美光さん、圭太さん、NobleScarletさん、他多数)
下図のように、A地点を1とし、各格子点を通る場合の数を順に加えていきます。
ただし、細い道路から太い道路へ出た場合、直進するものは数えないようにします(赤い格子点)。この結果、B地点に至る経路数は126通りになります。
答:126通り
以上
3.解答例2(トトロ@Nさん、あんみつさん、noetherさん、有無相生さん、mhayashiさん、King of Kingさん、N.Nishiさん、他多数)
n×m個のマス目上の最短経路数は、一般にn+mCn=(n+m)!/n!m!で表せます。従って、AからBへ至る最短経路の合計は6+4C6=210通りあります。
このうち、細い道路から太い道路に出たとき直進する場合は下図のように6ケースあります。
それぞれの経路数は、次の通り合計114通りあります。
ところが、これには下図のように重複して数えたものが30通りあるので、これを除外する必要があります。
従って、求める経路数は、210−(114−30)=126通りとなります。