数学A / 場合の数

指定の点を通り別の点を通らない最短経路

★★★★ 難関最短経路組合せ

問題

下の図のような碁盤の目の道がある。地点 $A$ から地点 $B$ まで最短距離で行く経路のうち、地点 $P$ を通り、かつ地点 $Q$ を通らない経路は何通りあるか。 $A = (0, 0)$ 、 $B = (5, 4)$ 、 $P = (2, 1)$ 、 $Q = (3, 3)$ とする。

A(0,0)→B(5,4) の碁盤。P(2,1)を通り Q(3,3)を通らない最短経路を数える

ヒントを見る

「 $P$ を通り $Q$ を通らない」=「 $P$ を通る」-「 $P$ も $Q$ も通る」。各区間 $A \to P$ 、 $P \to B$ などの経路数を組合せで数える。

解答・解説

方針

「 $P$ を通る経路」から「 $P$ と $Q$ の両方を通る経路」を引く。各区間の最短経路数は、右と上の移動回数から組合せで求める。

解答

⓪ 発想 — どう考え始めるか。 「 $P$ を通り $Q$ を通らない」は、直接数えず引き算で攻める。

「 $P$ を通る経路」から「 $P$ と $Q$ の両方を通る経路」を引けば、 $P$ を通るが $Q$ は通らない経路になる。

各区間の最短経路数は、右と上の移動回数の組合せ。 $A \to P$ 、 $P \to B$ 、 $P \to Q \to B$ をそれぞれ計算し、 $(A \to P \to B) - (A \to P \to Q \to B)$ を求める。

公式右に

p

回・上に

q

回進む最短経路は

_{p + q} C_{p}

通り。ある点を通る経路数 =(そこまで)×(そこから)

① $P$ を通る経路。 $A (0, 0) \to P (2, 1)$ は右 $2$ ・上 $1$ で $_{3} C_{2} = 3$ 通り。 $P (2, 1) \to B (5, 4)$ は右 $3$ ・上 $3$ で $_{6} C_{3} = 20$ 通り。よって

$3 \times 20 = 60 通り$

② $P$ と $Q$ の両方を通る経路。 $A \to P$ は $3$ 通り。 $P (2, 1) \to Q (3, 3)$ は右 $1$ ・上 $2$ で $_{3} C_{1} = 3$ 通り。 $Q (3, 3) \to B (5, 4)$ は右 $2$ ・上 $1$ で $_{3} C_{2} = 3$ 通り。よって

$3 \times 3 \times 3 = 27 通り$

③ 引く。

$60 - 27 = 33 通り$

まとめ:「通る・通らない」が混ざったら「通る全体 − 両方通る」の引き算。最短経路数は区間ごとに $_{p + q} C_{p}$ で出し、点を通る経路は掛け算でつなぐ。 $P$ を通る $60$ から、余分な「 $Q$ も通る $27$ 」を除いて $33$ 。

発展 — 一歩先へ。 格子の最短経路数は、各点に「左＋下」を足し込むパスカルの三角形そのもの。通行止め(通らない点)は、その点を $0$ にするだけで対応できる。これは動的計画法(DP)の最も基本的な例で、迷路の経路数え上げやロボットの経路計画の原型になっている。

答

$33$ 通り

別解

別解 — 格子の各点に経路数を書き込む(視覚で確実なルート)。 $A$ から各格子点までの最短経路数を、左下から順に書き込む(各点は「左の点＋下の点」の和)。ただし「 $Q$ を通らない」ので、 $Q (3, 3)$ の経路数を $0$ にしてから先へ進める。

まず $A (0, 0)$ から $P (2, 1)$ までの経路数は $(2 3) = 3$ 。ここからは「 $P$ を出発点」として、 $Q$ を封鎖しながら $B (5, 4)$ まで足し上げる。

$P$ に $3$ を置き、右・上へ和を伝播。 $Q (3, 3)$ に来たらそこを $0$ にリセット( $Q$ 経由を消す)。この“通行止め付き”の経路数え上げを $B$ まで続けると $B$ に $33$ が現れる。

引き算(本解) $60 - 27 = 33$ と同じ結果。格子に数を書き込む方法は、封鎖点が複数あっても「その点を $0$ にする」だけで対応でき、視覚的に確実。動的計画法(DP)の最も素朴な形だ。

ポイント

$P$ を通る $= 3 \times 20 = 60$ 、 $P$ も $Q$ も通る $= 3 \times 3 \times 3 = 27$ 。
$P$ を通り $Q$ を通らない $= 60 - 27 = 33$ 。

よくある間違い

「 $P$ を通り $Q$ を通らない」を直接数えようとする(「 $P$ 通る」 $-$ 「 $P$ と $Q$ 両方通る」)。
各区間の経路数 $(右右 + 上)$ の計算を誤る( $A \to P$ は右 $2$ ・上 $1$ で $(2 3) = 3$ )。
$P \to Q \to B$ を $P \to Q$ と $Q \to B$ の積で計算し忘れる。