受験数学の確率漸化式の問題を多項式・形式的冪級数で倒す

2032

今回は受験数学の確率漸化式の問題を多項式・形式的冪級数で倒します．
基本となるのは"状態を多項式で持つ"という考え方です．

形式的冪級数とは多項式の一般化で，項数が有限でなくてもよいです．

"状態を多項式で持つ"

2017年京大理系第6問

$n$を自然数とする．$n$個の箱すべてに，$1,2,3,4,5$の$5$種類のカードがそれぞれ$1$枚ずつ計$5$枚入っている．各々の箱から$1$枚ずつカードを取り出し，取り出した順に左から並べて$n$桁の数$X$を作る．このとき，$X$が$3$で割り切れる確率を求めよ．

明らかに，条件は出たカードの和が$3$の倍数となると言い換えられます．
いきなりですが次の多項式を考えます．
$$ f(x) = \Big(\frac{1}{5}x+\frac{1}{5}x^2+\frac{1}{5}x^3+\frac{1}{5}x^4+\frac{1}{5}x^5)^n$$

これを展開した様子を想像してみてください．これは場合の数の計算と同等だと分かります．

例えば$n=2$のとき，
$$ f(x) = \Big(\frac{1}{5}\Big)^2x^{1+1}+\Big(\frac{1}{5}\Big)^2x^{2+1}+\Big(\frac{1}{5}\Big)^2x^{3+1}\cdots+\Big(\frac{1}{5}\Big)^2x^{5+4}+\Big(\frac{1}{5}\Big)^2x^{5+5}$$
となり，$x^{a+b}$はカードが$a,b$と出る場合を表しています．
ということは$f(x)$の$x^{3の倍数}$の係数の総和を求めればいいと分かります．

$$ f(x) = \Big(\frac{1}{5}x+\frac{1}{5}x^2+\frac{1}{5}+\frac{1}{5}x+\frac{1}{5}x^2\Big)^n=\Big(\frac{1}{5}+\frac{2}{5}x+\frac{2}{5}x^2\Big)^n$$
このように$f(x)$を定義しても結果は変わらないので慣れてきたらこのようにするといいかもしれないです．以下これで再定義します．

これは後述する方法によって簡単に求められます．

このように，状態を多項式で持つということが出来ます．ポイントは対象を文字で記録出来ないかと考えることです．

$x^{mの倍数}$の係数の総和を求める

