百科问答小站 logo
百科问答小站 font logo



如何扩充相交族? 第1页

  

user avatar   jingfanc 网友的相关建议: 
      

(已经回高三了,但是依稀记得单老写过


user avatar    网友的相关建议: 
      

证:考察集合A的某一元素b与某一子集B,b或属于B,记为1,或不属于B,记为0.我们容易看出,在对集合A赋予顺序后,A的所有子集与n位二进制数建立双射.

事实1:定义某一二进制数B的对偶是这样的一个数B′,若将B中的所有1置为0,所有0置为1.易见B与B′不可共存于同一相交族F中.于是相交族F的基数最大为power(2,n-1).

事实2:易见这个基数最大的相交族F存在,且必含有集合A,其余集合之间若存在矛盾,考虑将出现矛盾的两个集合B,C任取其一换成其对偶即可消除矛盾.

故这样的最大相交族存在,因而总可以将其换成适当的形式,使其包含扩充前的相交族.




  

相关话题

  如何扩充相交族? 
  有哪些指标可以描述两个图(graph)的相似度? 
  不用计算机程序,如何求1,2,…,n中所有与n互素的数的平方和? 
  如何用组合数学证明 (n²)! 能被 (n!)^(n+1) 整除? 
  任给N个连续的整数,是否能从中找到一些数(至少一个),使得它们加起来是N(N+1)/2的倍数? 
  从正整数 1~N 中任意取两数 m、n,设 P 为 m/n 可约分的概率,问 N→∞ 时,P为多少? 
  有n级台阶,每次可以走1~(n-1)的任意阶数,那么一共有多少种走法? 
  从0,2 中选一个数字,从1,3,5中选两个数字,组成无重复数字的三位数,构成奇数的概率是多少? 
  如何证明树的树叶个数比度数不少于3的顶点数多? 
  n*n的棋盘填上1,2,...,n^2,使任意相邻(有公共边)格子里的数字之和不大于S,求S最小值? 

前一个讨论
科学家都是怎么记忆复杂的物理公式的?
下一个讨论
如何证明Banach空间的有限维子空间的性质?





© 2024-11-22 - tinynew.org. All Rights Reserved.
© 2024-11-22 - tinynew.org. 保留所有权利