次: ところで，試合の終わる回数は？ 上: n人巴戦について 前: 問題提起

• 行列による方法
• 式変形だけで解く

連立方程式（漸化式）による解き方

k連勝している人が先頭にいるときのm番目にいる人の 優勝する確率をP_k,mとおきます． （ $0\le k \le n-1, 1\le m \le n$）

$P_{0,1},P_{0,2},\dots ,P_{0,n}$を求めることが 最終目標です．

(n-1)連勝しているとき 先頭の人が優勝しているのだから

$$P_{n-1,1}=1,P_{n-1,2}=\cdots =P_{n-1,n}=0$$

が成り立ちます．

次に，k連勝 $(0\ge k\ge n-2)$しているとき， 先頭の二人が勝負することを考えましょう．

先頭にいる人は，1/2の確率で(k+1)連勝するか， 1/2の確率で負けるかのどちらかです．

ですから，

$$P_{k,1}=\frac{1}{2} P_{k+1,1}+\frac{1}{2}P_{1,n}.$$

同様に，2番目の人は

$$P_{k,2}=\frac{1}{2} P_{k+1,n}+\frac{1}{2}P_{1,1}.$$

3番目以降の人は，自らは勝負をしませんが ひとつ順番があがることに注意しましょう．

$$P_{k,m}=\frac{1}{2} P_{k+1,m-1}+\frac{1}{2} P_{1,m-1} \quad (3 \le m \le n).$$

ここで得た式を 並べておきましょう．

²

    

式を与えられれば解けるはずですが 実際に解くのはかなり難しくなります．

ここでは，おなじみの行列を用いる方法， 式変形だけで解く方法を紹介します．

行列による方法

この方法は大学生で習う余因子行列や行列式の 基礎的な知識があれば理解できるはずです．（多分．．）

漸化式より

$$\begin{eqnarray*}P_{k,1}&=&2P_{k-1,1}-P_{1,n}\\ P_{k,l}&=&2P_{k-1,l+1}-P_{1,l}\ \ (2\leq l\leq n-1)\\ P_{k,n}&=&2P_{k-1,2}-P_{1,1}. \end{eqnarray*}$$

このとき，

$$\begin{eqnarray*}{\bf v}_k&=& (P_{k,m})_{m=1}^n \ \ (0\leq k\leq n-1)\\ {\bf e}... ...3\cdots{\bf e}_{n-1}{\bf e}_1) \in{\rm M}(n\times n;{\mathbb R}) \end{eqnarray*}$$

