トップ› 九州大学› 2002年› 理系第6問

九州大学 2002年理系第6問解説

方針・初手

右斜め $45^\circ$ または右斜め $-45^\circ$ への移動を繰り返すことから、この問題は座標平面上におけるランダムウォークの経路数を考える問題に帰着できます。まずは、各方向への移動回数を文字で置き、到達点の座標と移動回数の関係を立式して (1) を処理します。 (2) は「特定の直線をまたぐ（到達する）経路の数」を数えるための典型手法である「鏡像法（反射の原理）」を用います。終点の1歩手前の座標に着目して場合分けを行うのがポイントです。 (3) は条件付き確率の計算ですが、事象の補集合を考えると (2) の結果をそのまま適用できる構造になっていることに気づくことが最大の鍵となります。

解法1

(1)

原点 $O(0,0)$ から出発し、1回の移動で $x$ 座標は常に $1$ 増加し、$y$ 座標は $1$ 増加または $1$ 減少する。 $n$ 回の移動後に格子点 $(n, k)$ に到達する折れ線グラフにおいて、右斜め $45^\circ$（$y$ 座標が $+1$）の移動回数を $a$ 回、右斜め $-45^\circ$（$y$ 座標が $-1$）の移動回数を $b$ 回とする。 $a, b$ は $0$ 以上の整数であり、総移動回数と $y$ 座標の変位から、次の連立方程式が成り立つ。

$$\begin{cases} a + b = n \\ a - b = k \end{cases}$$

2式を辺々足し合わせると、

$$2a = n + k$$

となる。$a$ は整数であるから、$2a$ は偶数であり、したがって折れ線グラフが存在するためには $n+k$ が偶数であることが必要である。逆に、$n+k$ が偶数であれば、$a = \frac{n+k}{2}$、$b = \frac{n-k}{2}$ はともに整数となる。条件 $0 \leqq k \leqq n$ より、$n+k \geqq 0$ かつ $n-k \geqq 0$ であるため、$a \geqq 0$ かつ $b \geqq 0$ を満たし、条件を満たす折れ線グラフは確かに存在する。以上より、折れ線グラフが存在するための必要十分条件は $n+k$ が偶数であることである。（証明終）

また、この条件が満たされているとき、折れ線グラフの数は、$n$ 回の移動のうち右斜め $45^\circ$ への移動を $a = \frac{n+k}{2}$ 回選ぶ組み合わせの数に等しいから、

$${}_n\mathrm{C}_{\frac{n+k}{2}}$$

通りである。

(2)

原点 $O$ から $(n,k)$ を結ぶ折れ線グラフのうち、格子点 $(0,k), (1,k), \cdots, (n-2,k)$ の少なくとも1つを通る（すなわち途中で少なくとも一度直線 $y=k$ に到達する）経路の集合を $S$ とする。終点が $(n,k)$ である経路の1歩手前（$x=n-1$ のとき）の $y$ 座標は、$k+1$ または $k-1$ のいずれかである。これにしたがって、集合 $S$ を以下の2つの部分集合に分割する。

$S_1$: $1$ 歩手前が $(n-1, k+1)$ である経路の集合
$S_2$: $1$ 歩手前が $(n-1, k-1)$ である経路の集合

まず $S_1$ について考える。原点 $O(0,0)$ から出発し、$(n-1, k+1)$ に至る経路において、条件より $k \geqq 0$ だから $k+1 \geqq 1 > 0$ である。したがって、$y$ 座標が正である点に到達するためには、途中で必ず直線 $y=k$ を横切るか接する必要がある。よって、原点 $O$ と $(n-1, k+1)$ を結ぶすべての折れ線グラフは集合 $S_1$ に属する。ゆえに、$S_1$ の要素数は「原点 $O$ と格子点 $(n-1, k+1)$ を結ぶ折れ線グラフの数」に等しい。

次に $S_2$ について考える。 $S_2$ に属する経路は、原点 $O$ から途中で少なくとも一度 $y=k$ に到達し、その後 $(n-1, k-1)$ を経由して $(n,k)$ に至る経路である。このような経路に対して、最後に直線 $y=k$ に到達した格子点を $(m, k)$（$0 \leqq m \leqq n-2$）とする。 $(m, k)$ から $(n-1, k-1)$ までの部分経路を、直線 $y=k$ を軸として対称移動（折り返し）させると、$(m, k)$ から $(n-1, k+1)$ に至る部分経路と1対1に対応する。原点 $O$ から $(m,k)$ までの前半の経路はそのままとすることで、この経路は「原点 $O$ と格子点 $(n-1, k+1)$ を結ぶ折れ線グラフ」全体と1対1の対応がつく。ゆえに、$S_2$ の要素数も「原点 $O$ と格子点 $(n-1, k+1)$ を結ぶ折れ線グラフの数」に等しい。

