トップ› 東京工業大学› 2018年› 理系第5問

東京工業大学 2018年理系第5問解説

方針・初手

点 $X$ が $1$ 秒ごとに隣の頂点へ移動するというルールから、時間の経過とともに存在する頂点群が切り替わる「パリティ（偶奇性）」に気づくことが重要である。頂点の座標の和 $x+y+z$ は移動のたびに偶奇が反転するため、$n$ が偶数か奇数かによって点 $X$ が存在する頂点が限定される。 (1)は $2$ 秒間の確率の推移を隣接する頂点を経由して直接計算する。(2)(3)は(1)の漸化式の形から連立漸化式として解くか、あるいは各座標が独立に変化する確率とみなして解く方針が考えられる。

解法1

点 $X$ の座標を $(x, y, z)$ とする。$1$ 秒移動するごとに $x, y, z$ のいずれか $1$ つだけが $1$ 増減するため、座標の和 $x+y+z$ の偶奇は $1$ 秒ごとに反転する。初期位置 $A(0,0,0)$ は $x+y+z=0$（偶数）であるから、$n$ が偶数のとき、点 $X$ は $x+y+z$ が偶数である頂点 $A(0,0,0), B(1,1,0), C(1,0,1), D(0,1,1)$ のいずれかに存在する。 $n$ が奇数のとき、点 $X$ は $x+y+z$ が奇数である頂点 $P_x(1,0,0), P_y(0,1,0), P_z(0,0,1), E(1,1,1)$ のいずれかに存在する。したがって、$n$ が奇数のとき、点 $X$ が $A, B, C, D$ に存在する確率は $0$ であり、$a_n = b_n = c_n = d_n = 0$ である。

(1)

$n$ 秒後に点 $X$ が $A, B, C, D$ にいる確率がそれぞれ $a_n, b_n, c_n, d_n$ である。 $n+1$ 秒後に点 $X$ が $P_x, P_y, P_z$ にいる確率をそれぞれ求める。点 $X$ が $P_x(1,0,0)$ に移動してくるのは、$A, B, C$ から移動する場合である。移動方向と確率を考慮すると、 $A \to P_x$（$x$ 軸方向）：確率 $p$ $B \to P_x$（$y$ 軸方向）：確率 $q$ $C \to P_x$（$z$ 軸方向）：確率 $r$ よって、$n+1$ 秒後に $P_x$ にいる確率は $p a_n + q b_n + r c_n$ である。

同様に、$n+1$ 秒後に $P_y(0,1,0)$ にいる確率は、隣接する $A, B, D$ からの移動を考えて $q a_n + p b_n + r d_n$ となる。 $n+1$ 秒後に $P_z(0,0,1)$ にいる確率は、隣接する $A, C, D$ からの移動を考えて $r a_n + p c_n + q d_n$ となる。

$n+2$ 秒後に $A(0,0,0)$ にいるためには、$n+1$ 秒後に $P_x, P_y, P_z$ のいずれかにいて、そこから $A$ へ移動すればよい。それぞれの確率は、$P_x \to A$ が $p$、$P_y \to A$ が $q$、$P_z \to A$ が $r$ であるから、

$$ \begin{aligned} a_{n+2} &= p(p a_n + q b_n + r c_n) + q(q a_n + p b_n + r d_n) + r(r a_n + p c_n + q d_n) \\ &= (p^2+q^2+r^2)a_n + 2pq b_n + 2pr c_n + 2qr d_n \end{aligned} $$

(2)

(1) と同様にして、$b_{n+2}, c_{n+2}, d_{n+2}$ を求める。 $n+1$ 秒後に $E(1,1,1)$ にいる確率は、隣接する $B, C, D$ からの移動を考えて $r b_n + q c_n + p d_n$ となる。

$n+2$ 秒後に $B(1,1,0)$ にいるのは、$n+1$ 秒後に隣接する $P_x, P_y, E$ にいる場合である。 $P_x \to B$ が $q$、$P_y \to B$ が $p$、$E \to B$ が $r$ であるから、

$$ \begin{aligned} b_{n+2} &= q(p a_n + q b_n + r c_n) + p(q a_n + p b_n + r d_n) + r(r b_n + q c_n + p d_n) \\ &= 2pq a_n + (p^2+q^2+r^2)b_n + 2qr c_n + 2pr d_n \end{aligned} $$

同様の計算により、$c_{n+2}, d_{n+2}$ は以下のようになる。

$$ c_{n+2} = 2pr a_n + 2qr b_n + (p^2+q^2+r^2)c_n + 2pq d_n $$

$$ d_{n+2} = 2qr a_n + 2pr b_n + 2pq c_n + (p^2+q^2+r^2)d_n $$

これらを用いて $a_{n+2} - b_{n+2} + c_{n+2} - d_{n+2}$ を計算する。

$$ \begin{aligned} &a_{n+2} - b_{n+2} + c_{n+2} - d_{n+2} \\ &= (p^2+q^2+r^2 - 2pq + 2pr - 2qr)a_n \\ &\quad + (2pq - p^2-q^2-r^2 + 2qr - 2pr)b_n \\ &\quad + (2pr - 2qr + p^2+q^2+r^2 - 2pq)c_n \\ &\quad + (2qr - 2pr + 2pq - p^2-q^2-r^2)d_n \\ &= (p-q+r)^2 a_n - (p-q+r)^2 b_n + (p-q+r)^2 c_n - (p-q+r)^2 d_n \\ &= (p-q+r)^2 (a_n - b_n + c_n - d_n) \end{aligned} $$

