京都大学 1998年度後期・理系数学後期第5問解答・解説

問題

点 $A_{i} (i, 1), B_{i} (i, 2)$ $(i = 1, \dots, n)$ を考える．横辺 $A_{i} A_{i + 1}, B_{i} B_{i + 1}$ には独立に確率 $p$ で右向き矢印、確率 $1 - p$ で×印が描かれ、縦辺 $A_{i} B_{i}$ には常に上向き矢印が描かれる． $A_{1}$ から矢印に従って $B_{n}$ に至る経路が少なくとも1本存在する確率を $Q_{n}$ とする．

(1) $Q_{2}, Q_{3}$ を求めよ．

(2) $Q_{n}$ を求めよ．

出典：京都大学 1998年度後期日程第2次学力試験後期・理系後期第5問

方針

経路はある列 $i$ で縦辺を上がる形に限られる。上段で最初に通れない横辺の位置を分類し、その位置以後の下段横辺がすべて通れる条件を数える。

解答

経路が存在するためには、ある $i$ $(1 ≦ i ≦ n)$ について

A_{1} \to A_{2} \to \dots \to A_{i}, A_{i} \to B_{i}, B_{i} \to B_{i + 1} \to \dots \to B_{n}

のすべての横辺が通れればよい。

上段の横辺を左から見て、最初に×印が現れる位置を $t$ とする。すなわち $1 ≦ t ≦ n - 1$ のとき、上段の第1辺から第 $t - 1$ 辺までは矢印、第 $t$ 辺は×印である。この確率は

p^{t - 1} (1 - p)

である。この場合、縦辺を上がる列は $i ≦ t$ でなければならない。経路が存在するための必要十分条件は、下段の第 $t$ 辺から第 $n - 1$ 辺までがすべて矢印であることであり、その確率は $p^{n - t}$ である。 $t$ より左の下段の状態は問わない。

上段に×印が1つもない場合は確率 $p^{n - 1}$ であり、列 $n$ で縦辺を上がれば必ず到達できる。従って

Q_{n} = t = 1 \sum n - 1 p^{t - 1} (1 - p) p^{n - t} + p^{n - 1} = (n - 1) (1 - p) p^{n - 1} + p^{n - 1} = p^{n - 1} {1 + (n - 1) (1 - p)} .

(1)

特に

Q_{2} = p (2 - p), Q_{3} = p^{2} (3 - 2 p) .

(2)

Q_{n} = p^{n - 1} {1 + (n - 1) (1 - p)} .

京都大学 1998年度後期・理系数学 後期 第5問

問題

方針

解答

(1)

(2)

京都大学 1998年度
後期・理系数学後期第5問