子集族

观察

以集合为元素的集合，叫子集族。 $M$ 的全部子集组成的族叫 $M$ 的 C 族， $∣ M ∣ = n$ 时它有 $2^{n}$ 个成员。竞赛里的子集族问题，常常是给族加一条规矩，问它最多能有多大。

先猜后证

${1, 2, 3, 4, 5}$ 的子集族 $F$ 中任意两个成员都有公共元素。 $F$ 最多有几个成员？

5

个

10

个

16

个

31

个

先选定答案，才能看到结论。

第 1 / 4 步

“构造 + 上界”是这类问题的标准两步：构造一个例子说明“能达到”，再用配对（或分抽屉）说明“不能更多”。配对其实就是抽屉原理： $8$ 个抽屉，挑了 $9$ 个子集，必有两个落在同一个抽屉里——互补，不相交。

换一条规矩： $F$ 中没有一个成员包含另一个（这样的族叫反链）。同一层的子集元素个数相同，自然互不包含；最宽的是中间一层，有 $C_{4}^{2} = 6$ 个。能不能跨层挑出更多？

第 1 / 4 步

这里的“链”扮演了上一节“互补对”的角色：把全体对象分成若干组，每组里至多选一个。组数就是上界。

n = 3

时自己试：最大的反链有几个成员？画出对称链，数一数有几条。

练习 1基础

${1, 2, \dots, 6}$ 的子集族中，任意两个成员都有公共元素。这个族最多有多少个成员？

练习 2基础

从 ${1, 2, 3, 4, 5}$ 的子集中挑出一族，使其中没有一个子集包含另一个。最多能挑几个？

练习 3提高

从 ${1, 2, 3, 4, 5}$ 的子集中挑出一族，使其中任意两个子集的并都不是 ${1, 2, 3, 4, 5}$ 。最多能挑几个？

练习 4挑战

从 ${1, 2, \dots, 10}$ 的子集中挑出一族，每个子集至多 $3$ 个元素，而且没有一个包含另一个。最多能挑几个？