第2問

あるクラスの生徒を、それぞれちょうど 3 人からなるグループに分け、異なる2グループが共有する生徒は高々1人であるとする。クラスの人数が 46 のとき、どのグループも真に含まない 10 人の集合が存在することを証明せよ。

ステップ 1/5: 極大集合を選ぶ

s=\max\{|S|:S\subseteq C,\ S\text{ contains no group properly}\}

詳しい解説

46人の集合を C とし、どのグループも真に含まない最大集合 S を取る。s=|S| が10以上であることを示せばよい。そうすれば S の10要素部分集合も同じ性質を持つ。