易混 2024 年中科大少年班营二 第 2 题 · P009933
把对象与局部小集合建立关联后，先分清是在做互不重叠的容量估计，还是允许重叠的覆盖估计。前者给对象数上界，后者给所需对象数下界，方向取决于每个局部对象被计几次。
前题取答题集合的补集，反设交集太小使其三元子集不得重复，从有限容量推出矛盾；后题最大相离集合迫使小半径球覆盖全空间，球可重叠，只能用覆盖次数至少一次的方向。
培玉 · 一试
2015 年安徽预赛 · 第 12 题
F3解答题组合计数综合
已知 31 位学生参加了某次考试，考试共有 10 道题，每位学生解出了至少 6 道题.求证：存在两位学生，他们解出的题目中至少有 5 道相同.
作答
这是解答题，请在纸上写出完整过程。写完后对照解答给自己评分。
解析
思路
直接数五道共同题的容量不够，先把每人的六题选择取补集，问题就化为十题中四元集的三子集容量。
解答
从每位学生解出的题中任取六题，记这六题的补集为 ，每个 有四道题。若不存在所求两学生，则任两所选六题的交集至多四题。由全集十题，有
故任两四元补集的交集至多二。这样它们包含的三元子集不可能重合；每个四元集含四个三元子集，三十一个学生便需要 个不同三元子集。但十题总共只有 个，矛盾。因此 。
复核
从至少六题中任选六题不会造成误证：所选六题若有五题相同，两人各自的解题全集当然也至少有五题相同。用四题补集计三子集后才超过容量；只数所选六题中的五子集不会给足够的矛盾。
方法总结
交集保证题可先取补集把大集合变小，再找每个小集合占用的局部子集容量。
为什么评为 F3（会透露解法方向）
需先取补集换算交集，找到三元子集的紧容量；直接对原六题集合数五子集并不能推出矛盾。
联系 · 1 条
已记下，谢谢！