大阪大学 1989年 理系 第5問 解説

方針・初手

全体の線分の本数を正確に数え上げることが第一歩である。さらに、$(0,0)$ から $(n,3)$ まで線分をたどって到達するための最短距離を考え、経路長とパリティ（偶奇性）に着目して条件を満たす線分の組み合わせを絞り込む。

解法1

線分の総数について

$S$ は $x$ 座標が $0, 1, \dots, n$、$y$ 座標が $0, 1, 2, 3$ の格子点である。

集合 $M$ に含まれる長さ $1$ の線分は、$x$ 軸に平行なものと $y$ 軸に平行なものに分けられる。

$x$ 軸に平行な線分は、各 $y=0,1,2,3$ （$4$ 通り）について、$x$ 座標が $1$ 増える区間が $n$ 個あるため、$4n$ 本存在する。

$y$ 軸に平行な線分は、各 $x=0,1,\dots,n$ （$n+1$ 通り）について、$y$ 座標が $1$ 増える区間が $3$ 個あるため、$3(n+1)$ 本存在する。

よって、$M$ の元の総数 $N$ は、

$$ N = 4n + 3(n+1) = 7n+3 $$

となる。

(1)

$7n+3$ 本の線分から相異なる $m$ 本を選ぶ選び方であるから、求める数は

$$ {}_{7n+3}\mathrm{C}_{m} \text{ 通り} $$

(2)

点 $(0,0)$ から点 $(n,3)$ まで線分を通って移動するときの最短距離は $n+3$ である。

したがって、$n+3$ 本の線分で $(0,0)$ と $(n,3)$ がつながるためには、選ばれた $n+3$ 本の線分が $(0,0)$ から $(n,3)$ への最短経路を形成しなければならない。

このような最短経路は、右に $n$ 回、上に $3$ 回進む順列の総数に等しく、その数は

$$ {}_{n+3}\mathrm{C}_{3} \text{ 通り} $$

各最短経路は $n+3$ 本の相異なる線分からなり、異なる最短経路は少なくとも $1$ 本は異なる線分を含むため、これらの線分集合はすべて異なる。

よって、条件を満たす $n+3$ 本の線分の選び方は ${}_{n+3}\mathrm{C}_{3}$ 通りであり、求める確率は

$$ \frac{{}_{n+3}\mathrm{C}_{3}}{{}_{7n+3}\mathrm{C}_{n+3}} $$

(3)

点 $(0,0)$ から点 $(n,3)$ を結ぶ経路（同じ頂点を $2$ 度通らない単純道）の長さを考える。

右、左、上、下へ進む回数をそれぞれ $x, x', y, y'$ とすると、$x - x' = n$、$y - y' = 3$ であるから、経路の長さ $L$ は

$$ L = x + x' + y + y' = (x - x') + (y - y') + 2(x' + y') = n + 3 + 2(x' + y') $$

となる。$x', y' \ge 0$ より、$L$ は $n+3, n+5, n+7, \dots$ となり、$n+3$ と同じ偶奇を持つ。

選ぶ線分は $n+4$ 本であるため、長さ $n+4$ の経路は存在しない。

よって、$n+4$ 本の線分で $(0,0)$ と $(n,3)$ がつながるためには、選ばれた線分の中に「長さ $n+3$ の最短経路（線分 $n+3$ 本）」がちょうど $1$ つ含まれ、残りの $1$ 本は経路外の線分でなければならない。

ここで、選ばれた $n+4$ 本の線分の中に $2$ つ以上の異なる最短経路が含まれる可能性について考える。

$2$ つの異なる最短経路 $P_1, P_2$ （ともに長さ $n+3$）について、これらが異なるためには少なくとも $1$ つの格子（$1 \times 1$ の正方形）の周上で異なる経路（一方が右→上、他方が上→右）を通る必要がある。

すなわち、$P_1$ と $P_2$ は少なくとも $2$ 本の線分が互いに異なるため、共有する線分の数は最大でも $(n+3) - 2 = n+1$ 本である。

よって、$P_1$ と $P_2$ に含まれる線分の和集合の本数は

$$ |P_1 \cup P_2| = |P_1| + |P_2| - |P_1 \cap P_2| \ge 2(n+3) - (n+1) = n+5 $$

となり、選ばれた $n+4$ 本の線分の中に $2$ つの最短経路が同時に含まれることはない。

したがって、条件を満たす $n+4$ 本の線分の選び方は、ある $1$ つの最短経路を構成する $n+3$ 本の線分を選び、さらにそれ以外の $N - (n+3)$ 本の線分から $1$ 本を選ぶ方法の総数に等しい。

これは経路ごとに重複なく数えられるため、求める選び方は

$$ {}_{n+3}\mathrm{C}_{3} \times \{ (7n+3) - (n+3) \} = 6n \cdot {}_{n+3}\mathrm{C}_{3} \text{ 通り} $$

以上より、求める確率は

$$ \frac{6n \cdot {}_{n+3}\mathrm{C}_{3}}{{}_{7n+3}\mathrm{C}_{n+4}} $$

解説

グラフ理論における「経路の長さとパリティ（偶奇性）」の性質が問われている。

格子点上の移動において、目的の点に到達する歩数は、最短距離と必ず偶奇が一致する。これに気づけば、（3） で経路長が $n+4$ になることはありえず、「最短経路＋無関係な $1$ 本の線分」という形しかないことが確信できる。

また、「複数の最短経路が同時に選ばれてしまうケース（重複）」の考慮も重要である。$2$ つの最短経路の和集合のサイズが $n+4$ を超えることを示せば、重複がないことが厳密に証明できる。

答え

(1)

$$ {}_{7n+3}\mathrm{C}_{m} \text{ 通り} $$

(2)

$$ \frac{{}_{n+3}\mathrm{C}_{3}}{{}_{7n+3}\mathrm{C}_{n+3}} $$

(3)

$$ \frac{6n \cdot {}_{n+3}\mathrm{C}_{3}}{{}_{7n+3}\mathrm{C}_{n+4}} $$