基礎理論｜平成22年度 秋期 ITパスポート試験 問72
図 1 の A1 地点から C2 地点へ行くとき，通過する地点が最も少なくてすむ最短経路は，図 2 のように数えることによって 3 通りあることが分かる。A1 地点から，C2 地点を経由して，D4 地点へ行く最短経路は何通りあるか。
〔図1〕碁盤の目の地点（当課が字で書き起こしたもの）
```
上 D1 ── D2 ── D3 ── D4
│ │ │ │
C1 ── C2 ── C3 ── C4
│ │ │ │
B1 ── B2 ── B3 ── B4
│ │ │ │
下 A1 ── A2 ── A3 ── A4
左 右
A1（左下）が出発点、C2 と D4 に印が付いている。
行は下から A・B・C・D、列は左から 1・2・3・4。移動は右か上のみ（最短経路のため）。
```
〔図2〕A1 から C2 までの数え方（当課が字で書き起こしたもの）
```
A1 ──→ B1 (1) ──→ C1 (1) ──┐
│ │ ├─→ C2 (3)
│ └──→ B2 (2) ───────┘
└──→ A2 (1) ──→ B2 (2)
（ ）内数字は，A1 からその地点までの最短経路の数を表す。
```
- 6
- ✓ これが正解9
- 12
- 20
解説
経る地点で切って、前と後ろの通り方を掛け合わせます。
経る地点が決められているときは、そこで切って数えます。前の道と後ろの道は、互いに関わりなく選べました。だから足すのではなく、掛け合わせることになります。前の道は、設問が三通りだと示してくれていました。後ろの道は、上へ一回と右へ二回で三回の動きになります。三回のうちどこで上へ行くかを選ぶので、三通りでした。示された数え方でたどっても、同じ三通りになります。三に三を掛けて、九通りという数が出ました。この数を挙げた肢が当たり、組合せの数え方が要になります。三と三を足した肢は、六通りという数になりました。経る地点を通らない道まで数えた肢は、二十通りです。設問は経ると限っているので、そこまでは数えません。全体の数え方を、そのまま当てると外れました。シラバスも、順列と組合せの考え方を学ぶよう求めています。
ほかの選択肢はなぜ違うのか
- 六という数を挙げた肢が、こちらのほうです。前の三通りと後ろの三通りを、足した形でした。ところが二つの道は、互いに関わりなく選べます。だから足すのではなく、掛け合わせる形になりました。数え方の向きが違います。
- 十二という数を挙げた肢が、こちらに当たります。どこかで数え方を取り違えた形になります。前も後ろも三通りなので、掛ければ九になりました。十二という数は、どちらの道からも出てきません。三通りずつが要です。掛ける相手が違います。
- 二十という数を挙げた肢が、こちらに当たります。経る地点を通らない道まで、数えた形でした。上へ三回と右へ三回で、六回のうち三回を選びます。けれども設問は、経ると限っていました。数えすぎになります。限りを読み落とした形です。
この問題に関係する言葉
- 組合せ
出典：平成22年度 秋期 ITパスポート試験 問72（改変：原典の図表をテキストに書き起こした）
同じ単元をまとめて解くなら基礎理論へ。
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）