横浜市立大学
2013年 国際総合学部 第2問
2
2
$n$個のボールと,$1$から$n$までの番号がふられた$n$個の空の箱がある.また,$1$から$n$の番号が書かれた$n$枚のカードが袋の中に入っている.いま,以下の手順に従いボールを箱の中に入れていくことを考える.
手順$1$ \quad 袋からカードを$1$枚無作為に取り出して,手順$2$に進む.
手順$2$ \quad 手順$1$で取り出したカードに書かれている番号の箱が, \begin{itemize}
空ならば,そこにボールを$1$つ入れて,手順$3$へ進む.
空でなければ,カードを袋に戻さず手元に置き,手順$1$に戻る. \end{itemize}
手順$3$ \quad 手元のすべてのカードを袋に戻す.この時点で, \begin{itemize}
すべての箱にボールが入っていれば終了する.
空の箱が$1$つでもあれば,手順$1$に戻る. \end{itemize}
また,$1 \leqq k \leqq n$を満たす自然数$k$について,$k-1$個目のボールを箱に入れ終わった状態(ただし,$k=1$のときは,はじめの状態とする)の後に, \begin{itemize}
次のボール,すなわち$k$個目のボールを箱に入れるまでにちょうど$i$枚のカードを袋から取り出す確率を$P_k(i)$とし,
$i$枚のカードを袋から取り出してもまだ次のボールを箱に入れることができない確率を$Q_k(i)$とする.ただし,$Q_k(0)=1$とする. \end{itemize} このとき,以下の問いに答えよ.
(1) $n=4$のとき$P_3(1)$,$P_3(2)$,$Q_3(2)$をそれぞれ求めよ.
(2) $Q_k(i)$を$P_k(i+1)$,$P_k(i+2)$,$\cdots$,$P_k(k)$を用いて表せ.ただし,$0 \leqq i \leqq k-1$とする.
(3) $k-1$個目のボールを箱に入れてから$k$個目のボールを箱に入れるまでに袋から取り出すカードの枚数の期待値$E_k$は$Q_k(0)+Q_k(1)+\cdots +Q_k(k-1)$であることを示せ.
(4) 不等式 \[ E_k \leqq \frac{n}{n-k+1} \] が成り立つことを示せ.
(5) 不等式 \[ E_1+E_2+\cdots +E_n \leqq n+n \log n \] が成り立つことを示せ.
手順$1$ \quad 袋からカードを$1$枚無作為に取り出して,手順$2$に進む.
手順$2$ \quad 手順$1$で取り出したカードに書かれている番号の箱が, \begin{itemize}
空ならば,そこにボールを$1$つ入れて,手順$3$へ進む.
空でなければ,カードを袋に戻さず手元に置き,手順$1$に戻る. \end{itemize}
手順$3$ \quad 手元のすべてのカードを袋に戻す.この時点で, \begin{itemize}
すべての箱にボールが入っていれば終了する.
空の箱が$1$つでもあれば,手順$1$に戻る. \end{itemize}
また,$1 \leqq k \leqq n$を満たす自然数$k$について,$k-1$個目のボールを箱に入れ終わった状態(ただし,$k=1$のときは,はじめの状態とする)の後に, \begin{itemize}
次のボール,すなわち$k$個目のボールを箱に入れるまでにちょうど$i$枚のカードを袋から取り出す確率を$P_k(i)$とし,
$i$枚のカードを袋から取り出してもまだ次のボールを箱に入れることができない確率を$Q_k(i)$とする.ただし,$Q_k(0)=1$とする. \end{itemize} このとき,以下の問いに答えよ.
(1) $n=4$のとき$P_3(1)$,$P_3(2)$,$Q_3(2)$をそれぞれ求めよ.
(2) $Q_k(i)$を$P_k(i+1)$,$P_k(i+2)$,$\cdots$,$P_k(k)$を用いて表せ.ただし,$0 \leqq i \leqq k-1$とする.
(3) $k-1$個目のボールを箱に入れてから$k$個目のボールを箱に入れるまでに袋から取り出すカードの枚数の期待値$E_k$は$Q_k(0)+Q_k(1)+\cdots +Q_k(k-1)$であることを示せ.
(4) 不等式 \[ E_k \leqq \frac{n}{n-k+1} \] が成り立つことを示せ.
(5) 不等式 \[ E_1+E_2+\cdots +E_n \leqq n+n \log n \] が成り立つことを示せ.
コメント(1件)
2015-07-20 22:04:54
解説お願いします |
書き込むにはログインが必要です。