解説

方針・初手

格子を座標で表す。地点 $O$ を $(0,0)$ とし，東向きを $x$ 軸の正方向，北向きを $y$ 軸の正方向とする。

このとき

$$ O=(0,0),\quad Q=(5,5),\quad S=(2,2),\quad T=(3,2),\quad V=(2,3),\quad U=(3,3),\quad W=(5,2)

$$

である。

$O$ から $Q$ への最短経路では，東へ $5$ 回，北へ $5$ 回だけ進む。したがって，経路数は東に進む位置の選び方として数えられる。

解法1

**(1)**

$O$ から $Q$ への最短経路の総数は

$$ {}_{10}\mathrm{C}_{5}=252

$$

である。

このうち，地点 $S$ を通る経路数を数える。

$O$ から $S=(2,2)$ までは東 $2$ 回，北 $2$ 回なので

$$ {}_{4}\mathrm{C}_{2}=6

$$

通りである。また，$S$ から $Q=(5,5)$ までは東 $3$ 回，北 $3$ 回なので

$$ {}_{6}\mathrm{C}_{3}=20

$$

通りである。よって，$S$ を通る経路数は

$$ 6\cdot 20=120

$$

である。

同様に，地点 $T=(3,2)$ を通る経路数は

$$ {}_{5}\mathrm{C}_{2}{}_{5}\mathrm{C}_{2}=10\cdot 10=100

$$

である。

ただし，$S$ と $T$ の両方を通る経路は重複して引かれる。最短経路では西や南には進まないので，両方を通る場合は必ず $S$ から $T$ の順に通る。

したがって，両方を通る経路数は

$$ {}_{4}\mathrm{C}_{2}\cdot 1\cdot {}_{5}\mathrm{C}_{2} =6\cdot 1\cdot 10 =60

$$

である。

よって，$S,T$ のいずれも通らない経路数は

$$ 252-120-100+60=92

$$

である。

**(2)**

$S,T,U,V$ のいずれも通らない最短経路を数える。地点 $(i,j)$ までの条件を満たす最短経路数を $a_{i,j}$ とおく。

通ってはいけない点では

$$ a_{2,2}=a_{3,2}=a_{2,3}=a_{3,3}=0

$$

とする。それ以外の点では，左または下から来るので

$$ a_{i,j}=a_{i-1,j}+a_{i,j-1}

$$

である。

まず，左端と下端では経路は一通りしかないので

$$ a_{0,j}=1,\quad a_{i,0}=1

$$

である。

禁止された $4$ 点の近くから順に計算する。

$$ a_{4,2}=a_{3,2}+a_{4,1}=0+5=5

$$

$$ a_{5,2}=a_{4,2}+a_{5,1}=5+6=11

$$

$$ a_{4,3}=a_{3,3}+a_{4,2}=0+5=5

$$

$$ a_{5,3}=a_{4,3}+a_{5,2}=5+11=16

$$

また，上側について

$$ a_{2,4}=a_{1,4}+a_{2,3}=5+0=5

$$

$$ a_{3,4}=a_{2,4}+a_{3,3}=5+0=5

$$

$$ a_{4,4}=a_{3,4}+a_{4,3}=5+5=10

$$

$$ a_{5,4}=a_{4,4}+a_{5,3}=10+16=26

$$

さらに

$$ a_{2,5}=a_{1,5}+a_{2,4}=6+5=11

$$

$$ a_{3,5}=a_{2,5}+a_{3,4}=11+5=16

$$

$$ a_{4,5}=a_{3,5}+a_{4,4}=16+10=26

$$

よって

$$ a_{5,5}=a_{4,5}+a_{5,4}=26+26=52

$$

である。

したがって，$S,T,U,V$ のいずれも通らない最短経路は $52$ 通りである。

**(3)**

地点 $W=(5,2)$ に到着するには，東へ $5$ 回，北へ $2$ 回進む必要がある。

ただし，$x=5$ に到達した時点で東方向の道がなくなるので，最後の一歩は必ず $(4,2)$ から $W=(5,2)$ へ進む東向きの一歩である。

したがって，その直前までの $6$ 歩では，東へ $4$ 回，北へ $2$ 回進んでいる。この並べ方は

$$ {}_{6}\mathrm{C}_{2}=15

$$

通りである。

各経路の確率は

$$ p^5q^2

$$

であるから，地点 $W$ に到着する確率は

$$ 15p^5q^2

$$

である。

**(4)**

総移動距離が $8$ 以上であるとは，少なくとも $7$ 歩進んだ時点ではまだ終了していないということである。

この試行は，東方向に $5$ 回進むか，北方向に $5$ 回進んだ時点で，右端または上端に達して終了する。

したがって，$7$ 歩進んでも終了していないためには，$7$ 歩の中で東が $5$ 回以上でも北が $5$ 回以上でもあってはならない。

$7$ 歩の合計が $7$ であるから，可能なのは東と北の回数が $3$ 回と $4$ 回に分かれる場合だけである。

よって，求める確率は

$$ {}_{7}\mathrm{C}_{3}p^3q^4+{}_{7}\mathrm{C}_{4}p^4q^3

$$

である。

ここで ${}_{7}\mathrm{C}_{3}={}_{7}\mathrm{C}_{4}=35$ より，

$$ {}_{7}\mathrm{C}_{3}p^3q^4+{}_{7}\mathrm{C}_{4}p^4q^3 =35p^3q^3(p+q)

$$

である。$p+q=1$ だから

$$ 35p^3q^3

$$

となる。

$x=pq$ より，

$$ 35p^3q^3=35(pq)^3=35x^3

$$

である。

解説

最短経路の問題では，まず「東に何回，北に何回進むか」を固定して，順列として数えるのが基本である。

（1） は，通ってはいけない点が $2$ つなので包除原理で処理できる。特に，$S$ と $T$ の両方を通る経路を足し戻す点が重要である。

（2） は，禁止点が $4$ つに増えて包除原理が煩雑になるため，漸化式で各交点までの経路数を求める方が安全である。

（3） と （4） は，確率の問題であるが，実質的には東と北の回数を数える問題である。境界に達した時点で終了するため，「最後の一歩」や「終了していない条件」を正確に見る必要がある。

答え

**(1)**

$$ 92

$$

**(2)**

$$ 52

$$

**(3)**

$$ 15p^5q^2

$$

**(4)**

$$ 35x^3

$$