2北里大学 2020年 1日目 数学 第2問解答・解説

図の隣接関係は $P-A,\ A-B,\ A-D,\ B-C,\ C-D,\ C-Q$ である。

初期配置 $(B,D)$ から1回動かすと、各球の行先はそれぞれ $A,C$ の二択である。同じ点に着く2通りは除去され、異なる点に着く2通りは $\{A,C\}$ となる。したがって $\displaystyle X_1=\frac12$ で、生き残った球は $A,C$ にある。

次に $A$ からは $P,B,D$、$C$ からは $B,D,Q$ へ各 $1/3$ で動く。9通り中、同じ点となる $(B,B),(D,D)$ と $(P,Q)$ の3通りで除去されるから

$$\displaystyle X_2=\frac12\cdot\frac{6}{9}=\frac13.$$

2回目終了時の生存配置は $\{B,D\},\{P,B\},\{P,D\},\{B,Q\},\{D,Q\}$ のいずれかである（各配置への経路数は異なる）。この5配置のどれからでも、次の移動で異なる $A,C$ に分かれる確率は $1/2$ である。従って

$$\displaystyle X_3=X_2\cdot\frac12=\frac16.$$

グラフの頂点は二部に分かれ、片方が $\{A,C\}$、もう片方が $\{B,D,P,Q\}$ で、各移動で二部が交代する。奇数回終了時に生存していれば配置は必ず $\{A,C\}$ である。そこから2回の移動で生き残る確率は、まず $6/9$、次に直前の5配置のどれでも $1/2$ なので合計 $1/3.$

$\displaystyle X_1=\frac12$ を初項として $\displaystyle X_{2k+1}=\frac13X_{2k-1}\ (k\geq1)$。ゆえに $\displaystyle X_{2k-1}=\frac{1}{2\cdot3^{k-1}}.$

また、配置 $\{A,C\}$ から1回の移動でそれぞれ $P,Q$ に進む確率は $1/9$ である。従って第 $2k$ 回目に初めてこの理由で除去される確率は $X_{2k-1}/9=1/(18\cdot3^{k-1}).$

$m=\lfloor n/2\rfloor$ とおくと、求める確率は互いに排反な各回の確率の和であり

$$\displaystyle \sum\limits _{k=1}^{m}\frac{1}{18\cdot3^{k-1}}=\frac1{12}(1-3^{-m})=\frac{1}{12}\left(1-3^{-\lfloor n/2\rfloor}\right).$$