(ベクトルはどれも縦ベクトル）とおくと， 問題の条件は

$${\bf v}_k=2A{\bf v}_{k-1}-B{\bf v}_1\ \ (0\leq k\leq n-1),\ \ {\bf v}_{n-1}={\bf e}_1$$

と表される．まず ${\bf v}_1$ を求める．上の漸化式より

$$\begin{eqnarray*}{\bf e}_1&=&{\bf v}_{n-1}=2A{\bf v}_{n-2}-B{\bf v}_1 =2A(2A{\bf... ...& \{2^{n-2}A^{n-2}-(2A-E_n)^{-1}(2^{n-2}A^{n-2}-E_n)B\}{\bf v}_1 \end{eqnarray*}$$

A^n-1=E_n， $A{\bf e}_1={\bf e}_1$ に注意すると

$$\begin{eqnarray*}{\bf e}_1&=&A(2A-E_n){\bf e}_1\\ &=& \{2^{n-2}(2A-E_n)A^{n-1}-... ...{n-2}E_n-A)B\}{\bf v}_1\\ &=& \{2^{n-2}(2A-B-E_n)+AB\}{\bf v}_1 \end{eqnarray*}$$

計算の便利のため $\alpha=2^{n-2}$ とおく． $M=\alpha(2A-B-E_n)+AB$，M の余因子行列を C とおくと， $C{\bf e}_1={\rm det}(M)\cdot{\bf v}_1$ なので ${\rm det}(M)$ と C の 1 列目の各成分がわかれば ${\bf v}_1$ もわかる．

まず M の形を調べる．

$$\begin{eqnarray*}AB &=& ({\bf e}_{n-1}{\bf e}_n{\bf e}_2{\bf e}_3\cdots{\bf e}_{... ...dots&2&0\\ 0&&&&-2&2\\ - -1&2&0&\cdots&0&-1 \end{array}\right) \end{eqnarray*}$$

だから，

$$M=\left( \begin{array}{cccccc} \alpha&0&0&\cdots&0&1-\alpha\\... ...ha\\ -\alpha&1+2\alpha&0&\cdots&0&-\alpha \end{array}\right).$$

C の (i,1)-成分 を c_i とおく． 余因子の定義に戻って計算すると，

$$\begin{eqnarray*}c_1&=&(-1)^{1-1} \left\vert \begin{array}{ccccc} -2\alpha&1+2\a... ...ha\\ &=&(-1)^n2\alpha\{(1+2\alpha)^{n-2}-2^{n-3}\alpha^{n-2}\}, \end{eqnarray*}$$

$$\begin{eqnarray*}c_2&=&(-1)^{2-1} \left\vert \begin{array}{ccccc} 0&1+2\alpha&&&... ...alpha(-\alpha)\}\\ &=&(-1)^n\alpha(2\alpha-1)(1+2\alpha)^{n-3}, \end{eqnarray*}$$

$3\leq i\leq n-2$ なる i に対しては
c_i=(-1)^i-1 $\left\vert \begin{array}{rcrcrlcll} 0&-2\alpha&1+2\alpha&&&0&\cdots&\cdots&0\\... ...&&&-2\alpha&2\alpha\\ -\alpha&1+2\alpha&&&0&&&&-\alpha \end{array}\right\vert$
なので

$$\begin{eqnarray*}c_i&=&(-1)^{i-1} \{-(-2\alpha)\}^{i-2}\{-(1+2\alpha)\}^{n-i-1} ... ...\}\\ &=&(-1)^n2^{i-2}\alpha^{i-1}(2\alpha-1)(2\alpha+1)^{n-i-1} \end{eqnarray*}$$

よく見ると i=2,n-1 でも正しい．

$$\begin{eqnarray*}c_n&=&(-1)^{n-1} \left\vert \begin{array}{ccccc} 0&-2\alpha&1+2... ...a)^{n-2}]\\ &=&(-1)^n\{2^{n-2}\alpha^{n-1} -(1+2\alpha)^{n-2}\} \end{eqnarray*}$$

これで全ての c_i がわかった．次に ${\rm det}(M)$ は

$$\begin{eqnarray*}{\rm det}(M)&=&(MC)_{1,1}=\alpha c_1+(1-\alpha)c_n\\ &=&\alpha... ...^n(2\alpha-1)\{(\alpha+1)(1+2\alpha)^{n-2}-2^{n-2}\alpha^{n-1}\} \end{eqnarray*}$$

ゆえに $P_{1,m}=c_m/{\rm det}(M) \ \ (1\leq m\leq n)$ は全てわかる．一方

$$\begin{eqnarray*}P_{0,1}&=&\frac12P_{1,1}+\frac12P_{1,n} =P_{0,2}\\ P_{0,m}&=&\frac12P_{1,m-1}+\frac12P_{1,m-1}=P_{1,m-1} \ \ (3\leq m\leq n) \end{eqnarray*}$$

なので，

$$\begin{eqnarray*}P_{0,1}=P_{0,2}&=&\frac12(P_{1,1}+P_{1,2})= \frac{c_1+c_2}{2{\r... ...2^{n-1}+1)^{n-2}}{2(2^{n-2}+1)(2^{n-1}+1)^{n-2}- 2^{(n-1)^2}}\\ \end{eqnarray*}$$

であり， $3\leq m\leq n$ に対しては

$$\begin{eqnarray*}P_{0,m}&=&P_{1,m-1}=\frac{c_{m-1}}{{\rm det}(M)}\\ &=&\frac{(-... ...2^{n-1}+1)^{n-m}} {2(2^{n-2}+1)(2^{n-1}+1)^{n-2}-2^{(n-1)^2}}\\ \end{eqnarray*}$$

この式は m=2 でも正しい．

$$\underline{ P_{0,1}=P_{0,2},\ \ P_{0,m}= \frac{2^{(n-1)(m-2)}... ...2^{n-2}+1)(2^{n-1}+1)^{n-2}-2^{(n-1)^2}} \ \ (2\leq m\leq n) }$$

式変形だけで解く

これ以降は高校生にも理解可能です． 誘導をつければ難しめの入試問題とでもいった感じになります．

式だけ与えてやれというのは，， どの変数が重要かということを理解していないと どうどうめぐりの式を量産して投げ出してしまいそうです． 私自身 多大な時間を費やしてしまったので 高校生では，，， いや，道具を知らない高校生こそができるに違いない．

