https://spherical-harmonics.hateblo.jp/entry/Waseda/2024/Rikou

2024.02.17記

[4] 2つのチーム $W$ ， $K$ が $n$ 回試合を行う．ただし， $n\geqq 2$ とする．各試合での $W$ ， $K$ それぞれの勝つ確率は $\dfrac{1}{2}$ とし，引き分けはないものとする． $W$ が連敗しない確率を $p_n$ とする．ただし，連敗とは2回以上続けて負けることを言う．

(1) $p_3$ を求めよ．

(2) $p_{n+2}$ を $p_{n+1}$ と $p_{n}$ を用いて表せ．

(3) 以下の2式を満たす $\alpha$ ， $\beta$ を求めよ．ただし， $\alpha\lt\beta$ とする．
$p_{n+2}-\beta p_{n+1}=\alpha (p_{n+1}-\beta p_{n})$
$p_{n+2}-\alpha p_{n+1}=\beta (p_{n+1}-\alpha p_{n})$

(4) $p_n$ を求めよ．

本問のテーマ

フィボナッチ数列

2024.02.17記
Waseda vs. Keio になっている．

[解答]
(1) $W$ が勝つことを○で表し負けることを×で表すことにすると連敗しないのは
○○○，×○○，○×○，○○×，×○×
の5通りだから $p_3=\dfrac{5}{8}$

(2) 1試合目に $W$ が勝った場合，残り $n+1$ 回に連敗しなければ良いのでその確率は $\dfrac{1}{2}p_{n+1}$

1試合目に $W$ が負けた場合，2試合目は勝たなければならず，そのあと残り $n$ 回に連敗しなければ良いのでその確率は $\dfrac{1}{4}p_{n+n}$

となる．よって $p_{n+2}=\dfrac{1}{2}p_{n+1}+\dfrac{1}{4}p_{n}$

(3) $\lambda^2=\dfrac{1}{2}\lambda+\dfrac{1}{4}$ の解を $\alpha，\beta$ とすれば良い．
つまり $\alpha=\dfrac{1-\sqrt{5}}{4}$ ， $\alpha=\dfrac{1+\sqrt{5}}{4}$ （ $\alpha\lt\beta$ ）とおくと
$\alpha+\beta=\dfrac{1}{2}$ ， $\alpha\beta=-\dfrac{1}{4}$
だから
$p_{n+2}=(\alpha+\beta)p_{n+1}-\alpha\beta$
が成立し，
$p_{n+2}-\beta p_{n+1}=\alpha (p_{n+1}-\beta p_{n})$
$p_{n+2}-\alpha p_{n+1}=\beta (p_{n+1}-\alpha p_{n})$
を満たす．

(4) $p_1=1$ ， $p_2=\dfrac{3}{4}$ である．

(3)により
$p_{n+2}-\beta p_{n+1}=\alpha^n (p_{2}-\beta p_{1})$ ，
$p_{n+2}-\alpha p_{n+1}=\beta^n (p_{2}-\alpha p_{1})$
だから，
$p_{n+1}=\dfrac{(p_2-\alpha p_1)\beta^n-(p_2-\beta p_1)\alpha^n}{\beta-\alpha}$
つまり
$p_{n}=\dfrac{(p_2-\alpha p_1)\beta^{n-1}-(p_2-\beta p_1)\alpha^{n-1}}{\beta-\alpha}$
$=\dfrac{1}{2\sqrt{5}}\left\{(2+\sqrt{5})\left(\dfrac{1+\sqrt{5}}{4}\right)^{n-1}-(2-\sqrt{5})\left(\dfrac{1-\sqrt{5}}{4}\right)^{n-1}\right\}$

[うまい解答]
次のルールで階段を上がることを考える．

・ $W$ が負けたとき：
階段を上がらずにその場所に留まる

・ $W$ が勝ったとき：
最初，または $W$ が勝った次の回ならば1段上がるが， $W$ が負けた次の回ならば2段上がる

このルールで $n$ 回試合を行った後， $n+1$ 回目に必ず $W$ を勝たせる壮行試合を行ったとすると「必ず階段を $n+1$ 段上がっている」ことになるので，その場合の数は

「 $n+1$ 段の階段を一番上まで上がるのに、1歩で1段または2段で上がる場合の上がり方の場合の数」

に等しく，それは $\mbox{Fib}(n+2)$ となる．

よって $p_n=\dfrac{\mbox{Fib}(n+2)}{2^n}$ $=\dfrac{1}{\sqrt{5}\cdot 2^n}\left\{\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+2}-\left(\dfrac{1-\sqrt{5}}{2}\right)^{n+2}\right\}$

$\mbox{Fib}(1)$ $=\mbox{Fib}(2)=1$ ，
$\mbox{Fib}(n+2)=\mbox{Fib}(n+1)+\mbox{Fib}(n)$
である．

一見，[解答]と[うまい解答]で値が違うように見えるが $(1\pm\sqrt{5})^3=8(2\pm\sqrt{5})$ なので同じ値になっている．