数学A 場合の数 問題 21 解説

方針・初手

最短経路では、遠回りになる左向き・下向きの移動は使わない。したがって、基本的には「右へ進む回数」と「上へ進む回数」の並べ方を数えればよい。

ただし、中央付近に通れない道があるため、$A$ から $D$ へ直接行く場合は単純に二項係数だけでは数えられない。そこで、各交点までの最短経路数を順に足し上げる。

解法1

横方向を右に $x$、縦方向を上に $y$ とし、$A=(0,0)$ とおく。図より

$$ B=(5,2),\quad C=(4,3),\quad D=(5,7) $$

とみなせる。

（1） $A$ から $B$ を通って $D$ まで行く場合

まず、$A$ から $B$ までは右へ $5$ 回、上へ $2$ 回進む。

この範囲には通れない道の影響がないので、最短経路の数は

$$ {}_{7}\mathrm{C}_{2}=21 $$

である。

また、$B$ から $D$ までは右端の道を上にまっすぐ進むだけなので $1$ 通りである。

したがって、求める経路数は

$$ 21\cdot 1=21 $$

である。

（2） $A$ から $C$ を通って $D$ まで行く場合

まず、$A$ から $C$ までは右へ $4$ 回、上へ $3$ 回進む。

この部分も最短経路は通常の格子と同じように数えられるので、

$$ {}_{7}\mathrm{C}_{3}=35 $$

通りである。

次に、$C$ から $D$ までは右へ $1$ 回、上へ $4$ 回進む。右へ進むタイミングを $5$ 回の移動のうちどこに置くかを考えればよいので、

$$ {}_{5}\mathrm{C}_{1}=5 $$

通りである。

したがって、求める経路数は

$$ 35\cdot 5=175 $$

である。

（3） $A$ から $D$ まで行く場合

$A$ から各交点までの最短経路数を順に足し上げる。

中央の通れない道の影響が出る前までは、通常の格子と同じである。特に、

$$ N(4,3)={}_{7}\mathrm{C}_{3}=35,\quad N(5,2)={}_{7}\mathrm{C}_{2}=21 $$

である。

よって、右下側では

$$ N(5,3)=N(4,3)+N(5,2)=35+21=56 $$

となる。

中央部分では、通れない道をまたいで数を足してはいけない。そのため、通れる道だけを使って次のように計算する。

$$ \begin{aligned} N(4,4)&=N(4,3)=35,\\ N(5,4)&=N(4,4)+N(5,3)=35+56=91,\\ N(1,5)&={}_{6}\mathrm{C}_{1}=6,\\ N(2,5)&=6,\\ N(3,5)&=6,\\ N(4,5)&=N(3,5)+N(4,4)=6+35=41,\\ N(5,5)&=N(4,5)+N(5,4)=41+91=132. \end{aligned} $$

さらに上側は、通れる道に沿って同じように足し上げる。

$$ \begin{aligned} N(0,6)&=1,\\ N(1,6)&=1+6=7,\\ N(2,6)&=7+6=13,\\ N(3,6)&=13+6=19,\\ N(4,6)&=19+41=60,\\ N(5,6)&=60+132=192. \end{aligned} $$

最後の段も同様に、

$$ \begin{aligned} N(0,7)&=1,\\ N(1,7)&=1+7=8,\\ N(2,7)&=8+13=21,\\ N(3,7)&=21+19=40,\\ N(4,7)&=40+60=100,\\ N(5,7)&=100+192=292. \end{aligned} $$

したがって、$A$ から $D$ までの最短経路は

$$ 292 $$

通りである。

解説

最短経路の問題では、まず「最短ならどの方向にしか進めないか」を確認することが重要である。この問題では、$A$ から $D$ へ向かう最短経路では右向き・上向きの移動だけを使う。

途中に通れない道がなければ、移動回数の並べ方として二項係数で数えられる。しかし、中央部分に通れない道があるため、$A$ から $D$ へ直接行く場合は単純に

$$ {}_{12}\mathrm{C}_{5} $$

としてはいけない。

一方、$B$ や $C$ を通る条件付きの問題では、区間ごとに分けて数え、それらを掛け合わせればよい。

答え

(1)

$A$ から $B$ を通って $D$ まで行く最短経路は

$$ 21 $$

通り。

(2)

$A$ から $C$ を通って $D$ まで行く最短経路は

$$ 175 $$

通り。

(3)

$A$ から $D$ まで行く最短経路は

$$ 292 $$

通り。