$f(x)=a_0+a_1x+a_2x^2+\cdots$において，$x^{mの倍数}$の係数の総和の求め方を解説します．
先に結論を言うと，$\zeta=\cos(2\pi/m)+i\sin{(2\pi/m)}$として，
$$ \frac{1}{p}(f(1)+f(\zeta)+\cdots+f(\zeta^{m-1}))$$
となります．これは，$x^m=1$の解の$k$乗和を$S_k$とすると
$$ S_k = \begin{cases} m & \text{if } k \equiv 0\pmod m \\ 0 & \text{otherwise} \end{cases} $$
となるためです．これは次の補題から分かります．(この補題の証明： http://wwu.phoenix-c.or.jp/~tokioka3/k_power/k_power.pdf )

$n$次方程式$f(x)=0$の$n$個の解の$k$乗和を$S_k$とすると次が成り立つ：
$$ \dfrac{xf'(x)}{f(x)}=\sum_{k=0}^{\infty}\dfrac{S_k}{x^k}$$

さて，例$1$に戻ります．いま説明したことを使えば，$f(x)=(\frac{1}{5}+\frac{2}{5}x+\frac{2}{5}x^2)^n$の$x^{3の倍数}$の係数の総和は，$\omega=\cos{2\pi/3}+i\sin{2\pi/3}$として，$\omega^3=1,\omega^2+\omega+1=0$に注意すれば，

$$ \frac{1}{3}\Big(f(1)+f(\omega)+f(\omega^2)\Big)=\frac{1}{3}+\frac{2}{3}\big(-\frac{1}{5}\big)^n$$

と求められます．

練習問題

2020年阪大文系第2問(3)のみ

円周を$3$等分する点を時計回りに$A,B,C$とおく．点$Q$は$A$から出発し，$A,B,C$を以下のように移動する．$1$個のさいころを投げて，$1$の目が出た場合には時計回りに隣の点に移動し，$2$の目が出た場合は反時計回りに隣の点に移動し，その他の目が出た場合は移動しない．さいころを$n$回投げたあとに$Q$が$A$に位置する確率を$p_n$とする．$p_n$を求めよ．

ヒント

$\mod 3$で$A(0),B(1),C(2)$として$Q$の場所を$x$で記録すると？

2011年一橋大第5問

$A$と$B$の$2$人が，$1$個のさいころを次の手順により投げ合う．

$1$回目は$A$が投げる．
$1,2,3$の目が出たら，次の回には同じ人が投げる．
$4,5$の目が出たら，次の回には別の人が投げる．
$6$の目が出たら，投げた人を勝ちとしてそれ以降は投げない．

$n$回目に$A$がさいころを投げる確率$a_n$を求めよ．
ちょうど$n$回目のさいころ投げで$A$が勝つ確率$p_n$を求めよ．
$n$回以内のさいころ投げで$A$が勝つ確率$q_n$を求めよ．

ヒント

(1)が出来たらあとは計算するだけですね．投げる人を$x$で記録すると？

多変数の多項式を用意する場合

考え方は変わりません．

2023年京大理系第3問

$n$を自然数とする．$1$個のさいころを$n$回投げ，出た目を順に$X_1,X_2,\cdots,X_n$とし，$n$個の数の積$X_1X_2\cdots X_n$を$Y$とする．
(1) $Y$が$5$で割り切れる確率を求めよ．
(2) $Y$が$15$で割り切れる確率を求めよ．

$Y$の素因数$3,5$の個数を$x,y$で記録しようと考えると，次の多項式が考えられます：
$$ f(x,y) = \Big(\frac{1}{6}+\frac{1}{6}+\frac{1}{6}{x}+\frac{1}{6}+\frac{1}{6}y+\frac{1}{6}x\Big)^n=\Big(\frac{2}{6}x+\frac{1}{6}y+\frac{3}{6}\Big)^n$$

(1)は$f(x,y)$における$x^{任意}y^{1以上}$の係数の総和，(2)は$x^{1以上}y^{1以上}$の係数の総和を求めればいいです．

(1)$g(y)=f(1,y)$として，$g(y)$における$y^{1以上}$の係数の総和を求めればいいので，定数項が$g(0)$であることに注意すれば
$$ g(1)-g(0)=1-\Big(\frac{5}{6}\Big)^n$$
と求められます．
(2) $x^{1以上}$の係数の総和($h(y)$とおく)から，$y^{1以上}$の係数を求めればいいので
$$ h(y)=f(1,y)-f(0,y)=\Big(\frac{1}{6}y+\frac{5}{6}\Big)^n-\Big(\frac{1}{6}y +\frac{3}{6}\Big)^n$$
$$ h(1)-h(0)=1-\Big(\frac{2}{3}\Big)^n-\Big(\frac{5}{6}\Big)^n+\Big(\frac{1}{2}\Big)^n$$
と求められます．

練習問題

2004年東大理系第4問

片面を白色に，もう片面を黒色に塗った正方形の板が$3$枚ある．この$3$枚の板を机の上に横に並べ，次の操作を繰り返し行う．
さいころを振り，出た目が$1,2$であれば左端の板を裏返し，$3,4$であればまん中の板を裏返し，$5,6$であれば右端の板を裏返す．
たとえば，最初，板の表の色の並び方が「白白白」であったとし，$1$回目の操作で出たさいころの目が$1$であれば，色の並び方は「黒白白」となる．さらに$2$回目の操作を行って出たさいころの目が$5$であれば，色の並び方は「黒白黒」となる．
(1) 「白白白」から初めて，$3$回の操作の結果，色の並び方が「黒白白」となる確率を求めよ．
(2) 「白白白」から初めて，$n$回の操作の結果，色の並び方が「白白白」または「白黒白」となる確率を求めよ．

ヒント

$\mod 2$で白$(0)$,黒$(1)$として板の状態を$x,y,z$で記録すると？

練習問題の略解

問題１：$f(x)=(\frac{4}{6}+\frac{1}{6}x+\frac{1}{6}x^2)^n$として，$p_n=\frac{1}{3}(f(1)+f(\omega)+f(\omega^2))=\frac{1}{3}+\frac{1}{3}(\frac{1}{2})^{n-1}$

問題２(1)：$f(x)=(\frac{3}{6}+\frac{2}{6}x)^n$として，$a_n=\frac{1}{2}(f(1)+f(-1))=\frac{1}{2}((\frac{5}{6})^n+(\frac{1}{6})^n)$
問題２(2)：$p_n=\frac{1}{6}a_{n-1}=\frac{1}{12}((\frac{5}{6})^{n-1}+(\frac{1}{6})^{n-1})$
問題２(3)：$q_n=\sum_{k=1}^np_k=\frac{1}{2}(\frac{6}{5}-\frac{1}{5}\cdot(\frac{1}{6})^n-(\frac{5}{6})^n)$
問題３(2)：
$f(x,y,z)=(\frac{1}{3}x+\frac{1}{3}y+\frac{1}{3}z)^n$として，「白白白」となる確率$p_n$は$p_n=\frac{1}{8}\sum_{x,y,z\in\{1,-1\}}f(x,y,z)=\frac{1}{8}(1+3(\frac{1}{3})^n+3(-\frac{1}{3})^n+(-1)^n)$
「白黒白」となる確率$q_n$は
$q_n=\frac{1}{8}(\sum_{x,z\in\{1,-1\}}f(x,1,z)-\sum_{x,z\in\{1,-1\}}f(x,-1,z))=\frac{1}{8}(1+(\frac{1}{3})^n-(-\frac{1}{3})^n-(-1)^n)$
$\therefore$求める確率は$p_n+q_n=\frac{1}{4}(1+2(\frac{1}{3})^n+(-\frac{1}{3})^n)$
問題3(1)：「白黒白」となる確率と同じなので$q_3=\frac{7}{27}$