浅葱色の計算用紙

数学(広義)を扱っています。移転後サイトです。

ポプテピピックで竹●房破壊

【Aパート】

問題:

画面上に「ポ」「プ」「テ」「ピピック」が等確率でランダムに表示される。画面上に「ポプテピピック」の文字列が完成すると竹●房が破壊される。このとき、竹●房が破壊されるまでに画面に表示される文字数の期待値を求めよ。

 

解答:

いつもの。

画面上に表示された最後の文字が「ポ」のとき竹●房が破壊されるまでに追加で表示される文字数の期待値を\( a \),

画面上に表示された最後の文字列が「ポプ」のとき竹●房が破壊されるまでに追加で表示される文字数の期待値を\( b \),

画面上に表示された最後の文字列が「ポプテ」のとき竹●房が破壊されるまでに追加で表示される文字数の期待値を\( c \),

画面上に表示された最後の文字列が上記のどれでもないとき(空であるときも含む)竹●房が破壊されるまでに追加で表示される文字数の期待値を\( x \)とすると

次の連立方程式が成り立つ。

\( a=\frac{1}{4}(1+a)+\frac{1}{4}(1+b)+\frac{1}{4}(1+x)+\frac{1}{4}(4+x) \)

\( b=\frac{1}{4}(1+a)+\frac{1}{4}(1+x)+\frac{1}{4}(1+c)+\frac{1}{4}(4+x) \)

\( c=\frac{1}{4}(1+a)+\frac{1}{4}(1+x)+\frac{1}{4}(1+x)+\frac{1}{4}(4) \)

\( x=\frac{1}{4}(1+a)+\frac{1}{4}(1+x)+\frac{1}{4}(1+x)+\frac{1}{4}(4+x) \)

あとはこの方程式をグレブナー基底でも何でも使って解くと、

\( a=441, b=420, c=336, x=448 \)

となるので、求める答えは448文字である。

 

 

【Bパート】

問題:

画面上に「\(c_1\)」「\(c_2\)」\( \cdots \)「\(c_{n-1}\)」「\(c_nc_n \cdots c_n\)」( \(c_n\)が\(n\)文字 )が等確率でランダムに表示される。画面上に文字列「\(c_1c_2\cdots c_{n-1}c_nc_n \cdots c_n\)」( \(c_n\)が\(n\)文字 )が完成すると竹●房が破壊される。このとき、竹●房が破壊されるまでに画面に表示される文字数の期待値を求めよ。

 

解答:

画面上に表示された最後の文字が「\(c_1\)」のとき竹●房が破壊されるまでに追加で表示される文字数の期待値を\( a_1 \),

画面上に表示された最後の文字列が「\(c_1c_2\)」のとき竹●房が破壊されるまでに追加で表示される文字数の期待値を\( a_2 \),

\( \cdots \)

画面上に表示された最後の文字列が「\(c_1c_2\cdots c_{n-1} \)」のとき竹●房が破壊されるまでに追加で表示される文字数の期待値を\( a_{n-1} \),

画面上に表示された最後の文字列が上記のどれでもないとき(空であるときも含む)竹●房が破壊されるまでに追加で表示される文字数の期待値を\( x \)とすると

次の連立方程式が成り立つ。

\( a_1=\frac{1}{n}(1+a_1)+\frac{1}{n}(1+a_2)+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \)

\( a_2=\frac{1}{n}(1+a_1)+\frac{1}{n}(1+a_3)+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \)

\( \cdots \)

\( a_{n-2}=\frac{1}{n}(1+a_1)+\frac{1}{n}(1+a_{n-1})+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \)

\( a_{n-1}=\frac{1}{n}(1+a_1)+\frac{1}{n}(n)+\frac{n-2}{n}(1+x)\)

\( x=\frac{1}{n}(1+a_1)+\frac{n-2}{n}(1+x)+\frac{1}{n}(n+x) \)

この方程式を解けばよい。

 

ここで、

\( a_1-\frac{1}{n}(1+a_2)=\frac{1}{n}(1+a_1)+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \)

\( a_2-\frac{1}{n}(1+a_3)=\frac{1}{n}(1+a_1)+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \)

\( \cdots \)

\( a_{n-2}-\frac{1}{n}(1+a_{n-1})=\frac{1}{n}(1+a_1)+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \)

であるから、\(1\leq k \leq n-2 \)の範囲で \(a_k-\frac{1}{n}(1+a_{k+1}) \)は一定値を取る。

よってこの値を\( C \)とすると、 \(a_k-\frac{1}{n}(1+a_{k+1})=C \)すなわち\(a_{k+1}-na_k=-nC-1 \)が成り立つ。ここで\(-nC-1=C'\)とすると、\(a_{k+1}-na_k=C'\)となるので、\(a_k\)はある定数\(A\)を用いて

\(a_k=An^k+\frac{C'}{1-n}\)

と表される。

 また、この式から\(a_1=An+\frac{-nC-1}{1-n}\)であるから、これを

\( C=\frac{1}{n}(1+a_1)+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \) (∵\(C\)の定義)

に代入すると、

\( \begin{eqnarray} C&=&\frac{1}{n}\left(An+\frac{-n(C+1)}{1-n}\right)+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \\ &=&\left(A-\frac{C+1}{1-n}\right)+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \end{eqnarray}\)

 また、\( a_{n-1}, x\)の式にも同様に代入すると、

\( An^{n - 1}+\frac{-nC-1}{1-n}=\left(A-\frac{C+1}{1-n}\right)+1+\frac{n-2}{n}(1+x) \)

\( x=\left(A-\frac{C+1}{1-n}\right)+\frac{n-2}{n}(1+x)+\frac{1}{n}(n+x) \)

となる。

これらの3式を\(A,C,x\)について解けばよい。

一旦分母を払って右辺を\(=0\)にする。

\( n(1-n)C-n(1-n)A+n(C+1)-(n-3)(1-n)(1+x)-(1-n)(n+x)=0 \)

\( An^n(1-n)+n(-nC-1)-n(1-n)A+n(C+1)-n(1-n)-(n-2)(1-n)(1+x)=0 \)

\( n(1-n)x-n(1-n)A+n(C+1)-(n-2)(1-n)(1+x)-(1-n)(n+x)=0 \)

あとはこれをグレブナー基底解いて、

 \( A=-2+\frac{1}{n}, C=\frac{n^{n-1}(n-1)(2n-1)-1}{n}, x=n^{n-1}(2n-1) \)

を得る。

したがって、求める文字数は\(n^{n-1}(2n-1) \)文字である。