トップ› 大阪大学› 2010年› 理系第5問

大阪大学 2010年理系第5問解説

方針・初手

立方体の頂点を2つのグループに分けて考える（2部グラフの性質）。$P$ と $Q$ が常に同じグループの頂点に存在することに着目する。また、異なる頂点にいる場合、2点間の最短距離は常に2となり、共通の隣接頂点が必ず2つ存在するという図形的性質を利用して確率を求める。

解法1

(1)

時刻 $0$ において、$P$ は $A$、$Q$ は $C$ にいる。 $P$ が1回の移動で移りうる頂点は、Aに隣接する $B, D, E$ の3つである。 $Q$ が1回の移動で移りうる頂点は、Cに隣接する $B, D, G$ の3つである。

時刻 $1$ で $P$ と $Q$ が異なる頂点にいる組み合わせ $(P, Q)$ を考える。 $P=B$ のとき、$Q=B, D, G$ のうち $Q=D, G$ が適する。 $P=D$ のとき、$Q=B, D, G$ のうち $Q=B, G$ が適する。 $P=E$ のとき、$Q=B, D, G$ のすべてが適する。

したがって、可能な組み合わせは以下の7通りである。

$$ (B, D), (B, G), (D, B), (D, G), (E, B), (E, D), (E, G) $$

(2)

立方体の8つの頂点を、移動のたびに交互に行き来する2つのグループに分ける。 $V_1 = \{A, C, F, H\}$ $V_2 = \{B, D, E, G\}$ 時刻 $0$ には $P=A \in V_1$、$Q=C \in V_1$ であるため、$n$ が偶数のときは $P, Q \in V_1$、$n$ が奇数のときは $P, Q \in V_2$ となり、$P$ と $Q$ は常に同じグループの集合に属する。したがって、$P$ と $Q$ が異なる頂点にいるとき、その2頂点間の距離（最短の辺の数）は常に2である。立方体において、距離が2である任意の2頂点は、共通の隣接頂点をちょうど2つ持つ。

時刻 $n$ において $P$ と $Q$ が異なる頂点にいるとする。時刻 $n+1$ に $P$ と $Q$ が同じ頂点に移動するのは、これら2つの共通の隣接頂点のいずれかに両者が移動した場合のみである。 $P$ と $Q$ はそれぞれ独立に、隣接する3頂点のいずれかに確率 $\frac{1}{3}$ で移動するため、特定の1つの頂点に両者が移動する確率は $\frac{1}{3} \times \frac{1}{3} = \frac{1}{9}$ である。共通の隣接頂点は2つあるので、時刻 $n+1$ に $P$ と $Q$ が同じ頂点に移動する確率は、

$$ \frac{1}{9} \times 2 = \frac{2}{9} $$

である。

これより、時刻 $n+1$ も異なる頂点に位置する確率は $1 - \frac{2}{9} = \frac{7}{9}$ となる。一方、時刻 $n$ で同じ頂点にいる場合は、その後移動しないため、時刻 $n+1$ で異なる頂点になる確率は $0$ である。したがって、$r_{n+1}$ と $r_n$ の間には次の漸化式が成り立つ。

$$ r_{n+1} = \frac{7}{9} r_n $$

時刻 $0$ では $P=A, Q=C$ で異なる頂点にいるため、$r_0 = 1$ である。よって、数列 $\{r_n\}$ は初項 $1$、公比 $\frac{7}{9}$ の等比数列となり、

$$ r_n = \left(\frac{7}{9}\right)^n $$

である。

(3)

時刻 $n$ において $P$ と $Q$ が異なる頂点にいる事象は、以下の3つの排反な状態に分けられる。 状態A: $P$ と $Q$ がともに上面 $ABCD$ の異なる頂点にいる 状態B: $P$ と $Q$ がともに下面 $EFGH$ の異なる頂点にいる 状態C: $P$ と $Q$ の一方が上面、他方が下面にいる（このとき必ず異なる頂点となる）

問題の定義より、時刻 $n$ において状態Aまたは状態Bである確率が $p_n$、状態Cである確率が $q_n$ である。対称性から、状態Aである確率と状態Bである確率はともに $\frac{1}{2} p_n$ である。

各状態からの時刻 $n+1$ への遷移を考える。上面の頂点から移動するとき、確率 $\frac{2}{3}$ で上面の頂点へ、確率 $\frac{1}{3}$ で下面の頂点へ移る。下面の頂点からの移動も同様に対称である。

状態Aからの遷移 $P, Q$ がともに上面の異なる頂点（例：$A$ と $C$）にいるとする。共通の隣接頂点2つ（$B, D$）は上面にあり、下面の隣接頂点（$E, G$）は互いに異なる。

両者が上面へ移動（確率 $\frac{2}{3} \times \frac{2}{3} = \frac{4}{9}$）: このうち同じ頂点になる確率は $\frac{2}{9}$ なので、異なる頂点（状態A）になる確率は $\frac{2}{9}$ である。
両者が下面へ移動（確率 $\frac{1}{3} \times \frac{1}{3} = \frac{1}{9}$）: 下面の隣接頂点は異なるため、必ず異なる頂点（状態B）になる。確率は $\frac{1}{9}$。
一方が上面、他方が下面へ移動（確率 $2 \times \frac{2}{3} \times \frac{1}{3} = \frac{4}{9}$）: このとき状態Cとなる。

