Twitterで出した問題の解説

514

はじめに

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

n

個の連続した座席があり, 順番に人が座ってゆきます.

ただし座る位置は, 既に座っている人の隣でない席から任意に選ぶとします.

　限界まで座ったときに座っている人数の期待値を

E_{n}

とするとき,

極限値

lim_{n \to \infty} \frac{E_{n}}{n}

を求めてください.

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

漸化式を立てる

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

まずは初めの方の項を求めてみますと, $E_{0} = 0, E_{1} = 1, E_{2} = 1$ のようになります.

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

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

$n$ 個の席があるとき, $1$ 人目が $\frac{1}{n}$ の確率で左から $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$ まで変化させたときのこれの和ですので,

$\begin{array}{rcl} E_{n} & = & \frac{1}{n} \sum_{k = 1}^{n} (1 + E_{k - 2} + E_{n - k - 1}) \\ = & 1 + \frac{1}{n} \sum_{k = 1}^{n} E_{k - 2} + \frac{1}{n} \sum_{k = 1}^{n} E_{n - k - 1} \\ = & 1 + \frac{2}{n} \sum_{k = 0}^{n - 2} E_{k} \end{array}$

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

漸化式を解く

E_{n} = 1 + \frac{2}{n} \sum_{k = 0}^{n - 2} E_{k}

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

ただし, 見慣れた形が良いので, $a_{n} = E_{n}$ とおかせてもらいます.

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

\sum_{k = 0}^{n - 2} a_{k} = \frac{n}{2} (a_{n} - 1)

まず, $f (x) = \sum_{n = 0}^{\infty} a_{n} x^{n}$ とおきます.

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

次に $\sum_{n = 0}^{\infty} x^{n} = \frac{1}{1 - x}$ ですので,
$\sum_{n = 0}^{\infty} (a_{n} - 1) x^{n} = f (x) - \frac{1}{1 - x}$
です. 両辺を微分して,
$\sum_{n = 1}^{\infty} n (a_{n} - 1) x^{n - 1} = f^{'} (x) - \frac{1}{(1 - x)^{2}}$
即ち
$\sum_{n = 2}^{\infty} \frac{n}{2} (a_{n} - 1) x^{n} = \frac{x}{2} (f^{'} (x) - \frac{1}{(1 - x)^{2}})$
となります.

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

微分方程式を解く

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

y^{'} = \frac{2 x}{1 - x} y + \frac{1}{(1 - x)^{2}}

を解いていきましょう.

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

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

最後に $f (0) = 0$ から, $C = - \frac{1}{2}$ とわかり,
$\begin{array}{rcl} f (x) = \frac{1 - e^{- 2 x}}{2 (1 - x)^{2}} \end{array}$
を得ました！

極限を求める

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

\sum_{n = 0}^{\infty} a_{n} x^{n} = \frac{1 - e^{- 2 x}}{2 (1 - x)^{2}}

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

$a_{0} = 0$ なので,
$\begin{array}{rcl} lim_{n \to \infty} \frac{a_{n}}{n} & = & lim_{n \to \infty} \sum_{k = 1}^{n} (\frac{a_{k}}{k} - \frac{a_{k - 1}}{k - 1}) \\ = & lim_{x \to 1} (1 - x) \sum_{n = 1}^{\infty} \frac{a_{n}}{n} x^{n} \\ = & lim_{x \to 1} (1 - x) \int_{0}^{x} \frac{1 - e^{- 2 t}}{2 t (1 - t)^{2}} d t \\ = & \frac{1 - e^{- 2}}{2} \end{array}$
と求められました！ただし最後にロピタルの定理を使いました.