以上より、求める折れ線グラフの数（$S$ の要素数）は $S_1$ と $S_2$ の要素数の和であり、どちらも同じ数であるから、原点 $O$ と格子点 $(n-1, k+1)$ を結ぶ折れ線グラフの数の2倍に等しい。（証明終）

(3)

事象 $E$ を「$T_9 = 3$ が起きる」、事象 $F$ を「どの $T_i$ ($i=0, 1, 2, \cdots, 7$) も $3$ にならない」とする。求める確率は、条件付き確率 $P(F \mid E)$ である。

(1) の結果より、事象 $E$ を満たす経路（原点と $(9,3)$ を結ぶ折れ線グラフ）の総数 $n(E)$ は、$n=9, k=3$ として、

$$n(E) = {}_9\mathrm{C}_{\frac{9+3}{2}} = {}_9\mathrm{C}_6 = \frac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 1} = 84$$

通りである。次に、事象 $E \cap \overline{F}$ について考える。これは「$T_9=3$ であり、かつ $i=0, 1, \cdots, 7$ の少なくとも1つの $i$ で $T_i=3$ となる」事象である。ここで、もし $T_8 = 3$ であると仮定すると、次の移動で $T_9 = 2$ または $T_9 = 4$ となり、$T_9 = 3$ に矛盾するため、事象 $E$ の下では必ず $T_8 \neq 3$ である。したがって、「$i=0, 1, \cdots, 7$ の少なくとも1つの $i$ で $T_i=3$ となる」ことは、「$i=0, 1, \cdots, 8$ の少なくとも1つの $i$ で $T_i=3$ となる」ことと同値である。すなわち、事象 $E \cap \overline{F}$ は「原点と格子点 $(9,3)$ を結ぶ折れ線グラフであって、途中の格子点 $(0,3), (1,3), \cdots, (7,3)$ の少なくとも1つを通る経路」を意味する。

これは (2) において $n=9, k=3$ とした状況に完全に一致する。 (2) の結果を用いれば、この事象を満たす経路の総数 $n(E \cap \overline{F})$ は、「原点と格子点 $(8, 4)$ を結ぶ折れ線グラフの数」の2倍に等しい。原点と格子点 $(8, 4)$ を結ぶ折れ線グラフの数は、(1) より

$${}_8\mathrm{C}_{\frac{8+4}{2}} = {}_8\mathrm{C}_6 = {}_8\mathrm{C}_2 = \frac{8 \cdot 7}{2 \cdot 1} = 28$$

通りである。したがって、

$$n(E \cap \overline{F}) = 28 \times 2 = 56$$

通りとなる。これより、事象 $E \cap F$ を満たす経路の総数 $n(E \cap F)$ は、全体から引くことで求められ、

$$n(E \cap F) = n(E) - n(E \cap \overline{F}) = 84 - 56 = 28$$

通りである。よって、求める条件つき確率 $P(F \mid E)$ は、

$$P(F \mid E) = \frac{n(E \cap F)}{n(E)} = \frac{28}{84} = \frac{1}{3}$$

となる。

解説

格子点上のランダムウォークにおいて「ある境界線（直線）に到達するかどうか」を判定する典型問題です。(2) の証明で用いた「直線に関する対称移動（折り返し）」の考え方は鏡像法や反射の原理と呼ばれ、カタラン数の導出などでも頻繁に用いられる極めて重要な手法です。 (3) は条件付き確率の計算ですが、終点の1歩手前で絶対に目標の直線上に乗らない（$T_8 \neq 3$）という事実を利用することで、事象の補集合が (2) で証明した命題の条件と完全に一致します。前の設問が次の設問の強力な誘導となっている、難関大らしい美しい構成の問題です。

答え

(1) 必要十分条件: $n+k$ が偶数であること（証明略）折れ線グラフの数: ${}_n\mathrm{C}_{\frac{n+k}{2}}$ （または $\frac{n!}{\left(\frac{n+k}{2}\right)!\left(\frac{n-k}{2}\right)!}$）

(2) 証明略

(3) $\frac{1}{3}$