1

2024東工大数学大問4を母関数で楽に解く [文系でもok]

605
0
$$$$

前提知識

 $(1)$は文系の方でも大丈夫です。
 $(3)$は最後数3の知識を使いますが、この記事で伝えたい本質的な部分とは逸れるので数2Bまでの知識があれば大丈夫です。

問題

次の問題を考えます。

東工大数学2024 大問4

$n$ を正の整数とし,$C_1, C_2, \dots, C_n$$n$ 枚の硬貨とする.各 $k=1, \dots, n$ に対し,硬貨 $C_k$ を投げて表が出る確率を $p_k$,裏が出る確率を $1 - p_k$ とする.この $n$ 枚の硬貨を同時に投げ,表が出た硬貨の枚数が奇数であれば成功,というゲームを考える.
$(1)$ $p_k = \frac{1}{3} (k=1, \cdots ,n)$ のとき, このゲームで成功する確率$X_n$を求めよ.
$(2)$ 省略
$(3)$ $n = 3m$ ($m$ は正の整数) で,$k = 1, \dots, 3m$ に対して,
$p_k = \begin{cases} \frac{1}{3m} & (k = 1, \dots, m) \\ \frac{2}{3m} & (k = m+1, \dots, 2m) \\ \frac{1}{m} & (k = 2m+1, \dots, 3m) \end{cases}$ とする.
このゲームで成功する確率を $Z_{3m}$ とするとき, $lim_{m \to \infty} Z_{3m} $を求めよ.

(2)は考え方的には独立しているので省略しました。
(3)の予備校等の出す解答(東工大の想定している解法?)は非常に長く乱雑で、試験本番でミスなく書けるかと言われると厳しいです。ですが、紹介する母関数という多項式の問題に帰着させるテクニックを使うことで本セット最難問であろうこの問題をあっさり解くことができます。

(1) 母関数を使った解法

わざわざ母関数という言葉を持ち出さずとも解ける問題ではありますが、母関数を初めて知った人のためにあえて書きます。

\begin{align} & f(x) = \left( \frac{1}{3}x + \frac{2}{3} \right)^n \tag{1}\\ & この多項式を展開した後の式を以下のように定義します \\ & f(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 + \cdots \tag{2}\\ & 自然数Nについて, x^Nの係数a_Nは, N回コインの表が出る確率を表している\\ & 今ここで, 我々が求めたいのはコインの表が奇数回出る確率X_nである. 従って \\ & X_n = a_1 + a_3 + a_5 + a_7 + \cdots \\ & である. ところで \\ & f(1) = a_0 + a_1 + a_2 + a_3 + a_4 + a_5 + \cdots \tag{3}\\ & f(-1) = a_0 - a_1 + a_2 - a_3 + a_4 - a_5 + \cdots \tag{4}\\ & であるために \\ & X_n = \frac{f(1) - f(-1)}{2} = \frac{ 1 - \left( \frac{1}{3}(-1) + \frac{2}{3} \right)^n }{2} = \frac{1}{2} - \frac{1}{2 \cdot 3^n} \end{align}

 なぜこの解法が上手くいくのでしょうか。
 特に、多項式の係数とN回表が出る確率が対応するのはなぜでしょうか。そもそもの話、求めたい確率は以下のものです。
\begin{align} & {}_n \mathrm{C}_1(\frac{1}{3})^1(\frac{2}{3})^{n-1} + {}_n \mathrm{C}_3(\frac{1}{3})^3(\frac{2}{3})^{n-3} + {}_n \mathrm{C}_5(\frac{1}{3})^5(\frac{2}{3})^{n-5} + \cdots \end{align}

ここで、以下の式を考えてください。

$f(1) = (\frac{1}{3} + \frac{2}{3})^n = (\frac{1}{3} + \frac{2}{3}) (\frac{1}{3} + \frac{2}{3}) (\frac{1}{3} + \frac{2}{3}) \cdots$

$\frac{1}{3}$$\frac{2}{3}$の項をどちらか選んで掛ける操作を$n$回繰り返すのでこの多項式の展開は、場合の数あるいは確率の計算と等価であることがわかります。
特に、$\frac{1}{3}$を奇数回だけ掛ける操作を繰り返した時の結果の和を考えることができれば求めたい確率を求められます。その操作が、上記を解答でしたことです。

(3) 母関数を使った解法

\begin{align*} g(x) &= \left( \frac{1}{3m}x + \left( 1 - \frac{1}{3m} \right) \right)^m \cdot \left( \frac{2}{3m}x + \left( 1 - \frac{2}{3m} \right) \right)^m \cdot \left( \frac{1}{m}x + \left( 1 - \frac{1}{m} \right) \right)^m \\ \end{align*}

$(1)$ の時と同様に、求めたいのはこの式を展開した後の$x$の奇数乗の係数の和である。
\begin{align*} \\ & \therefore Z_{3m} = \frac{g(1) - g(-1)}{2} \\ \end{align*}
また
\begin{align*} g(1) &= 1 \\ g(-1) &= \left(1 - \frac{2}{3m}\right)^m \cdot \left(1 - \frac{4}{3m}\right)^m \cdot \left(1 - \frac{2}{m}\right)^m \\ \end{align*}

である。あとは $m \to \infty$ に飛ばした時の値を考えればよく、$e$ の定義に着目することで次のようになる。 (数3の内容なので分からなくてok)

\begin{align*} \lim_{m \to \infty} \left(1 - \frac{2}{3m}\right)^m &= e^{-\frac{2}{3}} \\ \lim_{m \to \infty} \left(1 - \frac{4}{3m}\right)^m &= e^{-\frac{4}{3}} \\ \lim_{m \to \infty} \left(1 - \frac{2}{m}\right)^m &= e^{-2} \\ \end{align*}

よって、求める答えは以下のようになる。

\begin{align*} \lim_{m \to \infty} Z_{3m} &= \frac{1}{2} - \frac{e^{-4}}{2} \end{align*}

 あっさり解けちゃいましたね。
 このような問題は多項式の問題に帰着させることで発想が要らなくなり、計算量が大幅に少なくできます。

入試本番でも使えるのか?

 私は入試本番もこの解法で解きましたが、開示を見たらちゃんと点数が来ていたので特に問題ないと思われます。

あとがき

 誰かこういう記事を上げるだろうなと思っていたのですが(Twitterなどを見る限り同様の解法を思いついた人はいるっぽい)実際の解答を載せている人は軽く探した限りいなかったのでmathlogに載せてみました。

 ちなみにですが、このテクニックは2023東工大数学大問3でも使えます。

 母関数をもっと知りたい方へ
  https://mathlog.info/articles/2628
  https://mathlog.info/articles/377
  https://x.com/keisankionwykip/status/1591413396339314688?s=46&t=gcnkU9RlPJrASRER34fVjQ

投稿日:98
OptHub AI Competition

この記事を高評価した人

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

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

バッジはありません。

投稿者

I LOVE CAT VERY VERY MUCH.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中