トップ› 九州大学› 2002年› 文系第8問

九州大学 2002年文系第8問解説

方針・初手

右斜め上への移動と右斜め下への移動を繰り返す、いわゆるランダムウォークの経路数の問題である。 (1) は各移動の回数を文字でおき、連立方程式を立てて到達条件と組み合わせの数を求める定石問題。 (2) は「反射の原理（鏡像法）」を用いて経路の数を対応させる有名な手法の証明である。ある直線（ここでは $y=k$）に到達した以降、または以前の経路を折り返すことで、別の終点への経路と一対一対応をつくる。 (3) は条件つき確率であるが、(2) の結果をそのまま利用して「途中で目標値に到達してしまう経路数（余事象）」を求めることで、計算を大幅に短縮できる誘導となっている。

解法1

(1)

原点からの1回の移動で、$x$ 座標は常に $+1$ される。 $n$ 回の移動のうち、右上（$y$ 方向に $+1$）への移動が $a$ 回、右下（$y$ 方向に $-1$）への移動が $b$ 回あったとする。$a, b$ は $a+b=n$ を満たす非負の整数である。このとき、到達する格子点の $y$ 座標は $a - b$ となる。したがって、原点から格子点 $(n, k)$ を結ぶ折れ線グラフが存在するための条件は、

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

を満たす非負の整数 $a, b$ が存在することである。この連立方程式を解くと、

$$a = \frac{n+k}{2}, \quad b = \frac{n-k}{2}$$

となる。 $a, b$ が整数となるためには、$n+k$ と $n-k$ がともに偶数であることが必要である。$n+k$ と $n-k$ の差は $2k$ （偶数）であるため、両者の偶奇は必ず一致する。したがって、$n+k$ が偶数であることが必要十分条件となる。（なお、条件 $0 \leqq k \leqq n$ より、$n+k \geqq 0$ かつ $n-k \geqq 0$ が成り立つため、$a \geqq 0, b \geqq 0$ は常に満たされる。）

この条件が満たされているとき、折れ線グラフの総数は、$n$ 回の移動のうち右上への移動を $a$ 回選ぶ組み合わせの数に等しい。したがって、求める数は

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

である。

(2)

原点から $(n, k)$ に至る折れ線グラフを考える。終点 $(n, k)$ の直前（$n-1$ 番目）の格子点は、$(n-1, k-1)$ または $(n-1, k+1)$ のいずれかである。問題文の「格子点 $(0, k), (1, k), \dots, (n-2, k)$ の少なくとも1つを通る」という条件は、「$(n, k)$ に到達するより前に、少なくとも1回は直線 $y=k$ 上の点を通る」と言い換えられる。条件を満たす折れ線グラフを、直前の格子点によって次の2つのグループに分ける。

(i) $(n-1, k+1)$ を経由して $(n, k)$ に至る経路

始点の $y$ 座標は $0$ であり、途中で $y=k+1$ の点に到達する。$y$ 座標は1回の移動で $\pm 1$ しか変化しないため、$y=0$ から $y=k+1 (> k)$ へ至る過程で、必ずどこかで直線 $y=k$ 上の点を通過する。したがって、原点から $(n-1, k+1)$ を経由して $(n, k)$ に至る経路はすべて条件を満たす。この経路の総数は、原点から $(n-1, k+1)$ に至る折れ線グラフの数に等しく、(1) の結果を利用すると

$${}_{n-1} \mathrm{C}_{\frac{(n-1)+(k+1)}{2}} = {}_{n-1} \mathrm{C}_{\frac{n+k}{2}}$$

である。

(ii) $(n-1, k-1)$ を経由して $(n, k)$ に至る経路のうち、途中で直線 $y=k$ に触れる経路

