[math]2015年東京医科歯科大学数学問題1

問題
方針
解答
解説
関連問題
関連リンク

問題

$n$を自然数、$m$を$2n$以下の自然数とする。$1$から$n$までの自然数が$1$つずつ記されたカードが、それぞれの数に対して$2$枚ずつ、合計$2n$枚ある。この中から、$m$枚のカードを無作為に選んだとき、それらに記された数がすべて異なる確率を$P_n(m)$と表す。ただし、$P_n(1) = 1$とする。さらに、$E_n(m) = mP_n(m)$とおく。このとき以下の各問いに答えよ。
$(1)$ $P_3(2), P_3(3), P_3(4)$を求めよ。
$(2)$ $E_{10}(m)$が最大になるような$m$を求めよ。
$(3)$ 自然数$n$に対し、$E_n(m) > E_n(m+1)$を満たす自然数$m$の最小値を$f(n)$とするとき、$f(n)$を$n$を用いて表わせ。ただし、ガウス記号$[]$を用いてよい。ここで、実数$x$に対して、$x$を超えない最大の整数を$[x]$と表す。

方針

$P_n(m)$は具体的に求めることができる。$(2), (3)$では$E_n(m+1)$と$E_n(m)$の比を作るのが常套手段である。

解答

$(1)$ $n = 3$のとき、カードは$1, 1, 2, 2, 3, 3$の$6$枚である。この中から$2$枚を選ぶ事象の数は$_{6}{\mathbb{C}}_{2} = 15$通りである。カードが同じになるのは$(1, 1), (2, 2), (3, 3)$の$3$通りで、それ以外の組み合わせはすべてカードは異なる。よって、$\displaystyle P_3(2) = 1-\frac{3}{15} = \underline{\frac{4}{5}}$である。また、$3$枚を選ぶ事象の数は$_{6}{\mathbb{C}}_{3} = 20$通りである。カードが同じになるのは$(1, 1, 2), (1, 1, 2), (1, 1, 3), (1, 1, 3), (2, 2, 1), (2, 2, 1), (2, 2, 3), (2, 2, 3), (3, 3, 1), (3, 3, 1), (3, 3, 2), (3, 3, 2)$の$12$通りで、それ以外の組み合わせはすべてカードは異なる。ただし、同じ数字でもカードを区別した。よって、$\displaystyle P_3(3) = 1-\frac{12}{20} = \underline{\frac{2}{5}}$である。また、$4$枚を選ぶとどのように選んでも同じカードが出てくるので、$\underline{P_3(4) = 0}$である。

$(2), (3)$ $m \geq n+1$のときは、どのような選び方をしても記された数の中で同じものが出てくる（鳩の巣原理）。したがって、$m\geq n$のとき$P_n(m) = 0$である。$1\leq m\leq n$のときを考える。グループ$A$を$(1, 2, \cdots, n)$、グループ$B$を$(1, 2, \cdots, n)$とする。記された数が異なる選び方は、グループ$A$から$i$枚選び、グループ$A$から選んだカードと重複しないグループ$B$のカード$n-i$枚から$m-i$枚を選べば良いので、$\displaystyle P_n(m) = \frac{\sum_{i=0}^{m}{_{n}{\mathbb{C}}_{i}\cdot _{n-i}{\mathbb{C}}_{m-i}}}{_{2n}{\mathbb{C}}_{m}}$である。和の中身を計算すると、$$\begin{eqnarray}\frac{n!}{(n-i)!i!}\cdot \frac{(n-i)!}{(m-i)!(n-i-(m-i))!} & = & \frac{n!}{(n-m)!}\cdot \frac{1}{i!(m-i)!}\\ & = & \frac{n!}{m!(n-m)!}\cdot \frac{m!}{(m-i)!i!}\\ & = & _{n}{\mathbb{C}}_{m}\cdot _{m}{\mathbb{C}}_{i}\end{eqnarray}$$である。したがって、$$\begin{eqnarray}P_n(m) & = & \frac{_{n}{\mathbb{C}}_{m}}{_{2n}{\mathbb{C}}_{m}}\sum_{i=0}^{m}{_{m}{\mathbb{C}}_{i}}\\ & = & \frac{2^m \cdot _{n}{\mathbb{C}}_{m}}{_{2n}{\mathbb{C}}_{m}}\end{eqnarray}$$である。これより、$\displaystyle E_n(m) = \frac{m\cdot 2^m\cdot _{n}{\mathbb{C}}_{m}}{_{2n}{\mathbb{C}}_{m}}$となる。$m = 1, 2, \cdots, n-1$として比を考えると、$$\begin{eqnarray}\frac{E_{n}(m+1)}{E_n(m)} & = & \frac{(m+1)2^{m+1}}{m2^m}\cdot \frac{_{n}{\mathbb{C}}_{m+1}}{_{n}{\mathbb{C}}_{m}}\cdot \frac{_{2n}{\mathbb{C}}_{m}}{_{2n}{\mathbb{C}}_{m+1}}\\ & = & 2\left(1+\frac{1}{m}\right)\cdot \frac{n-m}{m+1}\cdot \frac{m+1}{2n-m}\\ & = & \frac{2(m+1)(n-m)}{m(2n-m)}\end{eqnarray}$$である。この比と$1$との大小を比べる。$$\begin{eqnarray}\frac{2(m+1)(n-m)}{m(2n-m)} = 1 \\ \iff 2(m+1)(n-m) = m(2n-m)\\ \iff 2n = m^2+2m \\ \iff 2n+1 = (m+1)^2 \\ \iff -(m+1+\sqrt{2n+1})(m+1-\sqrt{2n+1}) = 0\end{eqnarray}$$である。したがって、$m=1, 2, \cdots, [\sqrt{2n+1}-1]$までは$\displaystyle E_n(m+1) > E_n(m)$であり、$m = [\sqrt{2n+1}-1]+1, [\sqrt{2n+1}-1]+2, \cdots, n-1$からは$E_{m}(m+1) < E_n(m)$となる。これから、$E_n(m) > E_m(n+1)$を満たす最小の整数は$[\sqrt{2n+1}-1]+1 = [\sqrt{2n+1}]$となるから、$\underline{f(n) = [\sqrt{2n+1}]}$となる。なお、$n=1$のとき$E_1(1) = P_1(1) = 1, E_1(2) = 0$であるから$f(1) = 1$となりこの結果は$n = 1$でも成り立つ。また、$n = 10$のとき$E_{10}(m)$が最大になるのは$[\sqrt{2\times 10+1}] = \underline{4}$である。

解説

鳩の巣原理とは、$n$個のものを$m$個の箱に入れたとき、$n > m$であれば少なくとも$1$個の箱には$1$個よりも多いものが中にあるという原理である。当たり前のようであるが、ときに大きな威力を発揮する。

鳩の巣原理 - Wikipedia

解答では実数$x$に対して$[x-1]+1 = [x]$を用いている。これは、$x$を超えない最大の整数を$m$として、$$\begin{eqnarray}m\leq x < m + 1\\ \iff m-1 \leq x-1 < m \\ \iff [x-1] = m-1\\ \iff [x-1]+1 = m = [x]\end{eqnarray}$$による。