平成27年度 秋期 午前 問2
離散数学
点Qに至る最短経路
図の線上を，点Pから点Rを通って，点Qに至る最短経路は何通りあるか。
図（書き起こし）: 格子の図（絵）。線を数えて書き起こした構造は次のとおり。
長方形の格子。横に 5 区画・縦に 4 区画（＝縦線が 6 本・横線が 5 本）。 P … 格子の左下の角（黒丸） Q … 格子の右上の角（黒丸） R … 格子の内部の交点（黒丸）。P から見て 右へ 2・上へ 2 の位置 移動できるのは格子の線上だけで，最短経路なので右または上へだけ進む。
- ア16
- イ24
- ウ32
- エ60
答えと解説を見る
✓ これが正解エ60
解説
PからRまでとRからQまでを数えて掛けます。
最短経路なので、進む向きは右か上のどちらかに限られます。ですから道順の数は、右へ進む回数と上へ進む回数の並べ方が何通りあるかで決まります。途中の点を必ず通るという条件が付いているので、経路を前半と後半の2つに区切って考えます。前半は右へ2回・上へ2回の並べ方、後半は右へ3回・上へ2回の並べ方です。ここで軸になるのは2つです。1つ目は区画の数を図から正しく読み取ること、2つ目は前半と後半を掛け合わせるのか足し合わせるのかです。前半のどの道を選んでも後半のすべての道が続けられるので、結び付け方は掛け算になります。前半は6通り、後半は10通りで、合わせて60通りです。
ほかの選択肢はなぜ違うのか
- ア16：6通りと10通りを掛けずに足すと、この値になります。区切った2つの区間はつなげて1本の道になるので、加える数え方では場合の数が足りなくなります。
- イ24：縦の区画を1つ少なく数えると、後半が右へ3回・上へ1回の4通りに減り、前半との積が24になります。格子の縦線と横線の本数を数え直すと避けられます。
- ウ32：6通りと10通りという2つの値からは、掛けても足してもこの数は出てきません。区切る点は図で指定されているため、別の分け方に置き換えることもできません。
出典：平成27年度 秋期 基本情報技術者試験 午前 問2（改変：原典の図表をテキストに書き起こした）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）