集合A的特定交集条件下最大子集数量求解问询
集合A的特定交集条件下最大子集数量求解问询
大家好,我遇到了一个组合数学问题,想请教各位帮忙梳理思路:
问题详情
给定集合 ( A = {1, 2, \dots, 2021} ),要从A的所有子集中选出一部分子集,要求任意两个不同子集的交集恰好包含2019个元素,请问这样的子集最多能选出多少个?
我的初步想法
我已经知道答案应该是2021,但还没法严谨证明这就是最大值。目前我想到的一个满足条件的选法是:取所有大小为2020的A的子集——也就是每个子集刚好漏掉A里的一个元素。这样任意两个不同的这类子集,它们的交集就是A去掉那两个被各自漏掉的元素,也就是2021-2=2019个元素,完全符合题目要求。
不过我现在卡壳的点是:怎么证明不存在数量超过2021的子集族满足这个条件呢?有没有什么系统性的方法(比如用线性代数里的向量表示子集,或者组合计数的不等式)来推导这个上限?
备注:内容来源于stack exchange,提问作者user1353144




