Twitterで出した問題の解説

はじめに

この記事では, 次の問題を解説しようと思います. 高校範囲は少し超えます.

たぶん結構長くなりますが, よろしくお願いします.
${}$

漸化式を立てる

この問題は, 一人ずつ座っていく, ということですので, 漸化式が立てられそうだと考えてみます.
${}$

まずは初めの方の項を求めてみますと, $E_0=0,\ E_1=1,\ E_2=1$ のようになります.

次に$E_3$を考えてみましょう. $1$人目が確率$\frac13$で真ん中に座った場合は全部で$1$人, $1$人目が確率$\frac23$で端に座った場合は全部で$2$人, が座ることができますから, この期待値は$\frac13\cdot1+\frac23\cdot2=\frac53$ となります.
${}$

ではこれをもとに, 漸化式を立てていきましょう.
${}$

$n$個の席があるとき, $1$人目が$\frac1n$の確率で左から$k$番目$(1\leq k\leq n)$ の席に座ったとします. すると, 残りの席に座れる人数の期待値を, 前の項を使って表すことができます.

即ち, このとき, 左側の$1\sim(k-2)$番目の席と, 右側の$(k+2)\sim n$番目の席について, 座れる人数の期待値はそれぞれ$E_{k-2},\ E_{n-k-1}$ となります. ただし$E_{-1}=0$とします.

(これは, 左側に座る確率と右側に座る確率が独立ではないので変に思えますが, 期待値は独立でなくても加法性が成り立つので大丈夫です.)

従って, $1$人目が$k$番目の席に座ったときの, 座れる人数の期待値は, $1$人目を含めて$1+E_{k-2}+E_{n-k-1}$となります.
${}$

以上より, $E_n$は$k$を$1$から$n$まで変化させたときのこれの和ですので,

$$\beq E_n&=&\frac1n\sum_{k=1}^n\big(1+E_{k-2}+E_{n-k-1}\big)\\ &=&1+\frac1n\sum_{k=1}^nE_{k-2}+\frac1n\sum_{k=1}^nE_{n-k-1}\\ &=&1+\frac2n\sum_{k=0}^{n-2}E_k \eeq$$

と, 漸化式を立てることができました.
${}$

漸化式を解く

${}$

この漸化式を解きたいのですが, 少し難しそうですし, 最終的な目標は極限ですので, ここでは母関数を用いて解いてみたいと思います.

ただし, 見慣れた形が良いので, $a_n=E_n$とおかせてもらいます.

また, 説明のために下のように書き換えます.

${}$

まず, $\ds f(x)=\sumn{0}a_nx^n$ とおきます.

母関数に$\frac1{1-x}$を掛けると係数が足されて,
$$\frac{f(x)}{1-x}=\sumn{0}\bigg(\sum_{k=0}^na_k\bigg)x^n$$
即ち
$$\sumn{2}\bigg(\sum_{k=0}^{n-2}a_k\bigg)x^n=\frac{x^2}{1-x}f(x)$$
となります.
${}$

次に $\ds\sumn{0}x^n=\frac1{1-x}$ですので,
$$\sumn{0}\big(a_n-1\big)x^n=f(x)-\frac1{1-x}$$
です. 両辺を微分して,
$$\sumn{1}n\big(a_n-1\big)x^{n-1}=f'(x)-\frac1{(1-x)^2}$$
即ち
$$\sumn{2}\frac n2\big(a_n-1\big)x^n=\frac x2\bigg(f'(x)-\frac1{(1-x)^2}\bigg)$$
となります.
${}$

以上の$2$式の各項の係数が等しいので関数として等しく,
$$\frac{x^2}{1-x}f(x)=\frac x2\bigg(f'(x)-\frac1{(1-x)^2}\bigg)$$
即ち
$$ f'(x)=\frac{2x}{1-x}f(x)+\frac1{(1-x)^2}$$
なる微分方程式を得ました.
${}$

微分方程式を解く

では, 前節で得た微分方程式

を解いていきましょう.
${}$

一般に, $y,p,q$を$x$の関数として微分方程式$y'=py+q$の解は, 置き換えとかをして工夫することで $\ds y=e^{\int p\,dx}\cdot\bigg(\int qe^{-\int p\,dx}\,dx+C\bigg)$ となることから解くことができます.
${}$

今回は,
$$\beq p&=&\frac{2x}{1-x}=\frac2{1-x}-2\\ q&=&\frac1{(1-x)^2} \eeq$$
ですので,
$$\beq \int p\,dx&=&-2\log(1-x)-2x\\ e^{\int p\,dx}&=&\frac{e^{-2x}}{(1-x)^2}\\ \int qe^{-\int p\,dx}\,dx&=&\int e^{2x}\,dx\\ &=&\frac{e^{2x}}{2} \eeq$$
と, 奇跡的に(？)とても綺麗に解くことができ,
$$\beq&& y=\frac{e^{-2x}}{(1-x)^2}\bigg(\frac{e^{2x}}{2}+C\bigg)\eeq$$
となります.

最後に$f(0)=0$から,$\ds C=-\frac12$とわかり,
$$\beq&& f(x)=\frac{1-e^{-2x}}{2(1-x)^2}\eeq$$
を得ました！
${}$

極限を求める

最後に極限を求めていきましょう.

この右辺をTaylor展開することで$a_n$を明示することもできますが(実際にはΣが残ってしまいます), 母関数から直接極限を求めてみます.

$a_0=0$なので,
$$\beq \limn\frac{a_n}n&=&\limn\sum_{k=1}^n\Big(\frac{a_k}k-\frac{a_{k-1}}{k-1}\Big)\\ &=&\lim_{x\to1}\ (1-x)\sumn{1}\frac{a_n}nx^n\\ &=&\lim_{x\to1}\ (1-x)\int_0^x\frac{1-e^{-2t}}{2t(1-t)^2}\,dt\\ &=&\frac{1-e^{-2}}2 \eeq$$
と求められました！ ただし最後にロピタルの定理を使いました.
${}$

おわりに

以上の長い計算から, 隣り合わせにならないように各人が順番に座っていくと, 大体 $\ds\frac12-\frac1{2e^2}$くらいの席が埋まるということが分かりました！

これは面白いですね. これ, 極限値は明らかに$\frac12$と$\frac13$の間にあるので, 私はてっきり$\frac1e$に収束するものと思ったのですが, それとは少し違う形が出てきてびっくりしました.

では, ここまで読んで下さった方, 本当にありがとうございました.

${}$