作业帮 > 数学 > 作业

设M为n元集,若M有k个不同的子集A1,A2,…,Ak,满足:对于每个i、j∈{1,2,…,k},有Ai∩Aj≠Ф,求正

来源:学生作业帮 编辑:大师作文网作业帮 分类:数学作业 时间:2024/11/15 17:07:52
设M为n元集,若M有k个不同的子集A1,A2,…,Ak,满足:对于每个i、j∈{1,2,…,k},有Ai∩Aj≠Ф,求正整数k的最大
设M为n元集,若M有k个不同的子集A1,A2,…,Ak,满足:对于每个i、j∈{1,2,…,k},有Ai∩Aj≠Ф,求正
楼上说的 以一个元素为公共元素, 可以得 2^(n-1)个两两有公共元素的子集.这是最大可能性.
证明如下:
设G = {A1,...,Ak } 满足条件Ai∩Aj≠Ф. 则任给Ai, 存在Bi = M - Ai 为 Ai 的补集, 显然 Bi 不∈G.
于是 至少有k个M的子集不在G中. M 共有 2^n 个子集. 所以至少有 2^n / 2 = 2^(n-1)个子集不在G中, 于是 |G|