百度作业网构造45个｛1,2,3,4,……30｝的四元子集,使得任意两个集合交集最多1个元素?
来源：学生作业帮 编辑：百度作业网作业帮 分类：数学作业 时间：2024/07/31 12:25:01
构造45个｛1,2,3,4,……30｝的四元子集,使得任意两个集合交集最多1个元素?
RT
RT
n元集合子满足任意两个集合交集有且只有1个元素的条件的子集数最大为n,这个数目不可能再大了.
证明：
考虑每个子集所对应的n维01向量,例如n=30时集合{1,2,3,4}就对应向量{1,1,1,1,0,0,0……,0(共26个0)},而子集{4,5,6,7}则可以表示成{0,0,0,1,1,1,1,0,0……}.可以看出,两个子集的交集的元素个数就等于它们的向量的点积.
下面我们证明,满足要求的一组子集其对应的向量一定是线性无关的,从而直接得到向量个数不超过n的结论.
记m个向量分别为v_1, v_2, ..., v_m,令s=Σa_i v_i,考虑点积=Σ Σ a_i · a_j · .注意对每一对不同的i和j都有=1,而就等于子集A_i的元素个数|A_i|.于是,就等于(a_1 + a_2 + ... + a_m)^2 + Σ(a_i)^2·(|A_i|-1).当s=Σa_i v_i=0时,也应该为0；而上面表达式中的每一项都是非负整数,要让为0只可能是所有a_i都取0,这就说明这m个向量是线性无关的.
所以30元集合满足条件的最多有30个.
而30元集合满足任意两个集合没有交集最多为[30/4]=7
所以最多最多有30+7=37
证明：
考虑每个子集所对应的n维01向量,例如n=30时集合{1,2,3,4}就对应向量{1,1,1,1,0,0,0……,0(共26个0)},而子集{4,5,6,7}则可以表示成{0,0,0,1,1,1,1,0,0……}.可以看出,两个子集的交集的元素个数就等于它们的向量的点积.
下面我们证明,满足要求的一组子集其对应的向量一定是线性无关的,从而直接得到向量个数不超过n的结论.
记m个向量分别为v_1, v_2, ..., v_m,令s=Σa_i v_i,考虑点积=Σ Σ a_i · a_j · .注意对每一对不同的i和j都有=1,而就等于子集A_i的元素个数|A_i|.于是,就等于(a_1 + a_2 + ... + a_m)^2 + Σ(a_i)^2·(|A_i|-1).当s=Σa_i v_i=0时,也应该为0；而上面表达式中的每一项都是非负整数,要让为0只可能是所有a_i都取0,这就说明这m个向量是线性无关的.
所以30元集合满足条件的最多有30个.
而30元集合满足任意两个集合没有交集最多为[30/4]=7
所以最多最多有30+7=37
集合S={1，2，3，…，10}的四元子集T={a1，a2，a3，a4}中，任意两个元素的差的绝对值都不为1，这样的四元
前12个正整数组成一个集合{1，2，3，…，12}，此集合的符合如下条件的子集的数目为m：子集均含有4个元素，且这4个元
设S为集合{1,2,3,4,···,50}的一个子集,解S中任意俩个元素之和不能被7整除,则S中元素最多有多少个?
集合S=｛1,2,3,…,20｝的4元子集T=｛a1,a2,a3,a4｝中,任意两个元素的差的绝对值都不为1,这样的4元
集合A有m个元素,那么A的1元子集应该是m个,2元子集有多少个?3元子集有多少个?这种规律是什么呢?
证明对任意n,任意2n-1元正整数集合,一定存在n个元素,使得他们的和是n的倍数
一道集合题给定集合I={1,2,3,.,n}的k个子集：A1,A2,.Ak,满足任何两个子集的交集非空,并且再添加I的任
一个集合有5个元素,其中含有1个,2个,3个,4个元素的子集共有多少个?
一个集合含有5个元素,其中含有了1个,2个,3个,4个元素的了子集有多少个.
已知集合M是集合S={1,2,3,4,······,2009}的含有m个元素的子集,且对集合m的任意三个元素x,y,z均
已知集合{0,1,2,……,9},求这个集合的子集中含5个元素且其中2个是偶数的子集个数.
已知集合A={1,2,3,4,……,n},则A的所有含有3个元素的子集的元素和为