トップ› 東京大学› 1981年› 理系第1問

東京大学 1981年理系第1問解説

方針・初手

前半は、要素数 $n$ の集合から $2k$ 個の要素を選び、それを2個ずつの $k$ 組に分ける方法の総数を求める場合の数の問題である。組同士に区別がないことに注意して立式する。後半は、求めた式を用いて $f(n, k) = f(n, 1)$ という方程式を立てる。階乗や順列の式を整理し、「連続する整数の積」の形に持ち込んで $k$ の値で場合分けを行い、不等式評価によって解を絞り込む。

解法1

まず、$2k$ 個の要素を $n$ 個の要素から選ぶ必要があるため、$n \geqq 2k$ である。もし $n < 2k$ であれば条件を満たす選び方は存在せず $f(n, k) = 0$ となる。このとき $f(n, 1) = {}_n\text{C}_2 > 0$ であるため、$f(n, k) = f(n, 1)$ を満たすことはない。したがって、以降は $n \geqq 2k$ を前提として考える。

$n$ 個の要素から、互いに交わらない2要素の部分集合を $k$ 個選ぶ方法は、以下の手順で考えられる。まず $n$ 個の要素から $2k$ 個の要素を選ぶ。その選び方は ${}_n\text{C}_{2k}$ 通りである。次に、選んだ $2k$ 個の要素を2個ずつの $k$ 組に分ける。その方法は、組の順番を区別しないため、

$$ \frac{{}_{2k}\text{C}_2 \times {}_{2k-2}\text{C}_2 \times \cdots \times {}_2\text{C}_2}{k!} = \frac{(2k)!}{2^k k!} $$

通りである。したがって、求める総数 $f(n, k)$ は、これらを掛け合わせて

$$ f(n, k) = {}_n\text{C}_{2k} \times \frac{(2k)!}{2^k k!} = \frac{n!}{(2k)!(n-2k)!} \times \frac{(2k)!}{2^k k!} = \frac{n!}{2^k k! (n-2k)!} $$

通りとなる。

次に、$f(n, k) = f(n, 1)$ を満たす $n$ と $k$ ($k \geqq 2$) を求める。上で求めた式より、$f(n, 1)$ は以下のように表せる。

$$ f(n, 1) = \frac{n!}{2^1 \cdot 1! \cdot (n-2)!} = \frac{n(n-1)}{2} $$

方程式 $f(n, k) = f(n, 1)$ に代入して整理する。

$$ \frac{n!}{2^k k! (n-2k)!} = \frac{n!}{2 (n-2)!} $$

$n \geqq 2k \geqq 4$ より $n! \neq 0$ であるから、両辺を $n!$ で割り、逆数をとって整理すると

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

$$ (n-2)(n-3)\cdots(n-2k+1) = 2^{k-1} k! $$

となる。左辺は $2k-2$ 個の連続する自然数の積である。ここで、$k$ の値について場合分けをして調べる。

(i)

$k=2$ のとき方程式は $(n-2)(n-3) = 2^1 \cdot 2! = 4$ となる。展開して整理すると $n^2 - 5n + 2 = 0$ となるが、これを満たす整数 $n$ は存在しない。

(ii)

$k=3$ のとき方程式は $(n-2)(n-3)(n-4)(n-5) = 2^2 \cdot 3! = 24$ となる。 $n \geqq 2k = 6$ より $n-2 \geqq 4$ であり、左辺は連続する4つの自然数の積である。 $4 \times 3 \times 2 \times 1 = 24$ であるから、$n-2 = 4$ すなわち $n = 6$ となる。これは $n \geqq 6$ を満たしている。

(iii)

$k \geqq 4$ のとき $n \geqq 2k$ であるから、左辺が最小になるのは $n = 2k$ のときである。その最小値は

$$ (2k-2)(2k-3)\cdots 2 \cdot 1 = (2k-2)! $$

となる。ここで、すべての $k \geqq 4$ に対して $(2k-2)! > 2^{k-1} k!$ （右辺）が成り立つことを数学的帰納法で示す。

$k=4$ のとき、左辺は $6! = 720$、右辺は $2^3 \cdot 4! = 192$ となり、不等式は成立する。ある $k$ ($k \geqq 4$) で成立すると仮定する。$k+1$ のときの左辺は

$$ (2(k+1)-2)! = (2k)! = (2k)(2k-1) \cdot (2k-2)! $$

帰納法の仮定を用いると

$$ (2k)(2k-1) \cdot (2k-2)! > (2k)(2k-1) \cdot 2^{k-1} k! $$

ここで、$k \geqq 4$ のとき $(2k)(2k-1) - 2(k+1) = 4k^2 - 4k - 2 > 0$ より $(2k)(2k-1) > 2(k+1)$ であるから

$$ (2k)(2k-1) \cdot 2^{k-1} k! > 2(k+1) \cdot 2^{k-1} k! = 2^k (k+1)! $$

となり、$k+1$ のときも不等式が成立する。したがって、$k \geqq 4$ において常に左辺 $>$ 右辺となり、等式を満たす自然数 $n$ は存在しない。

以上（i）～（iii）より、条件を満たす $n, k$ の組は $n=6, k=3$ のみである。

解説

前半は、組分け問題の基本である「要素数が同じ組を複数作るときは、組の区別をなくすために階乗で割る」という操作が正確にできるかを問うている。後半は、階乗が含まれる等式を満たす自然数を探す問題である。変数が $n, k$ と2つあるため、扱いやすい $k$ に着目して具体的な値を代入し、実験を通して当たりをつけることが重要である。$k$ が大きくなると左辺の連続整数の積が急激に大きくなる性質を利用して、不等式評価で解が存在しないことを証明する流れは、整数問題における典型的な処理である。