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

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

問題

自然数$n$に対し、$3$個の数字$1, 2, 3$から重複を許して$n$個並べたもの$(x_1, x_2, \cdots, x_n)$の全体の集合を$S_n$とおく。$S_n$の要素$(x_1, x_2, \cdots, x_n)$に対し、次の$2$つの条件を考える。
条件$C_{12}: $ $1\leq i< j\leq n$である整数$i, j$の組で、$x_i = 1, x_j = 2$を満たすものが少なくとも$1$つ存在する。
条件$C_{123}: $ $1\leq i<j < k \leq n$である整数$i, j, k$の組で、$x_i = 1, x_j = 2, x_k = 3$を満たすものが少なくとも$1$つ存在する。
例えば、$S_4$の要素$(3, 1, 2, 2)$は条件$C_{12}$を満たすが、条件$C_{123}$は満たさない。$S_n$の要素$(x_1, x_2, _\cdots, x_n)$のうち、条件$C_{12}$を満たさない・・・・・ものの個数を$f(n)$、条件$C_{123}$を満たさない・・・・・ものの個数を$g(n)$とおく。このとき以下の各問いに答えよ。
$(1)$ $f(4)$と$g(4)$を求めよ。
$(2)$ $f(n)$を$n$を用いて表わせ。
$(3)$ $g(n+1)$を$g(n)$と$f(n)$を用いて表わせ。
$(4)$ $g(n)$を$n$を用いて表わせ。

方針

$f(n)$については、一番最初に出る$1$の位置で場合分けして考えると良い。

解答

$f(n)$の中で、$1$が最初に出る位置を$i\ \ (i = 1, 2, \cdots, n, n+1)$とする。ただし、$i = n+1$のときは$1$が出ないものと考える。$x_1, x_2, \cdots, x_{i-1}$までは$2$か$3$のどちらかが出て、$x_{i+1}, x_{i+2}, \cdots, x_{n}$は$1$か$3$のどちらかが出る。この場合の数は、$2^{i-1}\times 2^{n-i} = 2^{n-1}$通りである。$i = 1, 2, \cdots, n$として、最後に、$1$が一回も出ない場合$2^{n}$を足すと、$f(n) = 2^{n-1}\cdot n + 2^n = \underline{2^{n-1}(n+2)}$である。

また、$g(n)$の中で$f(n)$となるものとそうでないもの（条件$C_{12}$を満たすもの）が存在するが、$f(n)$となるものについては$x_{n+1} = 1, 2, 3$どれでも選んで良い（$g(n+1)$を作ることができる）。$f(n)$とならないものについては$x_{n+1} = 1, 2$とすれば$g(n+1)$になるので、$g(n+1) = 3f(n) + 2(g(n)-f(n)) = \underline{f(n) + 2g(n)}$である。

これから$g(n+1) = 2g(n) + 2^{n-1}(n+2)$となる。また、$n = 1, 2$のとき条件$C_{123}$を満たす$S_n$の要素はないので、$g(1) = 3, g(2) = 9$である。$$\begin{eqnarray}g(n+1) & = & 2g(n) + 2^{n-1}(n+2)\\ \frac{g(n+1)}{2^{n+1}} & = & \frac{g(n)}{2^n} + \frac{n+2}{4}\end{eqnarray}$$である。$\displaystyle \frac{g(n)}{2^n} = h(n)$とすると、$$h(n+1) = h(n) + \frac{n+2}{4}\\ h(1) = \frac{3}{2}, h(2) = \frac{9}{2}$$である。したがって、$$\begin{eqnarray}h(n) & = & \sum_{k=1}^{n-1}{\left(\frac{k+2}{4}\right)} + h(1) \\ & = & \frac{1}{4}\left(3+4+\cdots + (n+1)\right) + \frac{3}{2}\\ & = & \frac{1}{4}\left(1+2+\cdots + (n+1)\right)-\frac{1+2}{4}+\frac{3}{2}\\ & = & \frac{1}{4}\cdot \frac{(n+1)(n+2)}{2}+\frac{3}{4}\\ & = & \frac{n^2+3n+8}{8}\end{eqnarray}$$である。これより$\displaystyle g(n) = 2^nh(n) = \underline{2^{n-3}(n^2+3n+8)}$である。これは$n = 1$で成り立つ。

$(1)$ $f(4) = 2^3(4+2) = \underline{48}, g(4) = 2(16+12+8) = \underline{72}$である。

$(2)$ $f(n) = 2^{n-1}(n+2)$である。

$(3)$ $g(n+1) = f(n) + 2g(n)$である。

$(4)$ $g(n) = 2^{n-3}(n^2+3n+8)$である。

解説

最後の$x_n$が$1, 2, 3$のどれかで場合分けしたくなるが、$x_1, x_2, \cdots$のどれかに$1$があるとややこしくなるので、こういう場合はどこで最初に$1$が出るかを考えると良い。$g(n)$の漸化式を作ると指数が入った式が立つが、$2^{n}$で割る手法は身につけておきたい。