トップ› 名古屋大学› 2018年› 文系第3問

名古屋大学 2018年文系第3問解説

方針・初手

点Pおよび点Qが1時刻ごとにどの頂点へ移動するかを、頂点の隣接関係（次数）から正確に把握することが第一歩である。頂点は隣接する頂点の数が2個のもの（A, B, E, F）と3個のもの（C, D）に分かれる。さらに、移動の規則から、点P, Qは時刻が1進むごとに、頂点集合 $\{A, C, E\}$ と $\{B, D, F\}$ を必ず交互に行き来する（グラフが二部グラフである）ことに着目する。この性質により、時刻 $n$ の偶奇によらず、点PとQの相対的な位置関係（ともに同じ正方形上にあるか、異なる正方形上にあるか）による状態の推移確率が一定になることを見抜き、連立漸化式を立てる。

解法1

(1)

点Pは頂点Aから移動するため、移動可能な頂点はB, Dの2か所である。点Qは頂点Cから移動するため、移動可能な頂点はB, D, Fの3か所である。

したがって、時刻1における点P, Qの配置 $(P, Q)$ は、これら独立な移動の組み合わせにより、$2 \times 3 = 6$ 通り考えられる。具体的には以下の6通りである。

$(B, B), (B, D), (B, F), (D, B), (D, D), (D, F)$

解答用紙には、図2にならい、これら6通りの位置に点P, Qをそれぞれ記入した図を6つ描く。

(2)

規則(b)より、PはAからB, Dへ各 $\frac{1}{2}$ の確率で移動し、QはCからB, D, Fへ各 $\frac{1}{3}$ の確率で移動する。したがって、(1)で求めた6通りの配置はすべて等確率であり、それぞれの確率は以下の通りである。

$$ \frac{1}{2} \times \frac{1}{3} = \frac{1}{6} $$

$a_1$ は、時刻1においてP, Qが同じ頂点におらず、かつともに同じ正方形上（ABCD上またはCDEF上）にある確率である。これを満たす配置は $(B, D), (D, B), (D, F)$ の3通りである。よって、以下のようになる。

$$ a_1 = \frac{1}{6} \times 3 = \frac{1}{2} $$

$b_1$ は、時刻1においてP, Qが同じ頂点におらず、かつ異なる正方形上にある確率である。これを満たす配置は $(B, F)$ の1通りである。よって、以下のようになる。

$$ b_1 = \frac{1}{6} $$

次に $a_2, b_2$ を求めるために、時刻1における「同じ頂点にいない状態」を2つに分類し、時刻2への推移確率を計算する。

状態A：P, Qがともに同じ正方形上にある。配置は $(B, D), (D, B), (D, F)$。
状態B：P, Qが異なる正方形上にある。配置は $(B, F)$。

(i) 状態Aからの推移代表して $(P, Q) = (B, D)$ の場合を考える。 PはA, Cへ各 $\frac{1}{2}$、QはA, C, Eへ各 $\frac{1}{3}$ で移動する。可能な配置は $2 \times 3 = 6$ 通りあり、各確率は $\frac{1}{6}$ である。このうち、時刻2で状態Aになるのは $(A, C), (C, A), (C, E)$ の3通りであるため、確率は $\frac{3}{6} = \frac{1}{2}$ である。時刻2で状態Bになるのは $(A, E)$ の1通りであるため、確率は $\frac{1}{6}$ である。残りの2通りは $(A, A), (C, C)$ であり、同じ頂点にいる状態となる。配置が $(D, B), (D, F)$ の場合も、対称性から推移確率は同様となる。

(ii) 状態Bからの推移 $(P, Q) = (B, F)$ の場合を考える。 PはA, Cへ各 $\frac{1}{2}$、QはC, Eへ各 $\frac{1}{2}$ で移動する。可能な配置は $2 \times 2 = 4$ 通りあり、各確率は $\frac{1}{4}$ である。このうち、時刻2で状態Aになるのは $(A, C), (C, E)$ の2通りであるため、確率は $\frac{2}{4} = \frac{1}{2}$ である。時刻2で状態Bになるのは $(A, E)$ の1通りであるため、確率は $\frac{1}{4}$ である。残りの1通りは $(C, C)$ であり、同じ頂点にいる状態となる。

以上より、$a_2, b_2$ は以下のように計算できる。

$$ a_2 = a_1 \times \frac{1}{2} + b_1 \times \frac{1}{2} = \frac{1}{2} \times \frac{1}{2} + \frac{1}{6} \times \frac{1}{2} = \frac{1}{4} + \frac{1}{12} = \frac{1}{3} $$

$$ b_2 = a_1 \times \frac{1}{6} + b_1 \times \frac{1}{4} = \frac{1}{2} \times \frac{1}{6} + \frac{1}{6} \times \frac{1}{4} = \frac{1}{12} + \frac{1}{24} = \frac{1}{8} $$

(3)

