トップ› 東京大学› 2012年› 理系第2問

東京大学 2012年理系第2問解説

方針・初手

9つの小正三角形の部屋を、図における三角形の向きによって「下向きの部屋」と「上向きの部屋」に分類する。球は辺を越えて移動するため、1回の移動で必ず異なる向きの部屋へ移る。この性質から、移動回数（経過秒数）の偶奇によって球が存在し得る部屋の向きが限定されることに着目する。次に、偶数秒後の状態について、下向きの部屋から出発して2秒後にどの下向きの部屋にいるかという推移確率を求め、漸化式を立てて解く。

解法1

図の9つの小正三角形の部屋を、その向きによって「下向きの部屋」と「上向きの部屋」に分類する。下向きの部屋は図から3つあり、これらを $P, Q, R$ とおく（$R$ は一番下の段の左から2番目の部屋）。上向きの部屋は6つある。

隣り合う部屋は必ず向きが異なるため、球は1秒ごとに「下向きの部屋」と「上向きの部屋」を交互に移動する。球は下向きの部屋 $P$ を出発するため、$n$ 秒後に下向きの部屋 $Q$ に存在するためには、$n$ が偶数であることが必要である。よって、$n$ が奇数のとき、球が部屋 $Q$ にある確率は $0$ である。

以下、$n$ が偶数のときを考える。$n = 2k$（$k$ は $0$ 以上の整数）とおく。任意の下向きの部屋（たとえば $P$）から出発して、2秒後に各下向きの部屋にいる確率を調べる。 $P$ に隣接する上向きの部屋は3つある。これらを、大きな正三角形の頂点を含む部屋 $U_1$ と、辺に接するが頂点を含まない部屋 $U_2, U_3$ とする。球が $P$ にいるとき、1秒後にはこれら3つの部屋のいずれかに等確率 $\frac{1}{3}$ で移動する。

さらに1秒後（出発から2秒後）の移動を考える。 $U_1$ に隣接する部屋は $P$ しかないため、球が $U_1$ にいる場合は確率 $1$ で $P$ に戻る。 $U_2$ に隣接する下向きの部屋は $P$ と $R$ の2つであるため、球が $U_2$ にいる場合は確率 $\frac{1}{2}$ ずつで $P$ または $R$ に移動する。 $U_3$ に隣接する下向きの部屋は $P$ と $Q$ の2つであるため、球が $U_3$ にいる場合は確率 $\frac{1}{2}$ ずつで $P$ または $Q$ に移動する。

したがって、$P$ から出発して2秒後に各部屋にいる確率は以下のようになる。

$$ \begin{aligned} P \text{に戻る確率} &= \frac{1}{3} \times 1 + \frac{1}{3} \times \frac{1}{2} + \frac{1}{3} \times \frac{1}{2} = \frac{2}{3} \\ R \text{に移動する確率} &= \frac{1}{3} \times 0 + \frac{1}{3} \times \frac{1}{2} + \frac{1}{3} \times 0 = \frac{1}{6} \\ Q \text{に移動する確率} &= \frac{1}{3} \times 0 + \frac{1}{3} \times 0 + \frac{1}{3} \times \frac{1}{2} = \frac{1}{6} \end{aligned} $$

他の下向きの部屋 $Q, R$ から出発した場合も、隣接する上向きの部屋の構成（頂点を含む部屋1つ、含まない部屋2つ）は等しいため、2秒後の推移確率は同様になる。すなわち、どの下向きの部屋から出発しても、2秒後には確率 $\frac{2}{3}$ で元の部屋に戻り、確率 $\frac{1}{6}$ ずつで他の2つの下向きの部屋に移動する。

$2k$ 秒後に球が部屋 $Q$ にある確率を $q_k$ とする。状態の対称性から、$2k$ 秒後に部屋 $Q$ 以外の2つの下向きの部屋（$P$ または $R$）にある確率は合わせて $1 - q_k$ である。したがって、$2(k+1)$ 秒後に部屋 $Q$ にある確率 $q_{k+1}$ は、次のように表される。

$$ q_{k+1} = \frac{2}{3} q_k + \frac{1}{6} (1 - q_k) $$

これを整理する。

$$ q_{k+1} = \frac{1}{2} q_k + \frac{1}{6} $$

この漸化式を変形すると以下のようになる。

$$ q_{k+1} - \frac{1}{3} = \frac{1}{2} \left( q_k - \frac{1}{3} \right) $$

数列 $\left\{ q_k - \frac{1}{3} \right\}$ は、初項が $q_0 - \frac{1}{3}$、公比が $\frac{1}{2}$ の等比数列である。球は 0 秒後には部屋 $P$ にあるため、$q_0 = 0$ である。

$$ q_k - \frac{1}{3} = \left( 0 - \frac{1}{3} \right) \left( \frac{1}{2} \right)^k $$

$$ q_k = \frac{1}{3} \left\{ 1 - \left( \frac{1}{2} \right)^k \right\} $$

$n = 2k$ より $k = \frac{n}{2}$ であるから、$n$ が偶数のとき、求める確率は

$$ \frac{1}{3} \left\{ 1 - \left( \frac{1}{2} \right)^{\frac{n}{2}} \right\} $$

となる。

解説

一見すると複雑な図形に見えるが、隣り合う部屋の向きが必ず反転すること（二部グラフの性質）に気づけば、半分の部屋だけを追跡すればよいことが分かる。さらに、3つある「下向きの部屋」は、全体の中での位置は違って見えても、そこから1歩進んで戻ってくる「局所的な隣接関係」が全く同じ構造をしている。この状態の対称性を見抜くことが、この問題の最大のポイントである。これにより、連立漸化式を立てることなく、シンプルな1つの漸化式に帰着できる。