平成22年度 秋期 問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
答えと解説を見る
✓ これが正解イ9
解説
経る地点で切って、前と後ろの通り方を掛け合わせます。
経る地点が決められているときは、そこで切って数えます。前の道と後ろの道は、互いに関わりなく選べました。だから足すのではなく、掛け合わせることになります。前の道は、設問が三通りだと示してくれていました。後ろの道は、上へ一回と右へ二回で三回の動きになります。三回のうちどこで上へ行くかを選ぶので、三通りでした。示された数え方でたどっても、同じ三通りになります。三に三を掛けて、九通りという数が出ました。この数を挙げた肢が当たり、組合せの数え方が要になります。三と三を足した肢は、六通りという数になりました。経る地点を通らない道まで数えた肢は、二十通りです。設問は経ると限っているので、そこまでは数えません。全体の数え方を、そのまま当てると外れました。シラバスも、順列と組合せの考え方を学ぶよう求めています。
ほかの選択肢はなぜ違うのか
- ア6：六という数を挙げた肢が、こちらのほうです。前の三通りと後ろの三通りを、足した形でした。ところが二つの道は、互いに関わりなく選べます。だから足すのではなく、掛け合わせる形になりました。数え方の向きが違います。
- ウ12：十二という数を挙げた肢が、こちらに当たります。どこかで数え方を取り違えた形になります。前も後ろも三通りなので、掛ければ九になりました。十二という数は、どちらの道からも出てきません。三通りずつが要です。掛ける相手が違います。
- エ20：二十という数を挙げた肢が、こちらに当たります。経る地点を通らない道まで、数えた形でした。上へ三回と右へ三回で、六回のうち三回を選びます。けれども設問は、経ると限っていました。数えすぎになります。限りを読み落とした形です。
出典：平成22年度 秋期 ITパスポート試験 問72（改変：原典の図表をテキストに書き起こした）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）