平成22年秋期試験問題 問72
図1のA
1地点からC
2地点へ行くとき，通過する地点が最も少なくて済む最短経路は，図2のように数えることによって3通りであることが分かる。A
1地点から，C
2地点を経由して，D
4地点へ行く最短経路は何通りあるか。
解説
A1からC2への最短経路は問題文のとおり3通りです。C2からD4は上へ1回、右へ2回の3移動で、上に進む位置を選ぶ3通りがあります。
前半と後半は独立に選べるので3×3＝9通りです。C2を経由するという条件を外して全経路を数えないようにします。
