Evolton

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

以下の問いに答えよ。

(1) 自然数n，kが2≦k≦n−2をみたすとき，
nCk>nであることを示せ。

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

難易度5/ 10計算量4/ 10目安18分

場合の数、整数　数え上げ、不等式評価、素因数分解

方針

(1) は nCk が k=2 から k=n−2 の範囲では少なくとも nC2 以上であることを示し、n≧4 から n(n−1)2>n を使う。(2)では端の k=1,n−1,n を先に処理する。中央範囲では (1) により p>n となるが、恒等式 knCk=nn−1Ck−1 を使うと、素数 p が n−1Ck−1 を割る必要があり、値の大きさと矛盾する。

解答

(1) 2≦k≦n−2 であるから、特に n≧4 である。

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

したがって nCk≧nC2=n(n−1)2 である。n≧4 なので n(n−1)2>n であり、結局 nCk>n が成り立つ。

(2)
まず端の場合を調べる。 k=1 のとき nC1=n であるから、nC1=p となるのは n=p のときである。したがって (n,k)=(p,1) は解である。 k=n−1 のときも nCn−1=n であるから (n,k)=(p,p−1) は解である。k=n のときは nCn=1 なので、素数 p にはならない。

残りとして 2≦k≦n−2 を考える。このとき (1) より、もし nCk=p なら p>n である。

一方、組合せ数には knCk=nn−1Ck−1 という恒等式がある。ここに nCk=p を代入すると kp=nn−1Ck−1 である。p>n なので p は n を割らない。したがって素数 p は n−1Ck−1 を割らなければならない。

しかし n−1Ck−1=knnCk=kpn であり、k<n だから 0<n−1Ck−1<p である。正の整数で p より小さい数が p で割り切れることはない。これは矛盾である。

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

別解

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

方針

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

解答

(1)
二項係数はnCk+1nCk=n−kk+1より k<n/2 で増加し，対称性nCk=nCn−kをもつ。したがって 2≤k≤n−2 ではnCk≥nC2=n(n−1)2.この範囲が存在するとき n≥4 だからn(n−1)2>n.よってnCk>nである。

(2)
nCk=p とする。

k=0,n では値が1なので不適である。k=1 では nC1=n=p，k=n−1 でも nCn−1=n=p だから(n,k)=(p,1),(p,p−1)を得る。

残る 2≤k≤n−2 では(1)より p>n である。一方p=nCk=n!k!(n−k)!なのでn!=p k!(n−k)!,すなわち p∣n! である。しかし p>n なら 1,2,…,n のどの因数も素数 p で割れず，p∤n! となって矛盾する。

以上より，求める組は(n,k)=(p,1),(p,p−1)だけである。

総評

組合せ数の大小と素数性を組み合わせる整数問題。目安時間は18分。(1)は中央に向かって組合せ数が大きくなることを比で説明すると、端 k=2,n−2 が最小だと自然に分かる。(2)は k=1,n−1,n の端を先に処理し、中央部分では単に「分子に p がない」と書くより、恒等式 knCk=nn−1Ck−1 で矛盾を作る方が確実である。p=2 で2つの表示が同じ組になる点も最後に触れておくとよい。

冊子PDFで見る九大の場合の数の問題で問題集を作る

出典: 九州大学 2021年度 一般選抜（前期日程）数学（大学公式の問題PDF）。問題文はHTML表示のために再入力・数式組版しています。