ITパスポート 2010年 秋期 問72
問題文
図1のA1地点からC2地点へ行くとき、通過する地点が最も少なくてすむ最短経路は、図2のように数えることによって3通りあることが分かる。A1地点から、C2地点を経由して、D4地点へ行く最短経路は何通りあるか。
選択肢
ア：6
イ：9（正解）
ウ：12
エ：20
🔒 解説は解答すると表示されます
格子上の最短経路の通り数【ITパスポート解説】
正解の理由
図は3×3の小正方形が並ぶ格子（縦横にそれぞれ3マス）です。
格子の左下（A1）から右上の外側（D4）へ最短で行くには「右へ3回」かつ「上へ3回」の合計6回の移動が必要です。
6回のうちどの3回を「右」に使うかを選べば経路が決まるので、全最短経路の数は組合せで です（これは選択肢エの20に該当します）。
格子の左下（A1）から右上の外側（D4）へ最短で行くには「右へ3回」かつ「上へ3回」の合計6回の移動が必要です。
6回のうちどの3回を「右」に使うかを選べば経路が決まるので、全最短経路の数は組合せで です（これは選択肢エの20に該当します）。
ただし問題は「A1からC2を経由してD4へ行く最短経路は何通りか？」と問われています。最短経路でC2を通る経路は、A1→C2の最短経路の数とC2→D4の最短経路の数を掛け合わせた数になります（中継点で経路を分けて考えられるため）。図２からA1→C2の最短経路は3通りと与えられています。C2→D4も、A1→C2と同じだけの移動量（右3回・上3回 のちょうど半分に相当）を要する対称の位置関係にあるため、やはり最短経路は3通りです。したがって経路数は
で、正解は イ（9）です。
解法ステップ
- グリッド全体の構造を確認する（3×3の小正方形 → 枠の格子点は4×4）。
- A1（左下）からD4（右上外）までの最短移動回数を数える：
- 必要な「右」移動 = 3回、必要な「上」移動 = 3回 → 合計6回。
- 全最短経路の総数は （右に行く3回の位置を選ぶ組合せ）。
- 問題はC2を必ず経由する経路の数なので、分割して考える：
- 図２でA1→C2は3通り（図に示されている）。
- C2→D4は対称的に考えて3通り（上と右の移動の組合せが同じ）。
- 積の法則により総数は 。
選択肢別の誤答解説
- ア: 6
おそらく のように誤って移動回数を数えた結果です。今回の移動は合計6回（右3、上3）なので は当てはまりません。 - イ: 9
正解。A1→C2が3通り、C2→D4も3通りなので3×3=9。 - ウ: 12
12は部分的には正しそうに見えますが、例えば「A1→C2が3通り、C2→D4を4通りと誤認した」などの誤算が考えられます。対称性によりC2→D4は3通りです。 - エ: 20
これはA1→D4の「全ての最短経路の数」 を答えてしまったケースです。問題は「C2を経由して」の条件付きなので20は求める数ではありません。
よくある誤解
- 「全体の最短経路（20通り）＝条件付きの最短経路」と混同する
- 問題は必ずC2を通る経路の数を聞いています。全体の数20と答えてしまうミスが多いです。
- 中継点を通る経路は足し算で求めると思い込む
- 経路を区切れる場合は「A→Bの通り × B→Cの通り」で掛け算します（積の法則）。足す必要はありません。
- C2→D4の通り数を図２の数と混同して誤る
- 図２はA1から各点への最短経路数を示していますが、対称性を用いるとC2→D4も同じ数になることを確認してください。
補足コラム
- 格子上の「最短経路を数える」問題は組合せ（コンビネーション）で解くのが基本です。
- 右にm回、上にn回動く必要があるとき、最短経路の数は で求まります。これは「m+n回のうちm回を右にする位置を選ぶ」考え方です。
- 図形的に見るとパスの数はパスが通る格子点ごとに足し合わせる（パスの合流点では足す）ことで求められます。これはパスの重ね合わせがパスカスの三角形（パスの数が二項係数の形）に一致するからです。
FAQ
Q1. なぜA1→C2とC2→D4を掛けるのですか？
A1. A1→C2の各最短経路に対して、C2→D4の各最短経路をつなげると異なるA1→D4（C2経由）の最短経路になります。選択の独立性により総数は掛け算になります（積の法則）。
A1. A1→C2の各最短経路に対して、C2→D4の各最短経路をつなげると異なるA1→D4（C2経由）の最短経路になります。選択の独立性により総数は掛け算になります（積の法則）。
Q2. 「最短経路」を満たすための条件は？
A2. 無駄な戻り（右の後に左、上の後に下）をしないことです。格子上では「右」「上」だけを使う経路が最短になります。
A2. 無駄な戻り（右の後に左、上の後に下）をしないことです。格子上では「右」「上」だけを使う経路が最短になります。
Q3. 図２を使わずに解けますか？
A3. 図２はA1→各点の通りを示しているので便利ですが、対称性と組合せだけでも解けます。今回のように中央点がちょうど全工程の半分にあたる場合は、左右対称で通りは同じになります。
A3. 図２はA1→各点の通りを示しているので便利ですが、対称性と組合せだけでも解けます。今回のように中央点がちょうど全工程の半分にあたる場合は、左右対称で通りは同じになります。
関連キーワード: 格子経路、組合せ、二項係数、最短経路、パスの数え方
\ せっかくなら /
ITパスポートを
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！