このような経路において、初めて直線 $y=k$ 上に到達する格子点を $P$ とする。原点から $(n-1, k-1)$ に至る経路のうち、点 $P$ から $(n-1, k-1)$ までの部分を、直線 $y=k$ を軸として対称に折り返す（反射させる）。 $(n-1, k-1)$ は直線 $y=k$ に関して $(n-1, k+1)$ と対称であるため、折り返された経路の終点は $(n-1, k+1)$ となる。この操作により、「途中で初めて直線 $y=k$ に到達し、$(n-1, k-1)$ に至る経路」は、「原点から $(n-1, k+1)$ に至る経路（これは必ず途中で $y=k$ を通る）」と1対1に対応する。したがって、このグループに属する経路の総数も、原点から $(n-1, k+1)$ に至る折れ線グラフの数に等しく、

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

である。

(i) と (ii) は互いに排反であるから、条件を満たす折れ線グラフの総数はこれらの和となる。

$${}_{n-1} \mathrm{C}_{\frac{n+k}{2}} + {}_{n-1} \mathrm{C}_{\frac{n+k}{2}} = 2 \times {}_{n-1} \mathrm{C}_{\frac{n+k}{2}}$$

以上より、求める数は原点 $O$ と格子点 $(n-1, k+1)$ を結ぶ折れ線グラフの数の2倍に等しいことが示された。

(3)

事象 $A$ を「$T_9 = 3$ が起きる」、事象 $B$ を「どの $T_i$ $(i=0, 1, \dots, 7)$ も $3$ にならない」とする。求める確率は、条件つき確率 $P_A(B) = \frac{n(A \cap B)}{n(A)}$ である。

なお、(1) の必要十分条件より、$n+k$ が偶数でないと格子点には到達できない。$i=8$ で $T_8=3$ となる場合、$8+3=11$（奇数）となるため、格子点 $(8, 3)$ に到達することはあり得ない。したがって、「どの $T_i$ $(i=0, \dots, 7)$ も $3$ にならない」という条件は「$T_9=3$ となる直前まで一度も $3$ にならない」ことと同値である。

まず、$n(A)$ について考える。これは原点から $(9, 3)$ を結ぶ折れ線グラフの総数であり、(1) より $n=9, k=3$ として

$$n(A) = {}_9 \mathrm{C}_{\frac{9+3}{2}} = {}_9 \mathrm{C}_6 = 84$$

である。

次に、$n(A \cap \overline{B})$ を考える。これは「$(9, 3)$ に到達する経路のうち、途中で $(0, 3), (1, 3), \dots, (7, 3)$ の少なくとも1つを通る」経路の総数である。ここで (2) の結果を利用する。$n=9, k=3$ とすると、$n \geqq 2$ であり、$k \leqq n-2$（$3 \leqq 7$）、さらに $n+k=12$ で偶数となるため、(2) の条件をすべて満たす。したがって、この経路の総数は、原点と $(9-1, 3+1) = (8, 4)$ を結ぶ折れ線グラフの数の2倍に等しい。原点と $(8, 4)$ を結ぶ折れ線グラフの数は、(1) より

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

であるから、

$$n(A \cap \overline{B}) = 2 \times 28 = 56$$

となる。

ゆえに、条件を満たす経路の総数 $n(A \cap B)$ は、全体から余事象を引いて

$$n(A \cap B) = n(A) - n(A \cap \overline{B}) = 84 - 56 = 28$$

である。

以上より、求める条件つき確率は

$$P_A(B) = \frac{n(A \cap B)}{n(A)} = \frac{28}{84} = \frac{1}{3}$$

となる。

解説

カタラン数やランダムウォークに関連する「反射の原理（鏡像法）」をテーマにした良問である。 (2) で経路の折り返しによる一対一対応を証明させ、(3) でそれを具体値に適用するという親切な誘導になっている。反射の原理は、途中で特定の直線に「触れてはいけない」または「触れる」経路の数を数える際に絶大な威力を発揮する。この考え方を知らないと (2) の証明で戸惑う可能性が高いが、図を書いて折り返してみるという発想に至れれば自然と解き進められる。