京都大学 1995年度後期・理系数学後期第5問解答・解説

問題

$A$ は札 $0, 1, \dots, n$ 、 $B$ は札 $1, \dots, n$ を持ち、 $B$ から交互に相手の札を1枚取る。同番号を持てば2枚を捨て、なければ保持し、先に札がなくなった方が勝つ。 $A, B$ の勝率を $p_{n}, q_{n}$ とする。

(1) $p_{1}, p_{2}, q_{1}, q_{2}$ 。

(2) $p_{n} + q_{n} = 1$ 、 $(n + 2) p_{n} - n p_{n - 2} = 1$ を示せ。

(3) $p_{n}$ を求めよ。

出典：京都大学 1995年度後期日程第2次学力試験後期・理系後期第5問

方針

0の札が相手へ移る枝は役割交換、正番号を引く枝は最初の2手で同番号2組を除いた $n - 2$ のゲームになることを利用し、2段漸化式を解く。

解答

(1)

$n = 1$ では、 $B$ が1を引けば直ちに $B$ の勝ち、0を引いた後に $A$ が1を引けば $A$ の勝ち、0を引けば初期状態へ戻る。従って

p_{1} = \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{2} p_{1},

より $p_{1} = 1/3, q_{1} = 2/3$ 。同様に $n = 2$ の有限状態を最初の札で分けると

p_{2} = \frac{1}{4}, q_{2} = \frac{3}{4} .

(2)

ゲームは必ずどちらかの勝ちで終わり、引き分けはないので $p_{n} + q_{n} = 1$ 。最初に $B$ が0を引く確率は $1/ (n + 1)$ である。この場合、0の札を持つ側と次の手番が入れ替わるため、以後 $A$ が勝つ確率は $q_{n} = 1 - p_{n}$ である。正番号を引く確率は $n / (n + 1)$ で、1組を捨てた後、次の $A$ の手でも必ず1組を捨て、残りは $n - 2$ のゲームになる。従って

p_{n} = \frac{1 - p _{n}}{n + 1} + \frac{n}{n + 1} p_{n - 2} .

整理して

(n + 2) p_{n} - n p_{n - 2} = 1.

(3)

初期値と漸化式から偶数・奇数を分ける。帰納法により

p_{2 m} = \frac{m}{2 m + 2} (m ≧ 1), p_{2 m + 1} = \frac{m + 1}{2 m + 3} (m ≧ 0) .

実際、各式を $(n + 2) p_{n} = 1 + n p_{n - 2}$ へ代入すれば次の同じ偶奇の項が得られ、 $p_{1}, p_{2}$ とも一致する。

京都大学 1995年度後期・理系数学 後期 第5問

問題

方針

解答

(1)

(2)

(3)

京都大学 1995年度
後期・理系数学後期第5問