集合的子集族设X为一个n元素集, F={A1,A2,...,Am}是X的一个子集族, 且满足Ai交Aj为单元素集（对于任意的互异i,j）,求证m不大于n.lca001的分类讨论法与xtimz的运用高等代数的方法都好，前者更有独

集合的子集族设X为一个n元素集, F={A1,A2,...,Am}是X的一个子集族, 且满足Ai交Aj为单元素集（对于任意的互异i,j）,求证m不大于n.lca001的分类讨论法与xtimz的运用高等代数的方法都好，前者更有独
集合的子集族
设X为一个n元素集, F={A1,A2,...,Am}是X的一个子集族, 且满足Ai交Aj为单元素集（对于任意的互异i,j）,求证m不大于n.
lca001的分类讨论法与xtimz的运用高等代数的方法都好，前者更有独立思考性，没有依赖已有的结论。
现将问题中条件改变下：“满足Ai交Aj为空集或者单元素集”，则此时m，n之间满足什么关系？

集合的子集族设X为一个n元素集, F={A1,A2,...,Am}是X的一个子集族, 且满足Ai交Aj为单元素集（对于任意的互异i,j）,求证m不大于n.lca001的分类讨论法与xtimz的运用高等代数的方法都好，前者更有独
我的解答需要一些简单的线性代数.
我们先把Ai按元素个数从小到大排序,也就是1

反证法

我认为lca001的证法有问题，因为对F中所有子集多于两个元素的时候，他用了所有pi两两乘积求和的式子。虽然只分两个大类的时候是pq个不同元素，但是类别一多却不一定是每两个的不同元素相加。例如：3个类别的时候。设这三个类别是A、B、C。设A的一个集合和B的一个集合交于1，B的这个集合又和C的一个集合交于1，C的这个集合又和A的一个集合交于1，求和的时候1就算了3次。这其中似乎还有重复的。
...

全部展开

我认为lca001的证法有问题，因为对F中所有子集多于两个元素的时候，他用了所有pi两两乘积求和的式子。虽然只分两个大类的时候是pq个不同元素，但是类别一多却不一定是每两个的不同元素相加。例如：3个类别的时候。设这三个类别是A、B、C。设A的一个集合和B的一个集合交于1，B的这个集合又和C的一个集合交于1，C的这个集合又和A的一个集合交于1，求和的时候1就算了3次。这其中似乎还有重复的。
至于条件改了之后的题目，我认为是变简单了。你看，如果已经有了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。

收起

http://hi.baidu.com/lca001/blog/item/13ee280e3979213b6159f352.html?timeStamp=1293003588171
空集的情况十分简单，m≤n+1，否则n+1证明...

全部展开

http://hi.baidu.com/lca001/blog/item/13ee280e3979213b6159f352.html?timeStamp=1293003588171
空集的情况十分简单，m≤n+1，否则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

收起

设F中元素最多的一个集合为Ax
可以设这个集合为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中元素最多的一个集合为Ax
可以设这个集合为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

收起