MathLabs

第2問

あるクラスの生徒を、それぞれちょうど 3 人からなるグループに分け、異なる2グループが共有する生徒は高々1人であるとする。クラスの人数が 46 のとき、どのグループも真に含まない 10 人の集合が存在することを証明せよ。
ステップ 2/5: 反対を仮定する
s≤9⟹(s2)≤(92)=36s\le9\Longrightarrow\binom{s}{2}\le\binom{9}{2}=36
詳しい解説

s≤9 と仮定する。S の外の任意の生徒 v について、極大性から v を加えるとあるグループ全体が生じるので、v と S の2人からなるグループがある。交差条件より S の各ペアは高々1グループに属する。従ってこのように対応できる外部生徒は高々二項係数(s,2)≤36人である。