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パスポートを
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！