n人でじゃんけんをしてk回目で初めて一人が勝ち残る確率

今日は東大の入試問題にチャレンジしてみました。

[ 問題（原文のまま） ]
3 人で‘ジャンケン’ をして勝者をきめることにする．たとえば，1 人が‘紙’ を出し，他の2 人が‘石’ を
出せば，ただ1 回でちょうど1 人の勝者がきまることになる．3 人で‘ジャンケン’ をして，負けた人は次
の回に参加しないことにして，ちょうど1 人の勝者がきまるまで，‘ジャンケン’ をくり返すことにする．
このとき，k 回目にはじめてちょうど1 人の勝者がきまる確率を求めよ．

自分の解答を紹介します。
所要時間は約20分。
他にも色々な解き方があるはずです。

[ 解答 ]
k 回目に初めて一人が勝ち残る確率を $p_k$ で表し、一度のじゃんけんによって a 人が b 人になる確率を Q(a,b) で表すことにする。

$p_1$ ：
3→1
誰が勝つかで3通り、どれで勝つかで3通りなので
$p_1 = \frac{3 \times 3}{3^3} = \frac{1}{3}$

$p_2$ ：
3→3→1
3→2→1
上の一つの確率は $Q(3,3) \times p_1$ です。

$p_3$ ：
3→3→3→1
3→3→2→1
3→2→2→1
上の二つは2回目以降は $p_2$ と同じなので、これら二つを合わせた確率は $Q(3,3) \times p_2$ です。

$p_4$ ：
3→3→3→3→1
3→3→3→2→1
3→3→2→2→1
3→2→2→2→1
上の三つは2回目以降は $p_3$ と同じなので、これら三つを合わせた確率は $Q(3,3) \times p_3$ です。

結局、k の値によって起こりうる場合を上のように列挙してみると、一番下を除いた分は $Q(3,3) \times p_{k-1}$ で求められることが分かります。
そして、一番下が常に
3→2→…→2→1
の形になっていることも確認できます。

このような考察から、次の漸化式を得ます。
$p_k=Q(3,3) \times p_{k-1} + Q(3,2) \times Q(2,2)^{k-2} \times Q(2,1)$

ここで $Q(3,3)$ および $Q(2,2)$ は、n 人でじゃんけんをしてあいこになる確率の公式
$1-\frac{2^n-2}{3^{n-1}}$
を使うと（使わなくても計算できます）
$Q(3,3) = \frac{1}{3}$
$Q(2,2) = \frac{1}{3}$
また、 $Q(3,2) = \frac{{}_3C_2 \times 3}{3^3} = \frac{1}{3}$ （どの二人が勝つかで ${}_3C_2$ 通りで、どの手で勝つかで 3 通り。）
同様に $Q(2,1) = \frac{2 \times 3}{3^2} = \frac{2}{3}$
これらを代入して整理すると
$p_k = \frac{1}{3}p_{k-1}+\frac{2}{3^k}$ （ $k \geq 2$ ）

このような数列の一般項を求める方法もあるのですが、ここでは推測して数学的帰納法を使います。
漸化式にしたがって順次計算していくと
$p_1 = \frac{1}{3}$
$p_2 = \frac{1}{3} = \frac{3}{9}$
$p_3 = \frac{5}{27}$
$p_4 = \frac{7}{81}$
$p_5 = \frac{9}{243}$
したがって、 $p_k = \frac{2k-1}{3^k}$ と推測できます。
以下、数学的帰納法により証明します。
k = 1 のとき、成り立つ。…(1)
k = m のとき、成り立つと仮定すると
$p_{m+1} = \frac{1}{3} \times \frac{2m-1}{3^m} + \frac{2}{3^{m+1}} = \frac{2(m+1)-1}{3^{m+1}}$
よって、k = m + 1 のときに成り立つ。…(2)
(1), (2) により、全ての自然数について成り立つ。

以上により
$p_k = \frac{2k-1}{3^k}$

高校生に数学を教えることを生業としている手前、これくらいの問題が解けなければ話になりません。
解けて一安心です。

ところで、この問題を一般化した、次のような問題を考えることができます。

[ 問題 ]
n 人でじゃんけんをして、k 回目で初めて一人が勝ち残る確率を求めよ。

n = 3 の場合が東大バージョンです。
ということは、東大の入試問題よりも難しい問題と言えます。

実は、今日はこの問題を解こうと、一日中奮闘していました。
しかし、n = 4 の場合ですら、解くことができませんでした。
規則性もさっぱり見えて来ず、今はお手上げ状態です。
ネットで色々探してみたのですが、この問題自体は見つかっても、その解答は見つかりませんでした。
もしかしたら、今まで誰も解いたことがない問題なのかもしれません。

興味をもったそこのアナタ！
チャンレジしてみてはいかがでしょうか。