頂点集合を $U = \{A, C, E\}$ と $V = \{B, D, F\}$ に分ける。移動の規則から、点P, Qは1時刻ごとに $U$ と $V$ を交互に行き来する。したがって、時刻 $n$ における配置は、偶奇によらず常にPとQは同じ集合（ともに $U$、またはともに $V$）に属する。時刻 $n$ でP, Qが同じ頂点にいないとき、(2)と同様に状態を次のように分ける。

状態 $A_n$：P, Qがともに同じ正方形上にある（確率 $a_n$）
状態 $B_n$：P, Qが異なる正方形上にある（確率 $b_n$）

(i) 時刻 $n$ が奇数のとき（P, Q $\in V$）状態 $A_n$ の配置は $\{B, D\}, \{D, F\}$、状態 $B_n$ の配置は $\{B, F\}$ のみである。 (2)で調べた通り、どの配置からも、次の時刻に状態 $A_{n+1}$ になる確率は $\frac{1}{2}$ であり、状態 $B_{n+1}$ になる確率は状態 $A_n$ からは $\frac{1}{6}$、状態 $B_n$ からは $\frac{1}{4}$ である。

(ii) 時刻 $n$ が偶数のとき（P, Q $\in U$）状態 $A_n$ となる配置は $\{A, C\}, \{C, E\}$ である。 $(P, Q) = (A, C)$ とすると、PはB, Dへ各 $\frac{1}{2}$、QはB, D, Fへ各 $\frac{1}{3}$ で移動する（各確率は $\frac{1}{6}$）。次の時刻で状態 $A_{n+1}$ となるのは $(B, D), (D, B), (D, F)$ の3通りで確率は $\frac{1}{2}$、状態 $B_{n+1}$ となるのは $(B, F)$ の1通りで確率は $\frac{1}{6}$ である。 $(P, Q) = (C, E)$ の場合も対称性により同様である。

状態 $B_n$ となる配置は $\{A, E\}$ である。 PはB, Dへ各 $\frac{1}{2}$、QはD, Fへ各 $\frac{1}{2}$ で移動する（各確率は $\frac{1}{4}$）。次の時刻で状態 $A_{n+1}$ となるのは $(B, D), (D, F)$ の2通りで確率は $\frac{1}{2}$、状態 $B_{n+1}$ となるのは $(B, F)$ の1通りで確率は $\frac{1}{4}$ である。

したがって、$n$ の偶奇によらず推移確率は一定であり、以下の漸化式が成り立つ。

$$ \begin{cases} a_{n+1} = \frac{1}{2} a_n + \frac{1}{2} b_n \\ b_{n+1} = \frac{1}{6} a_n + \frac{1}{4} b_n \end{cases} $$

(4)

定義より $p_n = a_n + b_n$ である。 (3)で求めた漸化式より、$p_{n+1}$ を計算する。

$$ \begin{aligned} p_{n+1} &= a_{n+1} + b_{n+1} \\ &= \left(\frac{1}{2} + \frac{1}{6}\right) a_n + \left(\frac{1}{2} + \frac{1}{4}\right) b_n \\ &= \frac{2}{3} a_n + \frac{3}{4} b_n \end{aligned} $$

確率であるから $a_n \geqq 0, b_n \geqq 0$ であり、また $\frac{2}{3} < \frac{3}{4}$ であるため、以下の不等式が成り立つ。

$$ \frac{2}{3} a_n + \frac{3}{4} b_n \leqq \frac{3}{4} a_n + \frac{3}{4} b_n = \frac{3}{4} (a_n + b_n) $$

すなわち、次式を得る。

$$ p_{n+1} \leqq \frac{3}{4} p_n $$

これを繰り返し用いると、以下のようになる。

$$ p_n \leqq \frac{3}{4} p_{n-1} \leqq \dots \leqq \left(\frac{3}{4}\right)^{n-1} p_1 $$

ここで、(2)より $p_1 = a_1 + b_1 = \frac{1}{2} + \frac{1}{6} = \frac{2}{3}$ である。 $\frac{2}{3} \leqq \frac{3}{4}$ より $p_1 \leqq \frac{3}{4}$ であるから、これを代入する。

$$ p_n \leqq \left(\frac{3}{4}\right)^{n-1} \cdot \frac{3}{4} = \left(\frac{3}{4}\right)^n $$

以上により、与えられた不等式が示された。

解説

確率過程（マルコフ連鎖）の考え方を背景とする典型的な問題である。時刻1, 2の具体例を丁寧に計算させ、その推移の規則性がすべての時刻で成り立つことを洞察させる構成となっている。
グラフの頂点を次数や位置関係でグループ分けし、二部グラフの性質を利用することで、複雑に見える場合分けを大幅に整理できる。
(4)は、(3)で得られた連立漸化式を対角化して一般項を求めることも可能だが、非常に煩雑な計算になる。ここでは $a_n, b_n$ の係数を比較して上から評価するという、不等式証明の手法が要求されている。この見極めが完答のための重要なポイントである。