19

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

2077
0

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

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

"状態を多項式で持つ"

2017年京大理系第6問

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

明らかに,条件は出たカードの和が3の倍数となると言い換えられます.
いきなりですが次の多項式を考えます.
f(x)=(15x+15x2+15x3+15x4+15x5)n

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

例えばn=2のとき,
f(x)=(15)2x1+1+(15)2x2+1+(15)2x3+1+(15)2x5+4+(15)2x5+5
となり,xa+bはカードがa,bと出る場合を表しています.
ということはf(x)x3の係数の総和を求めればいいと分かります.

f(x)=(15x+15x2+15+15x+15x2)n=(15+25x+25x2)n
このようにf(x)を定義しても結果は変わらないので慣れてきたらこのようにするといいかもしれないです.以下これで再定義します.

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

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

xmの係数の総和を求める

f(x)=a0+a1x+a2x2+において,xmの係数の総和の求め方を解説します.
先に結論を言うと,ζ=cos(2π/m)+isin(2π/m)として,
1p(f(1)+f(ζ)++f(ζm1))
となります.これは,xm=1の解のk乗和をSkとすると
Sk={mif k0(modm)0otherwise
となるためです.これは次の補題から分かります.(この補題の証明: http://wwu.phoenix-c.or.jp/~tokioka3/k_power/k_power.pdf )

n次方程式f(x)=0n個の解のk乗和をSkとすると次が成り立つ:
xf(x)f(x)=k=0Skxk

さて,例1に戻ります.いま説明したことを使えば,f(x)=(15+25x+25x2)nx3の係数の総和は,ω=cos2π/3+isin2π/3として,ω3=1,ω2+ω+1=0に注意すれば,

13(f(1)+f(ω)+f(ω2))=13+23(15)n

と求められます.

練習問題

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

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

ヒント mod3A(0),B(1),C(2)としてQの場所をxで記録すると?
2011年一橋大第5問

AB2人が,1個のさいころを次の手順により投げ合う.

  • 1回目はAが投げる.
  • 1,2,3の目が出たら,次の回には同じ人が投げる.
  • 4,5の目が出たら,次の回には別の人が投げる.
  • 6の目が出たら,投げた人を勝ちとしてそれ以降は投げない.
  1. n回目にAがさいころを投げる確率anを求めよ.
  2. ちょうどn回目のさいころ投げでAが勝つ確率pnを求めよ.
  3. n回以内のさいころ投げでAが勝つ確率qnを求めよ.
ヒント (1)が出来たらあとは計算するだけですね.投げる人をxで記録すると?

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

考え方は変わりません.

2023年京大理系第3問

nを自然数とする.1個のさいころをn回投げ,出た目を順にX1,X2,,Xnとし,n個の数の積X1X2XnYとする.
(1) Y5で割り切れる確率を求めよ.
(2) Y15で割り切れる確率を求めよ.

Yの素因数3,5の個数をx,yで記録しようと考えると,次の多項式が考えられます:
f(x,y)=(16+16+16x+16+16y+16x)n=(26x+16y+36)n

(1)はf(x,y)におけるxy1の係数の総和,(2)はx1y1の係数の総和を求めればいいです.

(1)g(y)=f(1,y)として,g(y)におけるy1の係数の総和を求めればいいので,定数項がg(0)であることに注意すれば
g(1)g(0)=1(56)n
と求められます.
(2) x1の係数の総和(h(y)とおく)から,y1の係数を求めればいいので
h(y)=f(1,y)f(0,y)=(16y+56)n(16y+36)n
h(1)h(0)=1(23)n(56)n+(12)n
と求められます.

練習問題

2004年東大理系第4問

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

ヒント mod2で白(0),黒(1)として板の状態をx,y,zで記録すると?

練習問題の略解

問題1:f(x)=(46+16x+16x2)nとして,pn=13(f(1)+f(ω)+f(ω2))=13+13(12)n1

問題2(1):f(x)=(36+26x)nとして,an=12(f(1)+f(1))=12((56)n+(16)n)
問題2(2):pn=16an1=112((56)n1+(16)n1)
問題2(3):qn=k=1npk=12(6515(16)n(56)n)
問題3(2):
f(x,y,z)=(13x+13y+13z)nとして,「白白白」となる確率pnpn=18x,y,z{1,1}f(x,y,z)=18(1+3(13)n+3(13)n+(1)n)
「白黒白」となる確率qn
qn=18(x,z{1,1}f(x,1,z)x,z{1,1}f(x,1,z))=18(1+(13)n(13)n(1)n)
求める確率はpn+qn=14(1+2(13)n+(13)n)
問題3(1):「白黒白」となる確率と同じなのでq3=727

おわり

今回は幾つかの受験数学の確率漸化式の問題を多項式・形式的冪級数で倒しました.(形式的冪級数は使いませんでしたが.)すべての問題が必ずしも今回の手法で倒せるとは限らないので注意してください.ここまで読んでいただきありがとうございました.

投稿日:2024117
更新日:2024815
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

c_2
c_2
43
4913
OMC水色.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. "状態を多項式で持つ"
  2. $x^{mの倍数}$の係数の総和を求める
  3. 練習問題
  4. 多変数の多項式を用意する場合
  5. 練習問題
  6. 練習問題の略解
  7. おわり