図のような碁盤の目の道路があり、すべての間隔が等しいとする。点Aから点Bへ行く最短経路のうち、点Cと点Dの両方を通るものは何通りあるか。

1. 問題の内容

図のような碁盤の目の道路があり、すべての間隔が等しいとする。点Aから点Bへ行く最短経路のうち、点Cと点Dの両方を通るものは何通りあるか。

2. 解き方の手順

点Aから点Bへ行く最短経路は、右方向への移動と上方向への移動のみで構成される。点Cと点Dの両方を通る経路は、A→C→D→B の順に移動する経路である。

* AからCへの最短経路の数：右に2回、上に1回移動する必要がある。これは $\binom{2+1}{1} = \binom{3}{1} = 3$ 通り。

* CからDへの最短経路の数：右に1回、上に2回移動する必要がある。これは $\binom{1+2}{1} = \binom{3}{1} = 3$ 通り。

* DからBへの最短経路の数：右に1回、上に1回移動する必要がある。これは $\binom{1+1}{1} = \binom{2}{1} = 2$ 通り。

したがって、点Aから点Bへの最短経路で、点Cと点Dの両方を通る経路の総数は、これらの経路の数の積で求められる。

$3 \times 3 \times 2 = 18$

上記は誤りである．CとDの両方を通る経路なので，Cを通ってDを通る場合と，Dを通ってCを通る場合がある．

AからCへ行く経路数：$\binom{3}{1}=3$

AからDへ行く経路数：$\binom{4}{1}=4$

CからBへ行く経路数：$\binom{4}{2}=6$

DからBへ行く経路数：$\binom{3}{2}=3$

CからDへ行く経路数：$\binom{3}{2}=3$

DからCへ行く経路は存在しない．

CとD両方を通る経路は，A→C→D→Bのみである．よって，

A→C：３通り

C→D：３通り

D→B：２通り

なので，3*3*2 = 18通り．

AからCを通ってDを通ってBに行く経路なので，

(A→C) * (C→D) * (D→B)

= $\binom{3}{1} \times \binom{3}{2} \times \binom{2}{1}$

= $3 \times 3 \times 2 = 18$ 通り

問題文をよく読むと,CとDのどちらも通ると書いてあるので、経由順序は考慮する必要はない。

(A->C)* (A->D)* (C->B)*(D->B)の最小経路を考える.

しかし、これは違う経路を重複して数えることになるので間違い。

AからBへのすべての経路は $\binom{7}{3}=35$

AからCを通るすべての経路は $\binom{3}{1} * \binom{4}{2} = 3 * 6 = 18$

AからDを通るすべての経路は $\binom{4}{1} * \binom{3}{2} = 4 * 3 = 12$

点Cと点Dの順序に言及はないので、A->C->D->BとA->D->C->Bの両方を通る経路を考える必要がある。

A->C->D->B: $3*3*2=18$

A->D->C->B: 通れない

A->C->D->Bのみなので、18通り。

3. 最終的な答え

18通り