Appearance
题干
一个小区有9户居民，每户居民都派出一个代表加入3个不同的兴趣社团，任意两户居民 的社团列表中，都至少有一个社团是两个人共同参加的。请问：拥有人数最多的那个社团，最少有多少人参加?
解析
题目重述：
有 9 户居民，每户恰好加入 3 个 不同的兴趣社团。
任意两户的社团列表中，至少有一个社团是两人共同参加的。
问：在所有社团中，参加人数最多的那个社团，最少有多少人？
1. 问题建模（数学化）
- 将每个社团看作一个 元素（点）。
- 将每户居民参加的 3 个社团看作一个 三元子集（3-元组）。
- 于是问题转化为：
设有 9 个三元子集 $S_1, S_2, \dots, S_9$，满足任意两个子集相交非空（即 $|S_i \cap S_j| \ge 1$）。
定义元素 $x$的 度数$d(x)$ 为包含它的子集个数。
求 $\min \max_x d(x)$。
2. 下界证明：人数最多的社团必然 ≥ 5
我们采用 反证法，假设 所有社团的参加人数都不超过 4，即：
$$ \forall x,\quad d(x) \le 4 $$
然后推导矛盾。
2.1 选取一个初始三元组
任取一户居民，其社团集合记为：
$$ A = \lbrace 1, 2, 3\rbrace $$
设社团 $1, 2, 3$的度数分别为$d_1, d_2, d_3$。
除了这户居民外，还有 8 户居民。由于任意一户都与 $A$这户有共同社团，所以其余 8 个三元组中的每一个，都必须与$A$ 至少相交 1 个元素。
因此，$1, 2, 3$这三个社团的出现次数总和（除去$A$ 自身贡献的 3 次）至少为 8，所以：
$$ d_1 + d_2 + d_3 \ge 3 + 8 = 11 $$
又因为假设每个社团最多出现 4 次，所以：
$$ d_1 + d_2 + d_3 \le 4 + 4 + 4 = 12 $$
于是：
$$ d_1 + d_2 + d_3 \in \lbrace 11, 12\rbrace $$
2.2 必然存在一个恰好出现 4 次的社团
- 若和为 11，则三个度数只能是 $4, 4, 3$（顺序不限），存在度数为 4 的社团。
- 若和为 12，则三个度数只能是 $4, 4, 4$，存在度数为 4 的社团。
所以，无论如何，在 $A=\lbrace 1,2,3\rbrace $ 中，至少有一个社团出现了恰好 4 次。
不失一般性，设：
$$ d(1) = 4 $$
2.3 聚焦于社团 1，构造关键集合
设包含社团 1 的 4 户居民对应的三元组为：
$$ A_1, A_2, A_3, A_4 $$
它们都包含元素 $1$。把每个 $A_i$ 中的“除 1 外的两个元素”提取出来，记为二元组：
$$ P_i = A_i \setminus \lbrace 1\rbrace ,\quad i=1,2,3,4 $$
令所有这些二元组中出现的所有元素（除了 1 以外）组成集合 $U$：
$$ U = \bigcup_{i=1}^4 P_i $$
设 $|U| = m$。因为每个 $P_i$ 有 2 个元素，共有 4 个二元组，所以显然：
$$ m \le 8 $$
另外，由于总共有 9 户，不包含社团 1 的居民共有：
$$ 9 - 4 = 5 $$
户。设它们对应的三元组为：
$$ B_1, B_2, B_3, B_4, B_5 $$
2.4 核心观察：所有 $B_j$的元素都必须在$U$ 中
因为每个 $B_j$不包含$1$，但 $B_j$必须与每一个$A_i$ 相交。
而 $A_i$只包含元素$1$和$U$中的元素，既然$B_j$不含$1$，那么 $B_j$要想与所有$A_i$相交，它的元素 必须全部来自$U$。
否则，若 $B_j$含有某个不在$U$中的元素$y$，则 $y$不在任何$A_i$中，且$B_j$不含$1$，那么 $B_j$就与所有$A_i$ 都不相交，矛盾。
因此：
$$ B_j \subseteq U,\quad |B_j| = 3 $$
并且这 5 个三元组 $B_1, \dots, B_5$ 两两相交（因为它们对应不同的居民，任意两户必须有共同社团）。
2.5 计算并集大小 $m$ 的下界
对每个元素 $x \in U$，定义：
- $r_x$：元素 $x$在 4 个二元组$P_1, P_2, P_3, P_4$中出现的次数（即$x$ 与社团 1 共同出现的次数）；
- $s_x$：元素 $x$在 5 个三元组$B_1, \dots, B_5$ 中出现的次数。
那么元素 $x$ 的总度数为：
$$ d(x) = r_x + s_x $$
根据反证假设，总度数不超过 4，所以：
$$ s_x \le 4 - r_x $$
对所有的 $x \in U$ 求和：
$$ \sum_{x \in U} s_x \le \sum_{x \in U} (4 - r_x) = 4|U| - \sum_{x \in U} r_x $$
左边：$\sum s_x$是$B_1, \dots, B_5$的总元素个数，即$5 \times 3 = 15$。
右边：$\sum r_x$是 4 个二元组$P_i$的总元素个数，即$4 \times 2 = 8$。
代入得：
$$ 15 \le 4m - 8 \quad \Longrightarrow \quad 4m \ge 23 \quad \Longrightarrow \quad m \ge 6 $$
又因为 $m \le 8$，所以：
$$ m \in \lbrace 6, 7, 8\rbrace $$
2.6 根据 $m$ 的值分类讨论，逐一矛盾
情况 1：$m = 6$
此时 $|U| = 6$，而 4 个二元组 $P_i$总共贡献$8$个出现次数，所以重复的额外次数为$8 - 6 = 2$。
可能的重复模式只有两种：
模式 A：某个元素出现 3 次
设该元素为 $a$。那么 4 个二元组形如：
$$ \lbrace a, x\rbrace , \lbrace a, y\rbrace , \lbrace a, z\rbrace , \lbrace b, c\rbrace $$
其中 $x, y, z, b, c$互不相同，且都不等于$a$。
若某个 $B_j$不包含$a$，为了与前三个二元组相交，它必须包含 $x, y, z$（3 个元素）；但还要与 $\lbrace b, c\rbrace $相交，还至少需要$b$或$c$，总共至少 4 个元素，矛盾于 $|B_j|=3$。
所以所有 $B_j$都必须包含$a$，于是 $s_a = 5$。
此时：
$$ d(a) = r_a + s_a = 3 + 5 = 8 > 4 $$
矛盾。
模式 B：两个元素各出现 2 次
设这两个元素为 $a, b$。那么 4 个二元组形如：
$$ \lbrace a, x\rbrace , \lbrace a, y\rbrace , \lbrace b, u\rbrace , \lbrace b, v\rbrace $$
其中 $x, y, u, v$互不相同，且不等于$a, b$。
若某个 $B_j$不包含$a$，为了与前两个二元组相交，它必须包含 $x, y$；为了与后两个二元组相交，它必须包含 $u, v$，总共至少 4 个元素，矛盾。
所以所有 $B_j$都包含$a$。同理，所有 $B_j$也都包含$b$。
于是 $s_a = s_b = 5$，则：
$$ d(a) = r_a + s_a = 2 + 5 = 7 > 4 $$
矛盾。
因此 $m=6$ 不可能。
情况 2：$m = 7$
此时 4 个二元组共 8 次出现，额外重复次数为 $8 - 7 = 1$。
所以恰好有一个元素 $a$ 出现 2 次，其余 6 个元素各出现 1 次。
于是 4 个二元组形如：
$$ \lbrace a, b_1\rbrace , \lbrace a, b_2\rbrace , \lbrace c_1, c_2\rbrace , \lbrace d_1, d_2\rbrace $$
其中 $b_1, b_2, c_1, c_2, d_1, d_2$互不相同，且都不等于$a$。
若某个 $B_j$不包含$a$，为了与前两个二元组相交，它必须同时包含 $b_1, b_2$；为了与第三个相交，必须包含 $c_1$或$c_2$；为了与第四个相交，必须包含 $d_1$或$d_2$。
这至少需要 $2 + 1 + 1 = 4$个元素，矛盾于$|B_j| = 3$。
因此所有 $B_j$都必须包含$a$，即 $s_a = 5$。
于是：
$$ d(a) = r_a + s_a = 2 + 5 = 7 > 4 $$
矛盾。
情况 3：$m = 8$
此时 4 个二元组共 8 次出现，没有重复元素。
因此 4 个二元组两两不相交，形如：
$$ \lbrace a_1, a_2\rbrace , \lbrace b_1, b_2\rbrace , \lbrace c_1, c_2\rbrace , \lbrace d_1, d_2\rbrace $$
每个 $B_j$ 大小为 3，它最多只能从这 4 个互不相交的二元组中“击中”其中 3 个（因为每个二元组至少需要一个不同的元素）。
所以 $B_j$不可能同时与全部 4 个$A_i$ 相交，矛盾。
2.7 下界总结
所有可能情况 $m=6, 7, 8$ 都导出矛盾，因此反设不成立。
所以必然存在某个社团，其参加人数：
$$ \boxed{\ge 5} $$
3. 上界构造：达到 5 人的具体方案
我们需要构造一个实际例子，使得人数最多的社团恰好是 5 人。
利用 Fano 平面（7 个点，7 条线，每条线 3 个点，任意两条线恰好交于 1 点）：
取 7 个社团，编号为 $1, 2, \dots, 7$。
令前 7 户居民的社团列表为 Fano 平面的 7 条线：
$$ \begin{aligned} &123,\ 145,\ 167,\ 246,\ 257,\ 347,\ 356 \end{aligned} $$
这 7 个三元组两两相交于恰好 1 个社团。
剩下 2 户居民，让他们与第 1 户完全相同，即也参加：
$$ 123,\ 123 $$
于是全部 9 户为：
$$ 123,\ 145,\ 167,\ 246,\ 257,\ 347,\ 356,\ 123,\ 123 $$
统计各社团参加人数
- 社团 1：出现在 $123, 145, 167, 123, 123$ 中，共 5 次；
- 社团 2：出现在 $123, 246, 257, 123, 123$ 中，共 5 次；
- 社团 3：出现在 $123, 347, 356, 123, 123$ 中，共 5 次；
- 社团 4：出现在 $145, 246, 347$ 中，共 3 次；
- 社团 5：出现在 $145, 257, 356$ 中，共 3 次；
- 社团 6：出现在 $167, 246, 356$ 中，共 3 次；
- 社团 7：出现在 $167, 257, 347$ 中，共 3 次。
最大人数为：
$$ \max = 5 $$
并且任意两户都有共同社团（Fano 线两两相交；重复的 123 与任何线相交；重复的 123 之间相交于 3 个点）。
4. 最终结论
- 下界证明：人数最多的社团 不能少于 5。
- 上界构造：存在安排使得人数最多的社团 恰好为 5。
因此，题目所求的最小值为：
$$ \boxed{5} $$
本题的精髓在于巧妙地利用“度数”和“覆盖并集”进行反证，并结合 Fano 平面进行最优构造，是组合数学中极值集合论与有限几何的经典交汇。