東京大学 1981年度理系数学第1問解答・解説

問題

$S = {1, 2, \dots, n}$ ，ただし $n ≧ 2$ ，とする．2つの要素から成る $S$ の部分集合を $k$ 個とり出し，そのうちのどの2つも交わりが空集合であるようにする方法は何通りあるか．
つぎに，この数(つまり何通りあるかを表す数)を $f (n, k)$ で表したとき， $f (n, k) = f (n, 1)$ をみたすような $n$ と $k$ (ただし， $k ≧ 2$ )をすべて求めよ．

出典：東京大学 1981年度前期日程第2次学力試験理系第1問

方針

互いに交わらない2要素部分集合を $k$ 個選ぶには、まず使う $2 k$ 個の元を選び、それを順序のない2個組 $k$ 個に分ける。したがって $2 k > n$ なら0通り、 $2 k ≦ n$ なら $n! / (n - 2 k)! 2^{k} k!$ 通りである。これを $f (n, 1) = n (n - 1) /2$ と等置し、 $k = 2, 3$ を直接調べる。 $k ≧ 4$ は左辺の積が最小でも十分大きいことを示して除く。

解答

まず $2 k > n$ のときは、互いに交わらない2要素集合を $k$ 個作るための元が足りないので $f (n, k) = 0$ である。以下 $2 k ≦ n$ とする。

互いに交わらない2要素部分集合を $k$ 個選ぶには、まず $S$ から使う $2 k$ 個の元を選ぶ。選んだ $2 k$ 個を2個ずつの組に分ける方法は $\frac{( 2 k )!}{2 ^{k} k !}$ 通りである。したがって

f (n, k) =_{n} C_{2 k} \frac{( 2 k )!}{2 ^{k} k !} = \frac{n !}{( n - 2 k )! 2 ^{k} k !}

である。

また $f (n, 1) =_{n} C_{2} = \frac{n ( n - 1 )}{2}$ である。 $k ≧ 2$ で $f (n, k) = f (n, 1)$ とすると、 $2 k ≦ n$ でなければならず、両辺を整理して $\frac{( n - 2 )!}{( n - 2 k )!} = 2^{k - 1} k!$ を得る。 $k = 2$ のときは $(n - 2) (n - 3) = 4$ である。しかし $n ≧ 4$ なので左辺は $2 \cdot 1 = 2$ , $3 \cdot 2 = 6$ , $4 \cdot 3 = 12$ , $\dots$ と増加し、4にはならない。したがって解はない。 $k = 3$ のときは $(n - 2) (n - 3) (n - 4) (n - 5) = 24$ である。 $n ≧ 6$ であり、 $n = 6$ のとき左辺は $4 \cdot 3 \cdot 2 \cdot 1 = 24$ となる。 $n ≧ 7$ では左辺はこれより大きいので、解は $n = 6$ だけである。

最後に $k ≧ 4$ を考える。 $n ≧ 2 k$ だから

\frac{( n - 2 )!}{( n - 2 k )!} ≧ (2 k - 2)!

である。ここで

R_{k} = \frac{( 2 k - 2 )!}{2 ^{k - 1} k !}

とおくと、 $R_{4} = 15/4 > 1$ であり、

\frac{R _{k + 1}}{R _{k}} = \frac{( 2 k ) ( 2 k - 1 )}{2 ( k + 1 )} = \frac{k ( 2 k - 1 )}{k + 1} > 1 (k ≧ 4)

である。したがって $(2 k - 2)! > 2^{k - 1} k!$ がすべての $k ≧ 4$ で成り立ち、等式は不可能である。

以上より、求める組は $(n, k) = (6, 3)$ だけである。

東京大学 1981年度理系数学 第1問

問題

方針

解答

東京大学 1981年度
理系数学第1問