九州大学 2021年度理系数学前期第5問解答・解説

問題

以下の問いに答えよ。

(1) 自然数 $n$ ， $k$ が $2 ≦ k ≦ n - 2$ をみたすとき， $_{n} C_{k} > n$ であることを示せ。

(2) $p$ を素数とする。 $k ≦ n$ をみたす自然数の組 $(n, k)$ で $_{n} C_{k} = p$ となるものをすべて求めよ。

出典：九州大学 2021年度前期日程第2次学力試験理系前期第5問

方針

解法1（二項係数の積表示と素数の整除性を用いる）

(1)は $_{n} C_{k}$ が $k = 2$ から $k = n - 2$ の範囲では少なくとも $_{n} C_{2}$ 以上であることを示し、 $n ≧ 4$ から $\frac{n ( n - 1 )}{2} > n$ を使う。(2)では端の $k = 1, n - 1, n$ を先に処理する。中央範囲では (1) により $p > n$ となるが、恒等式 $k_{n} C_{k} = n_{n - 1} C_{k - 1}$ を使うと、素数 $p$ が $_{n - 1} C_{k - 1}$ を割る必要があり、値の大きさと矛盾する。

解法2（二項係数の単峰性と階乗の素因数を用いる）

二項係数列の比から，端から2番目より内側では $_{n} C_{k} \geq_{n} C_{2}$ であることを示す。(1)を得た後， $_{n} C_{k} = p$ が素数なら内部の場合には $p > n$ となる一方，階乗等式から $p ∣ n!$ となる矛盾を用いる。

解答

解法1（二項係数の積表示と素数の整除性を用いる）

(1)

$2 ≦ k ≦ n - 2$ であるから、特に $n ≧ 4$ である。

まず組合せ数の隣り合う比を考えると $\frac{_{n} C _{k + 1}}{_{n} C _{k}} = \frac{n - k}{k + 1}$ である。したがって $_{n} C_{k}$ は $k$ が端から中央へ近づくまでは増加し、その後は対称性 $_{n} C_{k} =_{n} C_{n - k}$ により同じ値を戻る。よって $2 ≦ k ≦ n - 2$ の範囲での最小値は端の $_{n} C_{2} =_{n} C_{n - 2}$ である。

したがって $_{n} C_{k} ≧_{n} C_{2} = \frac{n ( n - 1 )}{2}$ である。 $n ≧ 4$ なので $\frac{n ( n - 1 )}{2} > n$ であり、結局 $_{n} C_{k} > n$ が成り立つ。

(2)

まず端の場合を調べる。 $k = 1$ のとき $_{n} C_{1} = n$ であるから、 $_{n} C_{1} = p$ となるのは $n = p$ のときである。したがって $(n, k) = (p, 1)$ は解である。 $k = n - 1$ のときも $_{n} C_{n - 1} = n$ であるから $(n, k) = (p, p - 1)$ は解である。 $k = n$ のときは $_{n} C_{n} = 1$ なので、素数 $p$ にはならない。

残りとして $2 ≦ k ≦ n - 2$ を考える。このとき (1) より、もし $_{n} C_{k} = p$ なら $p > n$ である。

一方、組合せ数には $k_{n} C_{k} = n_{n - 1} C_{k - 1}$ という恒等式がある。ここに $_{n} C_{k} = p$ を代入すると $k p = n_{n - 1} C_{k - 1}$ である。 $p > n$ なので $p$ は $n$ を割らない。したがって素数 $p$ は $_{n - 1} C_{k - 1}$ を割らなければならない。

しかし $_{n - 1} C_{k - 1} = \frac{k}{n}_{n} C_{k} = \frac{k p}{n}$ であり、 $k < n$ だから $0 <_{n - 1} C_{k - 1} < p$ である。正の整数で $p$ より小さい数が $p$ で割り切れることはない。これは矛盾である。

したがって中央範囲には解はない。求める組は $(n, k) = (p, 1), (p, p - 1)$ である。ただし $p = 2$ のときはこの2つは同じ組 $(2, 1)$ である。

解法2（二項係数の単峰性と階乗の素因数を用いる）

(1)

二項係数は

\frac{_{n} C _{k + 1}}{_{n} C _{k}} = \frac{n - k}{k + 1}

より $k < n /2$ で増加し，対称性

_{n} C_{k} =_{n} C_{n - k}

をもつ。したがって $2 \leq k \leq n - 2$ では

_{n} C_{k} \geq_{n} C_{2} = \frac{n ( n - 1 )}{2} .

この範囲が存在するとき $n \geq 4$ だから

\frac{n ( n - 1 )}{2} > n .

よって

_{n} C_{k} > n

である。

(2)

$_{n} C_{k} = p$ とする。

$k = 0, n$ では値が1なので不適である。 $k = 1$ では $_{n} C_{1} = n = p$ ， $k = n - 1$ でも $_{n} C_{n - 1} = n = p$ だから

(n, k) = (p, 1), (p, p - 1)

を得る。

残る $2 \leq k \leq n - 2$ では(1)より $p > n$ である。一方

p =_{n} C_{k} = \frac{n !}{k ! ( n - k )!}

なので

n! = p k! (n - k)!,

すなわち $p ∣ n!$ である。しかし $p > n$ なら $1, 2, \dots, n$ のどの因数も素数 $p$ で割れず， $p ∤ n!$ となって矛盾する。

以上より，求める組は

(n, k) = (p, 1), (p, p - 1)

だけである。

九州大学 2021年度理系数学 前期 第5問

問題

方針

解法1（二項係数の積表示と素数の整除性を用いる）

解法2（二項係数の単峰性と階乗の素因数を用いる）

解答

解法1（二項係数の積表示と素数の整除性を用いる）

(1)

(2)

解法2（二項係数の単峰性と階乗の素因数を用いる）

(1)

(2)

九州大学 2021年度
理系数学前期第5問