[math]2001年東京医科歯科大学前期数学問題3

Table of Contents

問題

数の集合\(A\)に関する以下の諸条件を考える。ただし、\(n, k\)は\(n\geq k\geq 0\)を満たす整数とし、\(x, y\)は任意の数とする。
条件\(Z:\) \(x\)が\(A\)の要素ならば\(x\)は整数。
条件\(P_n:\) \(x\)が\(A\)の要素ならば\(1\leq x\)かつ\(x\leq n\)
条件\(Q_k:\) \(A\)はちょうど\(k\)個の要素からなる。
条件\(R:\) \(x, y\)が\(A\)の要素ならば\(x-y+1\ne 0\)
条件\(S_{n, k}:\) \(A\)は\(3\)条件\(Z, P_n, Q_k\)を満たす。
条件\(T_{n, k}:\) \(A\)は条件\(S_{n, k}\)および条件\(R\)を満たす。
条件\(S_{n, k}\)を満たすような集合\(A\)の個数を\(f(n, k)\)と表し、条件\(T_{n, k}\)を満たすような集合\(A\)の個数を\(g(n, k)\)と表す。このとき以下の各問いに答えよ。
\((1)\) \(f(n, 0)\)および\(f(n, n)\)を求めよ。また、\(n > k \geq 1\)のとき\(f(n, k)\)を\(f(n-1, k)\)と\(f(n-1, k-1)\)を用いて表わせ。
\((2)\) \(n > k\geq 1\)のとき\(g(n, k)\)を\(g(n-1, k)\)と\(g(n-2, k-1)\)を用いて表わせ。
\((3)\) \(m\geq 1, l\geq 0\)なる整数\(m, l\)に対して整数\(h(m, l)\)を\(h(m, l) = g(m+l-1, l)\)で定義する。このとき\(h(m, 0)\)および\(h(m, m)\)を求めよ。また\(m > l \geq 1\)のとき\(h(m, l)\)を\(h(m-1, l)\)と\(h(m-1, l-1)\)を用いて表わせ。
\((4)\) \(g(12, 4)\)を求めよ。

方針

問題文は長くて嫌気がさすが、実はそれほど難しくない。

解答

\((1)\) \(f(n, 0)\)は\(0\)個の要素からなる集合で、それは空集合だから、\(\underline{f(n, 0) = 1}\)となる。\(f(n, n)\)は\(n\)個の要素からなる集合で、その要素\(x\)について\(1\leq x\leq n\)となるものの個数である。要素は\(\{1, 2, \cdots, n\}\)となるから、\(\underline{f(n, n) = 1}\)である。
\(n> k\geq 1\)のとき、\(f(n, k)\)は\(k\)個の要素からなる集合で、その要素\(x\)について\(1\leq x\leq n\)となるものの個数である。これは\(n\)個の整数の中から\(k\)個を選ぶ場合の数に等しい。したがって、\(f(n, k) = _{n}{\mathbb{C}}_{k}\)である。一般に、\(_{n}{\mathbb{C}}_{k} = _{n-1}{\mathbb{C}}_{k} + _{n-1}{\mathbb{C}}_{k-1}\)であるから、\(\underline{f(n, k) = f(n-1, k) + f(n-1, k-1)}\)となる。

\((2)\) \(n>k\geq 1\)とする。\(g(n, k)\)は条件\(T_{n, k}\)を満たすような集合\(A\)の個数であるが、その集合が要素に\(n\)を含むかどうかで場合分けしてみる。要素に\(n\)を含む集合は、条件\(R\)から要素に\(n-1\)を含まない。したがって、\(1\)から\(n-2\)までの自然数の中から条件\(R\)を満たすように\(k-1\)個の要素を選び（この選び方は\(g(n-2, k-1)\)）、\(n\)を付け加えた集合は\(T_{n, k}\)を満たす。また、要素に\(n\)を含まない集合は、\(1\)から\(n-1\)までの自然数の中から条件\(R\)を満たすように\(k\)個の要素を選べば良い（この選び方は\(g(n-1, k)\)）。これから、\(\underline{g(n, k) = g(n-1, k) + g(n-2, k-1)}\)であることがわかる。

\((3)\) \(h(m, l) = g(m+l-1, l)\)であるから、\(h(m, 0) = g(m-1, 0)\)である。\((1)\)の\(f(n, 0)\)の場合と同様に、一般に\(g(n, 0) = 1\)であるから、\(\underline{h(m, 0) = 1}\)である。また、\(h(m, m) = g(2m-1, m)\)である。これは\(2m-1\)個の要素からなる集合で、その要素\(x, y\)について、\(1\leq x, y\leq 2m-1, x-y+1\ne 0\)となるものの個数である。すなわち、要素は具体的に\(\{1, 3, 4, \cdots, 2m-1\}\)となるから、\(g(2m-1, m) = 1\)である。よって、\(\underline{h(m, m) = 1}\)となる。

\((4)\) \(g(12, 4) = h(9, 4)\)である。\((1), (3)\)から\(f(n, 0) = h(n, 0), f(n, n) = h(n, n)\)であり、\(f(n, k)\)と\(h(m, l)\)が同じ漸化式を満たすことから、\(f(n, k) = h(n, k)\)である。\((1)\)から\(f(9, 4) = _9{\mathbb{C}}_4 = 126\)であるから、\(\underline{g(12, 4) = 126}\)となる。

解説

\((1)\)はすぐに\(_n{\mathbb{C}}_k\)のことだと分かり、何のために漸化式を作らなくてはいけないのか不思議に思ったものも多かったことだろう。しかしこれが\((4)\)の強力なヒントになっている。\((2)\)も落ち着いてよく考えれば、それほどのことはない。結論がすぐに見えてどう表現するか迷ったものも多かったかもしれない。手を動かすのをサボらずに自分で解答を作るように心がけてのが良い。解答を読むだけでは試験に必要な表現能力は身に付かない。\((3)\)も\((2)\)と同じくしっかりと表現できたかどうかで点が左右されそうな問題である。

メインが\((4)\)になる。落ち着いて\(f(n, k)\)と\(h(m, l)\)を見比べるとこれが同じものであることに気がつく。答えに急ぎたくなるが、落ち着いて考えさせる良問であると言えよう。直接\((3)\)の漸化式を使うと\((4)\)だけで\(30\)分くらい時間が掛かりるので、医科歯科の受験生のレベルを考えると少し不利な解答だろう。過去問で似たような問題が出題されており、医科歯科の数学、理科は過去問をしっかり研究したものには、大きいアドバンテージがある。