MathLabs

第2题

一个班的学生组成若干组,每组恰有三名成员,且任意两个不同的组至多有一名共同成员。证明当班级人数为 46 时,存在一个含 10 名学生的集合,其中没有一个组被真包含。
第 4/5 步:扩大集合
S′=S∪{u},∣S′∣=s+1S'=S\cup\{u\},\quad |S'|=s+1
详细分析

由于 u 不与 S 中两名学生同属任何组,加入 u 后不可能产生被 S′ 真包含的组:任何包含 u 且包含于 S′ 的组都需要这两名 S 中学生。原先包含于 S′ 的组在 S 中也不存在。因此 S′ 仍满足条件且比 S 大,与极大性矛盾。