集合的子集族
发布网友
发布时间：2023-03-26 20:52
共5个回答
热心网友
时间：2023-10-22 03:03
至于条件改了之后的题目，我认为是变简单了。你看，如果已经有了m个集合A1，……，Am满足改动之后的条件，如果它们的元素个数都少于等于2，就不进行操作。否则，若存在一个Ai的元素个数不少于3，那么在Ai中去掉一个元素之后得到一个新的Ai。显然，这个新的Ai不会和其他集合重复，否则原Ai至少与某一个集合交于3-1=2个元素。另外，这个新的Ai至多与其他集合交于一个元素，这是显然的。故进行操作之后得到的A1，……，Am仍然具有题目要求的性质。
多次操作直到所有的Ai都不多于两个元素。显然，这样就可以知道m≤n+n(n-1)/2。另一方面，取出n的所有一元集和二元集组成一个子集族，则它满足题目所要求的条件，并且这个子集族的元素个数为n+n(n-1)/2，故m的最大值为n+n(n-1)/2。
热心网友
时间：2023-10-22 03:03
空集的情况十分简单，m≤n+1，否则n+1<m,n<m-1,除空集外，F至少有m-1个非空子集，则必有一元在两个子集内。故“满足Ai交Aj为空集或者单元素集”，则此时m，n之间满足关系m≤n+1。
证明 设X={a1,a2,…,an}, F是X的一个子集族,由题中条件可知F中任意两个子集均有一个且仅有一个共同元素.
(1).如果F中有一个是单元素集,不妨设A1是单元素集,A1={a1},
则F中其它所有的子集A2,A3,...,Am均与A1有共同的元素a1,
A1-{a1},A2-{a1},...,Am-{a1}必互不相同,而且A1-{a1},A2-{a1},...,Am-{a1}中任意两个子集不能再有共同元素,否则与F中任意两个不同子集仅有一个共同元素矛盾,此时A1-{ai},A2-{ai},...,Am-{ai}最多是n个(包括空集),故m≤n;
[如X={1,2,3,4,5}, A1={1}, A2={1,2}, A3={1,3}, A4={1,4}, A5={1,5}是子集最多时的情况]
(2). 如果F中没有一个单元素集,即F中所有子集至少有两个元素,假设A1={ a1,a2}有两个元素，那么F中其它所有的子集必分为两大类,一类是与A1有共同元素a1的集合,一类是与A1有共同元素a2的集合,前者设为F1,后者设为F2,即F1中的子集均是与A1有共同元素a1的集合,F2中的子集均是与A1有共同元素a2的集合,设F1中的子集的个数为∣F1∣=p, F2中的子集的个数为∣F2∣=q,则p+q+1=m.
设Ai 是F1中的任意集合, Aj是F2中的任意集合,由题中条件可知Ai与Aj必有一个共同元素b,该元素b既不等于a1也等于a2,否则与题中的条件矛盾,另一方面,如果Ai1是不同于Ai的F1中的另一个子集, Aj1是不同于Aj的F2中的另一个子集, Ai1与Aji也必有一个共同元素b1,b1也不同于b,故F1中每一个子集与F2中每一个子集均有一个共同元素,共pq个不同元素,再加上a1,a2两个元素其总数不超过n,即有
pq+2≤n, p+q+1=m,
由(p-1)(q-1)≥0,pq-p-q+1≥0,pq+2≥p+q+1,m= p+q+1≤pq+2≤n.
[如果子集含有两个元素,上式取等号当且仅当p=q=1时,此时n=3,如X={1,2,3}, A1={1,2}, A2={1,3}, A3={2,3}]
(3). 如果F中所有子集多于两个元素,类似上面(2).的证明.
http://hi.baidu.com/lca001/blog/item/c137a842077c1b0273f05d88.html?timeStamp=1292602947078
热心网友
时间：2023-10-22 03:04
可以设这个集合为F={1,2,3,4,5}
则Ai和Aj一定属于{1,2,3,4,5}或者{1,2,3},{3,4,5}
最大的集合为F0={1,2,3,4,5}元素数量为N
第二类集合的数量为n,元素数量为N'
则一定有第二类元素的数量N'=(N+n-1)/n=f(x)
则f(x)=N/n+1-1/n 则N最小的集合形式为F={1,2,3}
Ai和Aj属于{1,2},{2,3}
所以f(x)=3/2+1-1/2=2=N'
N'一定小于N
当Ai或Aj取到F0时集合=F
所以m<=n
热心网友
时间：2023-10-22 03:04
我们先把Ai按元素个数从小到大排序，也就是1<=|A1|<|A2|<=|A3|<=...<=|Am|<=n。
很显然，|A2|必须大于1。
定义m*n的矩阵：M
M的每个元素是0或1，如果Ai包含元素j，则M(i,j)=1；否则M(i,j)=0。
考察M*M'，其中M‘代表M的转置矩阵。
M*M'是一个m*m的矩阵，它的对角元素依次为|A1|、|A2|、...、|Am|，其它非对角元素都是1。
可以证明（略），M*M'的秩为m（证明方法：高斯消元即可）。
关键的线性代数知识在下面：
作为一个m*n的矩阵M，它的秩最大为n。
根据定理，M*M'的秩<=M的秩，所以：m<=n。
热心网友
时间：2023-10-22 03:05
