トップ› 東京大学› 2013年› 理系第3問

東京大学 2013年理系第3問解説

方針・初手

Aが $n$ 回目に勝利するための条件を、直前の $n-1$ 回目終了時点の状態から逆算して整理する。 $n$ 回目にAが勝利するには、$n$ 回目のトスでAが「表」を出す必要がある。そのためには、$n-1$ 回目終了時点で以下の条件がすべて満たされている必要がある。

Aの得点が 1 点である。
Bの得点が 0 点または 1 点である。
コインの所持者がAである。

「コインの所持者」は「裏が出た合計回数」によって決まる。初期状態がAなので、裏が偶数回出た直後はA、奇数回出た直後はBが所持者となる。したがって、$n-1$ 回目までの裏の回数は偶数回でなければならない。この条件をもとに、AとBのトスの列（表と裏の並び）の組み合わせを数え上げる。

解法1

(1)

$n-1$ 回目終了時点での裏の回数を $2m-2$ 回（$m$ は正の整数）とする。コインは裏が出るたびに相手に渡るため、トスを行う順番は A $\to$ B $\to$ A $\to$ B $\dots$ と交互に切り替わる。裏が $2m-2$ 回出ているため、Aのターン（表が出れば継続、裏で相手に交代）とBのターンはそれぞれ $m$ 個、$m-1$ 個のブロックに分かれる。すなわち、$n-1$ 回目のトスはAが行っており、これまでのAのトス列の最後は裏である必要はないが、Bの $m-1$ 個のターンのブロックは必ず「裏」で終了している。

ここで、Bの得点によって場合分けを行う。

(i) Bの得点が 0 点の場合 $n-1$ 回のトスの内訳は、Aの表 1 回、Bの表 0 回、裏 $2m-2$ 回である。トスの総数は $(n-1) = 1 + 0 + (2m-2) = 2m-1$ 回であり、$n = 2m$（偶数）となる。

Aが行ったトスの総数は、表 1 回と裏 $m-1$ 回の計 $m$ 回である。この $m$ 回のトスのうち、表がどこで出たかの選び方は ${}_{m}\mathrm{C}_{1} = m$ 通りある。 Bが行ったトスの総数は $m-1$ 回であり、これらはすべて「裏」であるため並び方は 1 通りである。

したがって、このような $n-1$ 回のトス結果は $m$ 通りあり、各々の確率は $\left(\frac{1}{2}\right)^{n-1}$ である。 $n$ 回目にAが表を出す確率 $\frac{1}{2}$ を掛け合わせて、

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

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

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

(ii) Bの得点が 1 点の場合 $n-1$ 回のトスの内訳は、Aの表 1 回、Bの表 1 回、裏 $2m-2$ 回である。トスの総数は $(n-1) = 1 + 1 + (2m-2) = 2m$ 回であり、$n = 2m+1$（奇数）となる。

Aが行ったトスの総数は $m$ 回（表 1 回、裏 $m-1$ 回）であり、表の位置の選び方は ${}_{m}\mathrm{C}_{1} = m$ 通りある。 Bが行ったトスの総数も $m$ 回（表 1 回、裏 $m-1$ 回）である。ただし、Bのターンは $m-1$ 回の裏で必ず終了するため、Bのトス列の最後は必ず「裏」でなければならない。したがって、Bの表は最初の $m-1$ 回のトスのいずれかで出ることになり、その選び方は $m-1$ 通りである。

全体のトス結果は $m(m-1)$ 通りとなるので、

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

$m = \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)

求める値は $\sum_{n=1}^{\infty} p(n)$ である。$n$ の偶奇で分けて和を計算する。

$S = \sum_{m=1}^{\infty} p(2m) = \sum_{m=1}^{\infty} m \left(\frac{1}{4}\right)^m$ とおく。

$$ S - \frac{1}{4}S = \sum_{m=1}^{\infty} m \left(\frac{1}{4}\right)^m - \sum_{m=1}^{\infty} m \left(\frac{1}{4}\right)^{m+1} = \sum_{m=1}^{\infty} \left(\frac{1}{4}\right)^m $$

$$ \frac{3}{4}S = \frac{\frac{1}{4}}{1 - \frac{1}{4}} = \frac{1}{3} $$

これより $S = \frac{4}{9}$ を得る。

次に、$T = \sum_{m=1}^{\infty} p(2m+1) = \frac{1}{2} \sum_{m=1}^{\infty} m(m-1) \left(\frac{1}{4}\right)^m$ を求める。

$U = \sum_{m=1}^{\infty} m(m-1) x^m$ （$x = \frac{1}{4}$）とおくと、

$$ U - xU = \sum_{m=1}^{\infty} m(m-1) x^m - \sum_{m=1}^{\infty} (m-1)(m-2) x^m = \sum_{m=1}^{\infty} 2(m-1) x^m = 2x \sum_{k=1}^{\infty} k x^k $$