数列 $\{ a_n - b_n + c_n - d_n \}$ は、偶数番目、奇数番目それぞれで公比 $(p-q+r)^2$ の等比数列となる。 $n=0$ のとき、点 $X$ は $A$ にいるため $a_0 = 1, b_0 = c_0 = d_0 = 0$ であり、$a_0 - b_0 + c_0 - d_0 = 1$。よって、$n$ が偶数のとき、$a_n - b_n + c_n - d_n = ( (p-q+r)^2 )^{\frac{n}{2}} = (p-q+r)^n$ である。 $n$ が奇数のときは、前述の通り $a_n = b_n = c_n = d_n = 0$ であるから、$a_n - b_n + c_n - d_n = 0$ となる。

(3)

(2) と同様に、$a_{n+2} - b_{n+2} - c_{n+2} + d_{n+2}$ と $a_{n+2} + b_{n+2} - c_{n+2} - d_{n+2}$ を計算すると、以下の漸化式が得られる。

$$ a_{n+2} - b_{n+2} - c_{n+2} + d_{n+2} = (-p+q+r)^2 (a_n - b_n - c_n + d_n) $$

$$ a_{n+2} + b_{n+2} - c_{n+2} - d_{n+2} = (p+q-r)^2 (a_n + b_n - c_n - d_n) $$

$n=0$ における値はいずれも $1$ であるから、$n$ が偶数のとき、

$$ a_n - b_n - c_n + d_n = (-p+q+r)^n $$

$$ a_n + b_n - c_n - d_n = (p+q-r)^n $$

が成り立つ。さらに、$n$ が偶数のとき、点 $X$ は必ず $A, B, C, D$ のいずれかにいるため、

$$ a_n + b_n + c_n + d_n = 1 $$

である。得られた $4$ つの式を辺々足し合わせると、

$$ 4a_n = 1 + (p-q+r)^n + (-p+q+r)^n + (p+q-r)^n $$

よって、$n$ が偶数のとき、

$$ a_n = \frac{1}{4} \{ 1 + (-p+q+r)^n + (p-q+r)^n + (p+q-r)^n \} $$

$n$ が奇数のときは $a_n = 0$ である。

解法2

各座標の独立した変化に着目して (2) と (3) を解く。

(2)

点 $X$ の時刻 $n$ における座標を $(x_n, y_n, z_n)$ とする。 $1$ 秒経過するごとに、$y$ 座標が反転する確率は $q$、反転しない（$x$ または $z$ が反転する）確率は $p+r = 1-q$ である。 $n$ 秒後に $y_n = 0$ となる確率を $P(y_n=0)$ とすると、推移について以下が成り立つ。

$$ P(y_{n+1}=0) = (1-q)P(y_n=0) + q(1-P(y_n=0)) = (1-2q)P(y_n=0) + q $$

これを変形すると、

$$ P(y_{n+1}=0) - \frac{1}{2} = (1-2q) \left( P(y_n=0) - \frac{1}{2} \right) $$

初期位置は $A(0,0,0)$ なので $P(y_0=0) = 1$ である。よって、

$$ P(y_n=0) - \frac{1}{2} = \frac{1}{2}(1-2q)^n $$

ここで、$p+q+r=1$ より $1-2q = p+q+r-2q = p-q+r$ であるから、

$$ P(y_n=0) = \frac{1}{2} \{ 1 + (p-q+r)^n \} $$

また、$P(y_n=1) = 1 - P(y_n=0)$ より、

$$ P(y_n=0) - P(y_n=1) = (p-q+r)^n $$

$n$ が偶数のとき、点 $X$ は $A(0,0,0), B(1,1,0), C(1,0,1), D(0,1,1)$ のいずれかに存在する。このうち、$y$ 座標が $0$ であるのは $A, C$、$1$ であるのは $B, D$ であるから、

$$ P(y_n=0) = a_n + c_n, \quad P(y_n=1) = b_n + d_n $$

よって、$n$ が偶数のとき、

$$ a_n - b_n + c_n - d_n = P(y_n=0) - P(y_n=1) = (p-q+r)^n $$

$n$ が奇数のときは、解法1の冒頭の通り $0$ となる。

(3)

(2) と同様に $x$ 座標、$z$ 座標の反転確率に着目すると、$n$ が偶数のとき、

$$ P(x_n=0) - P(x_n=1) = (1-2p)^n = (-p+q+r)^n $$

$$ P(z_n=0) - P(z_n=1) = (1-2r)^n = (p+q-r)^n $$

$x$ 座標が $0$ なのは $A, D$、$1$ なのは $B, C$ であるから $a_n - b_n - c_n + d_n = (-p+q+r)^n$ $z$ 座標が $0$ なのは $A, B$、$1$ なのは $C, D$ であるから $a_n + b_n - c_n - d_n = (p+q-r)^n$ また $a_n + b_n + c_n + d_n = 1$ であり、これらと (2) の結果をすべて足し合わせると、

$$ 4a_n = 1 + (-p+q+r)^n + (p-q+r)^n + (p+q-r)^n $$

が得られる。$n$ が奇数のときは $a_n = 0$ である。

解説

立体上のランダムウォークにおいて、移動方向の確率が非対称な問題である。解法1のように隣接する状態からの推移を愚直に追うことで規則性を見出し、連立漸化式に帰着させるのが最も標準的な方針である。(2)の式変形が(3)のヒントになっており、符号の組み合わせを変えたものを自ら作り出して連立させるのがポイントである。一方で、解法2のように「各座標が独立した確率で反転する」と捉え直すと、非常に見通しよく解くことができる。立方体上の推移問題における強力な定石なので、別解の考え方も理解しておくとよい。いずれの方針をとるにせよ、時間 $n$ の偶奇による存在可能な頂点の場合分け（パリティ）を忘れないことが重要である。