II慶應義塾大学 2008年 数学 第II問解答・解説

以下，$i$ 回後の位置を $(x_i,y_i)$ とする。

(1) $x$ 座標の変化は各回独立に $+1,-1$ がそれぞれ確率 $1/2$ で起こり，$y$ 座標も同様である。また，$x$ と $y$ の変化は独立である。$x_i$ がすべて $-1,0,1$ に留まるには，奇数時刻では $x_i=\pm1$，偶数時刻では $x_i=0$ となる必要がある。各奇数時刻には2通りの選択があり，各偶数時刻の移動は直前の符号を戻すものに限られる。したがって，一方の座標が $n$ 回すべて範囲内に留まる確率は $2^{\lceil n/2\rceil}/2^n=2^{-\lfloor n/2\rfloor}$ である。両座標の独立性から $$\displaystyle p_n=2^{-2\lfloor n/2\rfloor},\qquad p_{2m-1}=\frac1{4^{m-1}},\quad p_{2m}=\frac1{4^m}.$$

(2) $D_i=x_i-y_i$ とおく。条件 $0\le D_i\le2$ と，$D_i$ が偶数であることから，各 $i=1,\ldots,n$ で $D_i=0$ または $D_i=2$ となる。$D_i=0$ のとき，次の差の変化は $0$ が2通り，$+2$ が1通り，$-2$ が1通りであり，条件を保つ選択は3通りである。$D_i=2$ のときも，変化 $0$ が2通り，$-2$ が1通り，$+2$ が1通りなので，条件を保つ選択は3通りである。各回の4通りの移動は等確率で独立だから $$\displaystyle q_n=\left(\frac34\right)^n.$$

(3) $E_A$ を $A_n\subset A\cap U$，$E_B$ を $A_n\subset B\cap U$ とする。包除原理より $r_n=P(E_A)+P(E_B)-P(E_A\cap E_B)$ である。両方を満たすとき，平方内に留まる条件から奇数時刻の座標は $(\pm1,\pm1)$，偶数時刻の座標は $(0,0)$ となる。奇数時刻の4隅のうち，さらに $0\le x-y\le2$ を満たすのは $(-1,-1),(1,-1),(1,1)$ の3つである。偶数時刻には原点へ戻る移動が1通りに定まる。よって $$\displaystyle P(E_A\cap E_B)=\begin{cases} \dfrac{3^m}{4^{2m-1}}& (n=2m-1),\\[4pt] \dfrac{3^m}{4^{2m}}& (n=2m). \end{cases}$$ (1)(2)と合わせて $$\displaystyle r_{2m-1}=\frac1{4^{m-1}}+\left(\frac34\right)^{2m-1}-\frac{3^m}{4^{2m-1}},\qquad r_{2m}=\frac1{4^m}+\left(\frac34\right)^{2m}-\frac{3^m}{4^{2m}}.$$

(4)(5)の数え上げでは，$u=(x+y)/2,\ v=(x-y)/2$ とおく。この変換で4通りの移動は格子上の上下左右への移動に対応し，どの移動も確率 $1/4$ である。3つの訪問点を頂点，移動可能な隣接関係を辺とする。実際に訪問した3点をつなぐ辺は連結でなければならず，格子には三角形がないので，その形は3頂点の道（中央1点と両端2点）である。

$s_3$ では，1回目の位置は4通り，2回目の移動も4通りある。3回目に1回目の位置へ戻る1通りを除くと，3つの位置がすべて異なる移動は各組合せにつき3通りである。したがって $s_3=4\cdot4\cdot3/4^3=3/4$。また $s_1=s_2=0$ である。

$s_4$ では，最初の位置を固定する。これが3点の道の中央なら，両端の選び方は $\displaystyle \binom42=6$ 通りで，各道をすべて訪れる3歩の移動は2通りである。最初の位置が端なら，中央の選び方が4通り，もう一方の端の選び方が3通りで，各道をすべて訪れる3歩の移動は1通りである。最初の位置自体は4通りだから，有利な移動列は $4\{6\cdot2+12\cdot1\}=96$ 通り。よって $$\displaystyle s_4=\frac{96}{4^4}=\frac38.$$

一般に $n=2m\ (m\ge2)$ とする。最初の位置を固定し，その後の $2m-1$ 歩で3点の道をすべて訪れる移動列を数える。最初の位置が中央のとき，全移動列は $2^m$ 通りであり，片方の端を訪れない列は端と中央を往復する1通りずつなので，すべて訪れる列は $2^m-2$ 通りである。最初の位置が端のとき，全移動列は $2^{m-1}$ 通りで，反対側の端を訪れない列が1通りあるから，すべて訪れる列は $2^{m-1}-1$ 通りである。3点の道は中央を最初の位置に置くと $\displaystyle \binom42=6$ 通り，最初の位置を端に置くと $4\cdot3=12$ 通りである。したがって有利な移動列は $$4\left\{6(2^m-2)+12(2^{m-1}-1)\right\}=96(2^{m-1}-1)$$ 通りであり，全移動列 $4^{2m}$ 通りに対する確率は $$\displaystyle \boxed{s_{2m}=\frac{96(2^{m-1}-1)}{4^{2m}}=\frac{6(2^{m-1}-1)}{16^{m-1}}}.$$ $m=2$ を代入すると $s_4=3/8$ となり，上の結果と一致する。