トップ› 東京大学› 2013年› 文系第4問

東京大学 2013年文系第4問解説

方針・初手

A がちょうど $n$ 回目に勝利する条件を整理する。勝利条件を満たすためには、「$n$ 回目に A がコインを投げて表を出し、その時点でちょうど A の得点が2点になる」必要がある。つまり、$n-1$ 回目のトスが終わった時点で以下の状態になっていなければならない。

A の得点が1点である。
B の得点が0点または1点である。
次にコインを投げるのは A である。

ルールより、コインの移動は「裏が出たとき」のみ発生し、最初は A が持っている。したがって、あるタイミングで A がコインを持っているための必要十分条件は、「それまでに出た裏の回数の合計が偶数回であること」である。これにより、表と裏の出る回数について、$n$ の偶奇で場合分けを行って確率を求めることができる。

解法1

$n-1$ 回目までのトスにおいて、裏が出た回数を $2m$ 回（$m \geqq 0$ の整数）とする。このとき、$n-1$ 回目終了時点で A が1点、B が $b$ 点（$b=0, 1$）であるとすると、$n-1$ 回のトスの内訳は「A の表が1回、B の表が $b$ 回、裏が $2m$ 回」となる。総トス回数について、以下の等式が成り立つ。

$$ n-1 = 1 + b + 2m \iff n = 2 + b + 2m $$

$b$ は $0$ または $1$ しかとり得ないため、$n$ の偶奇によって $b$ の値が完全に決定される。

(i) $n$ が偶数のとき $n = 2k$（$k \geqq 1$）とおく。このとき $b=0$ であり、$n-1$ 回目までに出る裏の回数は $2k-2$ 回となる。 $n-1$ 回のトスの結果の列は、A の表（$H_A$）が1回、裏（$T$）が $2k-2$ 回で構成される。 $H_A$ が出せるのは A の手番のときのみであり、これは $T$ が偶数回（$0, 2, 4, \dots, 2k-2$ 回）出た直後に限られる。つまり、$2k-2$ 個の $T$ の列に対して、$H_A$ を1回挿入できる位置は $k$ 箇所存在する。それぞれの結果の列が起こる確率は $\left(\frac{1}{2}\right)^{n-1}$ である。 $n$ 回目に A が投げて表が出る確率は $\frac{1}{2}$ なので、求める確率 $p(n)$ は、

$$ p(n) = k \left(\frac{1}{2}\right)^{n-1} \times \frac{1}{2} = k \left(\frac{1}{2}\right)^n $$

$k = \frac{n}{2}$ を代入して、

$$ p(n) = \frac{n}{2} \left(\frac{1}{2}\right)^n = n \left(\frac{1}{2}\right)^{n+1} $$

(ii) $n$ が奇数のとき $n = 2k+1$（$k \geqq 1$）とおく。（$n=1$ のときは勝利条件を満たさないため $p(1)=0$ である）このとき $b=1$ であり、$n-1$ 回目までに出る裏の回数は $2k-2$ 回となる。 $n-1$ 回のトスの結果の列は、A の表（$H_A$）が1回、B の表（$H_B$）が1回、裏（$T$）が $2k-2$ 回で構成される。 $2k-2$ 個の $T$ の列に対して、それぞれの表を挿入する位置を考える。

$H_A$ は、A の手番である「$T$ が偶数回出た直後」の $k$ 箇所のいずれかに入る。
$H_B$ は、B の手番である「$T$ が奇数回出た直後」の $k-1$ 箇所のいずれかに入る。

$H_A$ と $H_B$ が入る条件（それまでの $T$ の累積回数）は互いに影響を与えないため、挿入位置の選び方は独立に $k \times (k-1)$ 通りある。 $n$ 回目に A が投げて表が出る確率を含めると、求める確率 $p(n)$ は、

$$ p(n) = k(k-1) \left(\frac{1}{2}\right)^{n-1} \times \frac{1}{2} = k(k-1) \left(\frac{1}{2}\right)^n $$

$k = \frac{n-1}{2}$ を代入して、

$$ p(n) = \frac{n-1}{2} \cdot \frac{n-3}{2} \left(\frac{1}{2}\right)^n = (n-1)(n-3) \left(\frac{1}{2}\right)^{n+2} $$

（この式は $n=1$ のとき $p(1)=0$ となり成立する）

解法2

状態遷移と漸化式を用いて解く。 $m$ 回目のトスを終えた時点で、「A がコインを持ち、A が $i$ 点、B が $j$ 点」である確率を $A_m(i,j)$、「B がコインを持ち、A が $i$ 点、B が $j$ 点」である確率を $B_m(i,j)$ とおく。求める確率は $p(n) = \frac{1}{2} A_{n-1}(1,0) + \frac{1}{2} A_{n-1}(1,1)$ である。

初期状態は $A_0(0,0) = 1$ であり、得点が動かない状態遷移について以下の漸化式が成り立つ。

$$ \begin{cases} A_m(0,0) = \frac{1}{2} B_{m-1}(0,0) \\ B_m(0,0) = \frac{1}{2} A_{m-1}(0,0) \end{cases} $$

これにより $A_m(0,0)$ は $m$ が偶数のときのみ値を持ち、$A_{2k}(0,0) = \left(\frac{1}{4}\right)^k$ となる。次に、A が1点だけを取っている状態 $A_m(1,0)$ の漸化式を立てる。

$$ \begin{cases} A_m(1,0) = \frac{1}{2} A_{m-1}(0,0) + \frac{1}{2} B_{m-1}(1,0) \\ B_m(1,0) = \frac{1}{2} A_{m-1}(1,0) \end{cases} $$

辺々から $B$ の項を消去すると、

$$ A_m(1,0) = \frac{1}{2} A_{m-1}(0,0) + \frac{1}{4} A_{m-2}(1,0) $$

$A_m(1,0)$ は $m$ が奇数のときのみ値を持つ。$m=2k+1$ とおき、両辺に $4^{k+1}$ を掛けて整理すると、数列 $\{4^k A_{2k-1}(1,0)\}$ が等差数列になることがわかり、これを解くと

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

となる。したがって、$n$ が偶数（$n=2k$）のとき、

$$ p(n) = \frac{1}{2} A_{n-1}(1,0) = k \left(\frac{1}{2}\right)^{2k} = n \left(\frac{1}{2}\right)^{n+1} $$

同様に、$B_m(0,1)$ および $A_m(1,1)$ に至る遷移の漸化式を立てて解くことで、$A_{2k}(1,1) = k(k-1) \left(\frac{1}{2}\right)^{2k}$ が得られる。したがって、$n$ が奇数（$n=2k+1$）のとき、

$$ p(n) = \frac{1}{2} A_{n-1}(1,1) = \frac{1}{2} k(k-1) \left(\frac{1}{2}\right)^{2k} = (n-1)(n-3) \left(\frac{1}{2}\right)^{n+2} $$

となり、解法1と同じ結果が得られる。

解説

「コインの所持者が変わる条件」と「得点が入る条件」が独立していることに気づけるかが鍵となる問題である。コインは裏が出るたびに持ち主が入れ替わるため、「次に投げるのが誰か」は「それまでに出た裏の回数の偶奇」に完全に依存する。解法1のように、求める事象を「表と裏の並べ替え」として捉え、独立に配置できるものを数え上げる手法は、複雑な確率の問題で見通しを良くする強力な定石である。解法2のような漸化式を立てる方針も、確実かつ機械的に解を進められるため有力である。