ITパスポート試験 ITパスポート 2010年 (平成22年 秋期) 問72: 図1のA1地点からC2地点へ行くとき、通過する地点が最も少なくてすむ最短経路は、図2のように数えることによって3通りあることが分かる。A1地点から、C2地点を経

問題本文

図1のA1地点からC2地点へ行くとき、通過する地点が最も少なくてすむ最短経路は、図2のように数えることによって3通りあることが分かる。A1地点から、C2地点を経由して、D4地点へ行く最短経路は何通りあるか。 図1: 4×4のグリッド上にA1(左下)、D4(右上)などの地点が配置されている。 図2: A1(1)→B1(1)、A1→A2(1)、B1→C1(1)、B1→B2(2)、A2→B2、C1→C2(3)、B2→C2。 ( )内数字は、A1からその地点までの最短経路の数を表す。

選択肢

• ア.6
• イ.9
• ウ.12
• エ.20

正解

イ. 9

解説

最短経路の場合分け問題.A1からC2は3通りと与えられている.C2からD4への最短経路数を計算し、A1→C2→D4の総数=A1→C2(3通り)×C2→D4(?通り)で求める.C2からD4は右に1区画・上に2区画移動で、組合せC(3,1)=3通り.合計3×3=9通り.混同注意として、合計問題は両区間の積を取る原則「経由点までの数×経由点からの数」を覚える.正解はイ.

選択肢ごとの解説

• ア.6通りはA1→C2(3通り)+C2→D4(3通り)と誤って加算した値.経路の組合せは順次的な経路選択であり、積で計算するのが正しいため誤答.
• イ.正解.A1→C2が3通り、C2→D4が3通り(右1上2の組合せ).3×3=9通りが正答.経由点問題は両区間の経路数を掛ける.
• ウ.12通りは中間経路数の誤算.正しくはC2→D4=C(3,1)=3通り、A1→C2=3通り、計9通り.12は数え過ぎ.
• エ.20通りはA1→D4の総経路数(C(6,3)=20)に近い値だが、C2経由の条件を満たさない総経路数で誤り.C2必須経由を考慮していない.