求使这样的集合族存在的最大正整数n.已知一族集合A1,A2……An具有性质:1.每个Ai含有30个元素;2.对每一对i,j:1≤i<j≤n,Ai∩Aj都是单元集;3.A1∩A2∩……∩An=空集 求使这样的集合族存在的最
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/04 18:04:53
![求使这样的集合族存在的最大正整数n.已知一族集合A1,A2……An具有性质:1.每个Ai含有30个元素;2.对每一对i,j:1≤i<j≤n,Ai∩Aj都是单元集;3.A1∩A2∩……∩An=空集 求使这样的集合族存在的最](/uploads/image/z/3002096-56-6.jpg?t=%E6%B1%82%E4%BD%BF%E8%BF%99%E6%A0%B7%E7%9A%84%E9%9B%86%E5%90%88%E6%97%8F%E5%AD%98%E5%9C%A8%E7%9A%84%E6%9C%80%E5%A4%A7%E6%AD%A3%E6%95%B4%E6%95%B0n.%E5%B7%B2%E7%9F%A5%E4%B8%80%E6%97%8F%E9%9B%86%E5%90%88A1%2CA2%E2%80%A6%E2%80%A6An%E5%85%B7%E6%9C%89%E6%80%A7%E8%B4%A8%EF%BC%9A1.%E6%AF%8F%E4%B8%AAAi%E5%90%AB%E6%9C%8930%E4%B8%AA%E5%85%83%E7%B4%A0%EF%BC%9B2.%E5%AF%B9%E6%AF%8F%E4%B8%80%E5%AF%B9i%2Cj%3A1%E2%89%A4i%EF%BC%9Cj%E2%89%A4n%2CAi%E2%88%A9Aj%E9%83%BD%E6%98%AF%E5%8D%95%E5%85%83%E9%9B%86%EF%BC%9B3.A1%E2%88%A9A2%E2%88%A9%E2%80%A6%E2%80%A6%E2%88%A9An%3D%E7%A9%BA%E9%9B%86+%E6%B1%82%E4%BD%BF%E8%BF%99%E6%A0%B7%E7%9A%84%E9%9B%86%E5%90%88%E6%97%8F%E5%AD%98%E5%9C%A8%E7%9A%84%E6%9C%80)
求使这样的集合族存在的最大正整数n.已知一族集合A1,A2……An具有性质:1.每个Ai含有30个元素;2.对每一对i,j:1≤i<j≤n,Ai∩Aj都是单元集;3.A1∩A2∩……∩An=空集 求使这样的集合族存在的最
求使这样的集合族存在的最大正整数n.
已知一族集合A1,A2……An具有性质:1.每个Ai含有30个元素;2.对每一对i,j:1≤i<j≤n,Ai∩Aj都是单元集;3.A1∩A2∩……∩An=空集
求使这样的集合族存在的最大正整数n.
最好讲得浅显易懂一点,(答案是871,准确无误,
求使这样的集合族存在的最大正整数n.已知一族集合A1,A2……An具有性质:1.每个Ai含有30个元素;2.对每一对i,j:1≤i<j≤n,Ai∩Aj都是单元集;3.A1∩A2∩……∩An=空集 求使这样的集合族存在的最
这个悬赏80--100比较合理,加价吧,
1\2n(n-1)≤30且 n为整数 ,所以n取8
我们考虑所有Ai的并集,设共有m个元素,记为b1,b2,…,bm。定义集合:B1,B2,…Bm,满足,若bj∈Ai,则Ai∈Bj。也就是我们构造了原集合的对偶集合。
这些B1,B2,…,Bm,不难发现有如下性质:
(1)任何两个之间至多只有一个公共元素。(2)每一个Bj没有包含所有的A1,A2,…,An。(3)每一个二元组(Ai,Aj)恰好在某一个Bk中。(4)每一个Ai恰属于30...
全部展开
我们考虑所有Ai的并集,设共有m个元素,记为b1,b2,…,bm。定义集合:B1,B2,…Bm,满足,若bj∈Ai,则Ai∈Bj。也就是我们构造了原集合的对偶集合。
这些B1,B2,…,Bm,不难发现有如下性质:
(1)任何两个之间至多只有一个公共元素。(2)每一个Bj没有包含所有的A1,A2,…,An。(3)每一个二元组(Ai,Aj)恰好在某一个Bk中。(4)每一个Ai恰属于30个不同的Bj。
下面我们证明任何一个Bj至多只有30个元素,用反证法,假设有一个B1包含了31个元素,不妨设这个集合为B1,这31个元素为A1,A2,…A31。由性质(3),这31个元素中的任意两个不能同时出现在另一个Bi中了。由性质(2),我们可以找到一个不同于这31个元素的一个As,由性质(3),这个As必须与A1,A2,…A31一起搭配过,也就是说二元组(As,Al)(l=1,2,…,31)必须同属于互异的31个集合:Bi1,Bi2,…,Bi31。这样As就在31个Bi中出现了,与性质(4)矛盾。
下面来估计。
对二元组(Ai,Aj)计算,一方面,它的数目为n*(n-1)/2。另一个方面,考察每一个|Bi|,它们的和为30n,不难发现,当每一个|Bi|都是30的时候,所有Bi的二元组数目之和最大(即在知道总和的情况下,求|Bi|的所有组合数的和最大)。于是我们有不等式
n*(n-1)/2<=30*29/2*n;
解得n<=871.最大n为871.
构造就不写了。根据等号成立条件就行了。
收起