東北大学 2005年 理系 第3問 解説

方針・初手

得点が $k$ になるとは、$k-1$ 回目までは引いた数が毎回 strictly increasing であり、$k$ 回目で初めて「直前以下」になることである。

したがって、まず

• $X_1,X_2,\dots$ を各回に引いた数字とする
• 得点が $k$ である条件を $X_1<X_2<\cdots<X_{k-1}$ かつ $X_k\leqq X_{k-1}$

と整理して数えるのが自然である。

期待値は、確率分布から直接計算してもよいが、$P(\text{得点}\geqq k)$ を用いると簡潔に求まる。

解法1

各回に引いた数字を $X_1,X_2,\dots$ とする。 $X_i$ はそれぞれ独立に $1,2,\dots,n$ のいずれかを確率 $\dfrac1n$ でとる。

(1) 得点が $k$ となる確率

$2\leqq k\leqq n+1$ とする。

得点が $k$ であるための条件は

$$ X_1<X_2<\cdots<X_{k-1},\qquad X_k\leqq X_{k-1} $$

である。

ここで、$X_{k-1}=j$ とおくと、$j$ は少なくとも $k-1$ 以上である。 実際、$X_1<X_2<\cdots<X_{k-1}=j$ となるには、$1,2,\dots,j-1$ の中から $k-2$ 個を選んで昇順に並べるしかないので、そのような並び方は

$$ {}_{j-1}\mathrm{C}_{k-2} $$

通りである。

さらに $X_k\leqq j$ となる選び方は $j$ 通りある。 したがって、得点が $k$ であり、かつ $X_{k-1}=j$ となる確率は

$$ {}_{j-1}\mathrm{C}_{k-2}\cdot j\cdot \frac1{n^k} $$

である。

よって

$$ P(\text{得点}=k) =\frac1{n^k}\sum_{j=k-1}^{n}j{}_{j-1}\mathrm{C}_{k-2}. $$

ここで

$$ j{}_{j-1}\mathrm{C}_{k-2}=(k-1){}_{j}\mathrm{C}_{k-1} $$

であるから、

$$ P(\text{得点}=k) =\frac{k-1}{n^k}\sum_{j=k-1}^{n}{}_{j}\mathrm{C}_{k-1}. $$

さらに、階差和の公式

$$ \sum_{j=k-1}^{n}{}_{j}\mathrm{C}_{k-1}={}_{n+1}\mathrm{C}_{k} $$

を用いると、

$$ P(\text{得点}=k)=\frac{(k-1){}_{n+1}\mathrm{C}_{k}}{n^k} \qquad (2\leqq k\leqq n+1) $$

を得る。

(2) 期待値 $f(n)$ とその極限

得点を $S$ とする。 一般に

$$ E[S]=\sum_{k\geqq1}P(S\geqq k) $$

が成り立つ。

ここで $S\geqq k$ であることは、$k-1$ 回目までは終了していないこと、すなわち

$$ X_1<X_2<\cdots<X_{k-1} $$

が成り立つことと同値である。

$1,2,\dots,n$ から異なる $k-1$ 個を選び、それらを昇順に並べればこの条件を満たす列がちょうど 1 つ定まるので、そのような列の総数は

$$ {}_{n}\mathrm{C}_{k-1} $$

通りである。したがって

$$ P(S\geqq k)=\frac{{}_{n}\mathrm{C}_{k-1}}{n^{k-1}} \qquad (1\leqq k\leqq n+1) $$

である。

よって

$$ f(n)=E[S] =\sum_{k=1}^{n+1}\frac{{}_{n}\mathrm{C}_{k-1}}{n^{k-1}}. $$

$r=k-1$ とおくと

$$ f(n)=\sum_{r=0}^{n}{}_{n}\mathrm{C}_{r}\frac1{n^r} =\left(1+\frac1n\right)^n. $$

したがって

$$ \lim_{n\to\infty}f(n) =\lim_{n\to\infty}\left(1+\frac1n\right)^n =e $$

である。

解説

この問題の本質は、「終了するまでの間、引いた数列は strictly increasing である」という構造を見抜くことである。

(1) では、最後の成功値 $X_{k-1}=j$ を固定すると数えやすい。 $j$ を固定すれば、その前は $1,\dots,j-1$ から $k-2$ 個を選ぶだけであり、最後の $X_k$ は $1,\dots,j$ のどれでもよい。

(2) では期待値を分布から直接計算するよりも、$P(S\geqq k)$ を使う方が短い。 「少なくとも $k$ 点」という条件は「最初の $k-1$ 個が昇順」と言い換えられるので、二項定理にそのまま落ちる。

答え

$$ P(\text{得点}=k)=\frac{(k-1){}_{n+1}\mathrm{C}_{k}}{n^k} \qquad (2\leqq k\leqq n+1) $$

$$ f(n)=\left(1+\frac1n\right)^n $$

$$ \lim_{n\to\infty}f(n)=e $$