状態Cからの遷移 $P$ が上面、$Q$ が下面（例：$A$ と $F$）にいるとする。共通の隣接頂点は上面に1つ（$B$）、下面に1つ（$E$）ある。

両者が上面へ移動（確率 $\frac{2}{3} \times \frac{1}{3} = \frac{2}{9}$）: 同じ頂点になる確率は $\frac{1}{9}$ なので、異なる頂点（状態A）になる確率は $\frac{1}{9}$。
両者が下面へ移動（確率 $\frac{1}{3} \times \frac{2}{3} = \frac{2}{9}$）: 同じ頂点になる確率は $\frac{1}{9}$ なので、異なる頂点（状態B）になる確率は $\frac{1}{9}$。

時刻 $n+1$ において状態Aまたは状態B（すなわち $p_{n+1}$ の状態）となるのは、

状態Aの確率 $\frac{1}{2}p_n$ から、確率 $\frac{2}{9} + \frac{1}{9} = \frac{1}{3}$ で遷移
状態Bの確率 $\frac{1}{2}p_n$ から、確率 $\frac{1}{9} + \frac{2}{9} = \frac{1}{3}$ で遷移
状態Cの確率 $q_n$ から、確率 $\frac{1}{9} + \frac{1}{9} = \frac{2}{9}$ で遷移の和である。

したがって、

$$ \begin{aligned} p_{n+1} &= \frac{1}{3} \times \frac{1}{2}p_n + \frac{1}{3} \times \frac{1}{2}p_n + \frac{2}{9}q_n \\ &= \frac{1}{3}p_n + \frac{2}{9}q_n \end{aligned} $$

と表される。

(4)

(2) より $P$ と $Q$ が異なる頂点にいる確率は $r_n$ であり、$p_n + q_n = r_n$ であるから、

$$ q_n = \left(\frac{7}{9}\right)^n - p_n $$

が成り立つ。これを (3) の漸化式に代入する。

$$ p_{n+1} = \frac{1}{3}p_n + \frac{2}{9} \left\{ \left(\frac{7}{9}\right)^n - p_n \right\} $$

$$ p_{n+1} = \frac{1}{9}p_n + \frac{2}{9}\left(\frac{7}{9}\right)^n $$

両辺に $9^{n+1}$ を掛けると、

$$ 9^{n+1} p_{n+1} = 9^n p_n + 2 \cdot 7^n $$

$x_n = 9^n p_n$ とおくと、

$$ x_{n+1} - x_n = 2 \cdot 7^n $$

数列 $\{x_n\}$ の階差数列が $2 \cdot 7^n$ である。時刻 $0$ において $P=A, Q=C$ であり、ともに上面の異なる頂点にいるため $p_0 = 1$、すなわち $x_0 = 1$ である。 $n \geqq 1$ のとき、

$$ \begin{aligned} x_n &= x_0 + \sum_{k=0}^{n-1} 2 \cdot 7^k \\ &= 1 + 2 \cdot \frac{7^n - 1}{7 - 1} \\ &= 1 + \frac{1}{3}(7^n - 1) \\ &= \frac{1}{3} \cdot 7^n + \frac{2}{3} \end{aligned} $$

この式は $n=0$ のときも $x_0 = 1$ となり成り立つ。 $p_n = \frac{x_n}{9^n}$ であるから、

$$ p_n = \frac{1}{3}\left(\frac{7}{9}\right)^n + \frac{2}{3}\left(\frac{1}{9}\right)^n $$

これを用いて $q_n$ を求める。

$$ \begin{aligned} q_n &= \left(\frac{7}{9}\right)^n - p_n \\ &= \frac{2}{3}\left(\frac{7}{9}\right)^n - \frac{2}{3}\left(\frac{1}{9}\right)^n \end{aligned} $$

求める極限は、

$$ \lim_{n\to\infty} \frac{q_n}{p_n} = \lim_{n\to\infty} \frac{\frac{2}{3}\left(\frac{7}{9}\right)^n - \frac{2}{3}\left(\frac{1}{9}\right)^n}{\frac{1}{3}\left(\frac{7}{9}\right)^n + \frac{2}{3}\left(\frac{1}{9}\right)^n} $$

分母分子を $\left(\frac{7}{9}\right)^n$ で割ると、

$$ \lim_{n\to\infty} \frac{q_n}{p_n} = \lim_{n\to\infty} \frac{\frac{2}{3} - \frac{2}{3}\left(\frac{1}{7}\right)^n}{\frac{1}{3} + \frac{2}{3}\left(\frac{1}{7}\right)^n} $$

$n \to \infty$ のとき $\left(\frac{1}{7}\right)^n \to 0$ であるから、

$$ \lim_{n\to\infty} \frac{q_n}{p_n} = \frac{\frac{2}{3}}{\frac{1}{3}} = 2 $$

解説

立方体の頂点の移動に関する確率漸化式の典型問題である。頂点を2つのグループ（市松模様に塗るイメージ）に分けることで、$P$ と $Q$ が同じ頂点に出会う条件を見えやすくする手法が有効である。 (3) の立式において、状態を正確に定義し、どの状態からどの状態へどのような確率で移るかという「推移確率」を漏れなく調べ上げることがポイントとなる。 (4) では $p_n+q_n=r_n$ という関係式を利用し、連立漸化式を隣接2項間漸化式に帰着させて一般項を求める典型的な処理を行う。極限計算では、公比の絶対値が最大の項で分母分子を割る定石に従えばよい。