ここで $\sum_{k=1}^{\infty} k \left(\frac{1}{4}\right)^k = S = \frac{4}{9}$ であるから、$x = \frac{1}{4}$ を代入して、

$$ \frac{3}{4} U = 2 \cdot \frac{1}{4} \cdot \frac{4}{9} = \frac{2}{9} $$

これより $U = \frac{8}{27}$ となり、$T = \frac{1}{2} U = \frac{4}{27}$ を得る。

以上より、

$$ \sum_{n=1}^{\infty} p(n) = S + T = \frac{4}{9} + \frac{4}{27} = \frac{16}{27} $$

解法2

(2) の別解：吸収確率を用いた解法

$\sum_{n=1}^{\infty} p(n)$ は、無限にゲームを続けたときに「最終的にAが勝利する確率」に他ならない。 Aの得点、Bの得点、コインの所持者を組 $(a, b, X)$ で表し、状態 $(a, b, X)$ からゲームを始めて最終的にAが勝利する確率を $v(a, b, X)$ とする。求める値は初期状態における $v(0, 0, A)$ である。

各状態からの遷移（表、裏がそれぞれ確率 $\frac{1}{2}$）を考えると、次の方程式が成り立つ。

$$ \begin{cases} v(0,0,A) = \frac{1}{2} v(1,0,A) + \frac{1}{2} v(0,0,B) \\ v(0,0,B) = \frac{1}{2} v(0,1,B) + \frac{1}{2} v(0,0,A) \\ v(1,0,A) = \frac{1}{2} \cdot 1 + \frac{1}{2} v(1,0,B) \quad \text{（表が出ればA勝利）} \\ v(1,0,B) = \frac{1}{2} v(1,1,B) + \frac{1}{2} v(1,0,A) \\ v(0,1,A) = \frac{1}{2} v(1,1,A) + \frac{1}{2} v(0,1,B) \\ v(0,1,B) = \frac{1}{2} \cdot 0 + \frac{1}{2} v(0,1,A) \quad \text{（表が出ればB勝利）} \\ v(1,1,A) = \frac{1}{2} \cdot 1 + \frac{1}{2} v(1,1,B) \quad \text{（表が出ればA勝利）} \\ v(1,1,B) = \frac{1}{2} \cdot 0 + \frac{1}{2} v(1,1,A) \quad \text{（表が出ればB勝利）} \end{cases} $$

これを下から順に解く。 $v(1,1,B) = \frac{1}{2} v(1,1,A)$ を $v(1,1,A)$ の式に代入し、

$$ v(1,1,A) = \frac{1}{2} + \frac{1}{4} v(1,1,A) \implies v(1,1,A) = \frac{2}{3}, \quad v(1,1,B) = \frac{1}{3} $$

同様に、

$$ v(0,1,B) = \frac{1}{2} v(0,1,A) $$

$$ v(0,1,A) = \frac{1}{2} \cdot \frac{2}{3} + \frac{1}{4} v(0,1,A) \implies v(0,1,A) = \frac{4}{9}, \quad v(0,1,B) = \frac{2}{9} $$

さらに、

$$ v(1,0,A) = \frac{1}{2} + \frac{1}{2} v(1,0,B) $$

$$ v(1,0,B) = \frac{1}{2} \cdot \frac{1}{3} + \frac{1}{2} v(1,0,A) = \frac{1}{6} + \frac{1}{2} v(1,0,A) $$

よって、

$$ v(1,0,A) = \frac{1}{2} + \frac{1}{12} + \frac{1}{4} v(1,0,A) \implies \frac{3}{4} v(1,0,A) = \frac{7}{12} \implies v(1,0,A) = \frac{7}{9} $$

最後に、

$$ v(0,0,B) = \frac{1}{2} \cdot \frac{2}{9} + \frac{1}{2} v(0,0,A) = \frac{1}{9} + \frac{1}{2} v(0,0,A) $$

$$ v(0,0,A) = \frac{1}{2} \cdot \frac{7}{9} + \frac{1}{2} \left( \frac{1}{9} + \frac{1}{2} v(0,0,A) \right) = \frac{7}{18} + \frac{1}{18} + \frac{1}{4} v(0,0,A) $$

$$ \frac{3}{4} v(0,0,A) = \frac{4}{9} \implies v(0,0,A) = \frac{16}{27} $$

よって、求める確率は $\frac{16}{27}$ である。

解説

（1）では、ゲームが $n$ 回目で終わるための必要条件から逆算して、トス列の構造（表と裏の配置のルール）を決定できるかが鍵となる。特に、「Bのターンブロックの最後は必ず裏になる」という制約に気づけると、組み合わせの計算が非常にシンプルになる。（2）の無限級数の和は、（1）が正しく解けていれば標準的な「（等差数列）×（等比数列）」型の級数計算に帰着する。計算量に差はあるが、解法2で示したようにマルコフ連鎖の吸収確率として立式すると、無限回の試行を有限個の方程式に落とし込むことができ、非常に見通しが良い。