You need to enable JavaScript to run this app.
最新活动
大模型
产品
解决方案
定价
生态与合作
支持与服务
开发者
了解我们

集合A的特定交集条件下最大子集数量求解问询

集合A的特定交集条件下最大子集数量求解问询

大家好,我遇到了一个组合数学问题,想请教各位帮忙梳理思路:

问题详情

给定集合 ( A = {1, 2, \dots, 2021} ),要从A的所有子集中选出一部分子集,要求任意两个不同子集的交集恰好包含2019个元素,请问这样的子集最多能选出多少个?

我的初步想法

我已经知道答案应该是2021,但还没法严谨证明这就是最大值。目前我想到的一个满足条件的选法是:取所有大小为2020的A的子集——也就是每个子集刚好漏掉A里的一个元素。这样任意两个不同的这类子集,它们的交集就是A去掉那两个被各自漏掉的元素,也就是2021-2=2019个元素,完全符合题目要求。

不过我现在卡壳的点是:怎么证明不存在数量超过2021的子集族满足这个条件呢?有没有什么系统性的方法(比如用线性代数里的向量表示子集,或者组合计数的不等式)来推导这个上限?

备注:内容来源于stack exchange,提问作者user1353144

火山引擎 最新活动