Evolton

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

S={1,2,⋯ ,n},ただしn≧2,とする.
2つの要素から成るSの部分集合をk個とり出し,
そのうちのどの2つも交わりが空集合であるようにする方法は何通りあるか.

つぎに,この数(つまり何通りあるかを表す数)をf(n,k)で表したとき,
f(n,k)=f(n,1)をみたすようなnとk(ただし,k≧2)をすべて求めよ.

難易度6/ 10計算量5/ 10目安20分

場合の数、整数 数え上げ、範囲評価、場合分け

方針

まず使う 2k 個の元を選び、それらを順序のない k 組へ分ける。
f(n,1) との等式を階乗積へ直し、k=2,3 と k≧4 を分けて調べる。

解答

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

互いに交わらない2要素部分集合を k 個選ぶには、まず S から使う 2k 個の元を選ぶ。選んだ 2k 個を2個ずつの組に分ける方法は (2k)!2kk! 通りである。したがってf(n,k)=nC2k(2k)!2kk!=n!(n−2k)!2kk!である。

また f(n,1)=nC2=n(n−1)2 である。k≧2 で f(n,k)=f(n,1) とすると、2k≦n でなければならず、両辺を整理して (n−2)!(n−2k)!=2k−1k! を得る。 k=2 のときは (n−2)(n−3)=4 である。しかし n≧4 なので左辺は 2⋅1=2, 3⋅2=6, 4⋅3=12, … と増加し、4にはならない。したがって解はない。 k=3 のときは (n−2)(n−3)(n−4)(n−5)=24 である。n≧6 であり、n=6 のとき左辺は 4⋅3⋅2⋅1=24 となる。n≧7 では左辺はこれより大きいので、解は n=6 だけである。

最後に k≧4 を考える。n≧2k だから(n−2)!(n−2k)!≧(2k−2)!である。ここでRk=(2k−2)!2k−1k!とおくと、R4=15/4>1 であり、Rk+1Rk=(2k)(2k−1)2(k+1)=k(2k−1)k+1>1(k≧4)である。したがって (2k−2)!>2k−1k! がすべての k≧4 で成り立ち、等式は不可能である。

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

別解

解法2(組を順に選ぶ)

方針

1組目、2組目と順に2要素集合を選び、最後に組を選んだ順序 k! を除く。
得られる積の式から f(n,k)=f(n,1) を調べる。

解答

k 個の組に仮の順序を付けて選ぶとnC2 n−2C2⋯n−2k+2C2通りである。同じ k 組が k! 回ずつ現れるからf(n,k)=nC2 n−2C2⋯n−2k+2C2k!=n!(n−2k)!2kk!.ただし 2k>n では f(n,k)=0 である。

f(n,k)=f(n,1) は(n−2)(n−3)⋯(n−2k+1)=2k−1k!と同値である。k=2 では (n−2)(n−3)=4 に整数解はない。
k=3 では(n−2)(n−3)(n−4)(n−5)=24となり、n=6 だけが解である。

k≧4 では左辺は n=2k のときでも (2k−2)! 以上である。(2k−2)!2k−1k!は k=4 で 15/4>1、さらに k とともに増加するので等式は不可能である。
よって(n,k)=(6,3)だけである。

総評

難度は10段階中6、計算量は10段階中5程度。想定時間は18分から25分程度。互いに交わらない2要素集合を、2k 個の元の選択と組分けに分けて数えることが出発点である。採点では、2kk! で割る理由、2k≦n の必要条件、k=2,3 の直接確認、k≧4 を評価で除くことが重要である。最後の評価を省くと、(6,3) 以外がないことの説明が不足する。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

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

出典: 東京大学 1981年度 前期 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。