$$\boxed{ \sum_{m=1}^n P_{1,m}=1 }$$ (1)

に注意します．作戦としては， 「各P_1,mをひとつの文字で表す」 ことを目指します．

まずP_1,1をP_1,nを用いて表すことを考えます．

(1)を繰り返し用いることによって

$$\begin{align*}P_{1,1}&=\frac12 P_{2,1}+\frac12 P_{1,n} \\ &=(\frac12)^2P_{3,1}+... ...{n-2}P_{n-1}+ \left( (\frac12)^{n-2}+\cdots +\frac12\right) P_{1,n} \end{align*}$$

(4)より P_n-1,1=1であるから

$$\boxed{ P_{1,1}=(\frac12)^{n-2}+\left( 1-(\frac12)^{n-2}\right)P_{1,n} }$$ (2)

次に， $P_{n-1,n},P_{n-2,n},\dots ,P_{1,n}$を調べます．ここでは でてきた式を (3)を用いて一番左だけを変形していきます． また，(4)を効果的に用いている ことに注意しましょう．
$$\begin{align*}P_{n-1,n}&=0 \\ P_{n-2,n}&=\frac12 P_{1,n-1}+\frac12 P_{n-1,n-1} ... ...12)^{n-2}P_{1,2}+(\frac12)^{n-3}P_{1,3} +\cdots +\frac12 P_{1,n-1} \end{align*}$$

まとめて書いておくと， $k=1,2,\dots , n-1$に対して

$$\boxed{ P_{k,n}=(\frac12)^{n-k-1}P_{1,k+1}+\cdots +\frac12 P_{1,n-1} }$$ (3)

あるいは

$$\boxed{ P_{k,n}=\sum_{j=1}^{n-1-k}(\frac12)^{n-k-j}P_{1,k+j} }$$

である．

ここで

$$\boxed{ b_k := 2^{k-1}P_{1,k} }$$ (4)

とおくと，

$$\boxed{ 2^{n-1}P_{k,n}=b_{k+1}+\cdots +b_{n-1} }$$ (5)

が成り立つ．

一方， $P_{1,m}\ \ (m=2,\dots ,n-1)$に対しても同様の操作を行う．

$$\begin{align*}P_{1,2}&=\frac12 P_{2,n}+\frac12 P_{1,1} \\ P_{1,3}&=(\frac12)^2P... ...2)^{n-2}P_{n-1,n}+ (\frac12)^{n-2}P_{1,1}+\cdots +\frac12 P_{1,n-2} \end{align*}$$

まとめて書いておくと， $m=2,\dots , n-1$に対して

$$\boxed{ P_{1,m}=(\frac12)^{m-1}P_{m,n}+(\frac12)^{m-1}P_{1,1}+\cdots +\frac12 P_{1,m-1} }$$ (6)

あるいは

$$\boxed{ P_{1,m}=(\frac12)^{m-1}P_{m,n}+ \sum_{j=1}^{m-1}(\frac12)^{m-j}P_{1,j} }$$

である．

よって，(8)より

$$\boxed{ b_m=P_{m,n}+b_1+\cdots +b_{m-1} }$$ (7)

(9)を (11)に代入する．

$$b_k=(\frac12)^{n-1}(b_{k+1}+\cdots +b_{n-1}) +b_1+\cdots +b_{k-1}$$

階差をとって

$$b_k-b_{k-1}=-(\frac12)^{n-1}b_k+b_{k-1}$$

ゆえに

$$b_k=\frac{2^n}{1+2^{n-1}}b_{k-1}$$

よって

$$b_k=(\frac{2^n}{1+2^{n-1}})^{k-2}b_2$$

(8)より

$k=2,\cdots n-1$に対して，

$$\boxed{ P_{1,k}=(\frac{2^{n-1}}{1+2^{n-1}})^{k-2}P_{1,2} }$$ (8)

が成り立つ．

これで，最初に掲げた作戦はほぼ終了しました． これを(7)に代入してP_1,nをP_1,2で表すことができます．

さらに，(6)によってP_1,1をP_1,2で 表すことができます．

したがって，(5)に代入することによって P_1,2が得られます．

したがって， $P_{1,m}\ \ (m=1,\ldots n)$を すべて求めることができます．

よって， $P_{0,m}\ \ (m=1,\ldots n)$を求めることができます．

（詳しくは，後で書く．）

次: ところで，試合の終わる回数は？ 上: n人巴戦について 前: 問題提起