MathLabs

第2题

一个班的学生组成若干组,每组恰有三名成员,且任意两个不同的组至多有一名共同成员。证明当班级人数为 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 中两名学生组成。由交集条件,S 中每一对学生至多属于一个组。因此这样对应的外部学生至多为二项式(s,2)≤36 名。