高中数学奥赛系列辅导资料：集合(2).doc

集合(二)
【经验谈】
　　集合是数学中的重要基础知识，不论是高考还是数学竞赛中都少不了它的一席之地。本文将帮助你彻底掌握集合知识。

【内容综述】
集合是组合数学的基础，也是高中数学竞赛中的重要组成部分。希望大家通过本讲学习开拓思路，灵活解题，另外，要想解好集合题目，相关知识也很重要。

【例题分析】
　　例1：设，，…是有限集合的50个子集，每个子集都含有的半数以上的元素，证明：存在子集，它至多含5个元素，并且和集合，…中每一个集合至少有一个公共元。
　　分析：我们知道，这种题目并没有什么特别好的办法，只能一个一个把这5个元素找出来，我们还是可以先将题目简化成简单形式，看是否方便理解一些，但这里我们就不这么做了。
　　证明：设集合中元素个数为n，子集，，…中每一个都含以上的元素，即所有这些子集的元素个数大于 由抽屉原理，必有集合的元素，它至少属于26个子集，同理可证，对每个，在子集，，…，中至少有个子集，它们具有公共元素，在集合中取出一个元素，它至少属于26个子集，并作为集合 中五个元素之一，去掉包含这个元素的26个子集，在余下24个子集中取一个元素，它至少属于13个子集，去掉这13个子集，在余下的11个子集中取一个元素，它至少属于6个子集，在余下5个子集中取一个元素，它属于3个子集，剩下两个子集再取一个公共元素就可以了，于是，求得集合的至多5个元素（在上述过程中所取的元素可能重复，所以可能小于5），它们构成集合，而子集，，…中每一个都至少含有它的一个元素。
　　说明：这道题目当和均较小时也就可以作为小学生竞赛题，而数目增大以后却成为了英国高中竞赛题目，假设我们在分析较小的数时可以把规律找出，而这是很简单的，那么整道题目也就迎刃而解了，这就告诉我们，做这类整数问题时，应该时时刻刻想到先将数目变小看看规律，然后再做题目本身。

　 例2：有11人管理一个保险柜，可以在柜上加若干把锁，每把锁可以有若干把钥匙，问：如何加锁和如何分配各锁的钥匙，才能使任何6个人可以把保险柜打开，但任意5个人却不能。
　　分析：我们反过来想一下，假设…是11个人打不开的锁的集合，从11个人中任意找5个人的可能性有种情况。要想把它们都区别开，也就是说至少要有462把锁。那么再对462把锁进行构造就可以了。
　　解：设加把锁，又设，，…是这11个人各自打不开的锁的集合，从11个集合中任选5个并集都不相同，故至少应有锁把，为分配好各锁的钥匙，设锁号依次为1号，2号，…462号，同时把11个人任取5个的组合也编上1至462号，然后把锁和组合一一对应起来，给每个人发钥匙时，他所在的组的号的钥匙不给他，其他钥匙都给他，这时就满足题设了。
　　说明：这个构造难度很大，这主要原因还是因数目太大了，也应该先从小的数目做起，最后回到原题。

例3把个元素的集合分为若干个两两不交的子集，按照下述规则将某一个子集中某些元素挪到另一个子集：从前一子集挪到后一子集的元素个数等于后一子集的元素个数（前一子集的元素个数应不小于后一子集的元素个数），证明：可以经过有限次挪动，使得到的子集与原集合相重合。
分析：首先考虑到是一个很特殊的数，其次我们发现若两个集合的元素个数除以2的若干次幂后若为奇数，那么，它们之间挪后就应为偶数这一事实，若还不能想到解答就试一下，时的情况，相信解答就不会难找到了。
证明：考虑含奇数个元素的子集（如果有这样的子集），因为所有子集所含元素的个数总和是偶数，所以具有奇数个元素的子集个数也是偶数，任意将所有含有奇数个元素的子集配成对，对每对子集按题目要求的规则移动：从较大的子集挪出一些元素，添加到较小的子集，挪出的元素个数为较小子集的元素个数，于是得到的所有子集的元素个数都是偶数，现在考虑元素个数不被4整除的子集，如果，则总共有两个元素，它们在同一个子集，因此设，因为子集的元素个数的总数被4整除，因此这样的子集的个数为偶数，任意将这样的子集配成对，对每一对子集施行满足题目要求的挪动，于是得到的每个子集数均可被4整除，依此做下去，最后得到的每个子集元素个数均可被整除，也就是只能有一个子集，它的元素个数为，证毕。
说明：这道题的证明中隐含了一种单一变量在变化时变化方向相同这一性质，就这道题来说，一直在增加的就是各子集元素个数被2的多少次幂整除的这个幂次数，这是一大类问题，除了这种变化量，还要经常考虑变化中的不变量。

例4：给定1978个集合，每个集合都含有40个元素，已知其中任意两个集合都恰有一个公共元，证明：存在一个元素，它属于全部集合。
分析：我们可以先去找一个属于很多个集合的元素，最好它就是我们要找的那一个。
证明：考虑给定的1978个集合中任意一个集合，它和其它1977个集合都相交，因此，存在，使得它至少属于其中50个集合，否则，集合中每个元素至多属于49个集合，而集合恰有40个元素，所以除外至多有1960个集合，不可能，因此设属于集合，…，下面证明它属于给定的1978个集合中任一个。
对于除了，，…的任一个集合，设，则与，，，…每一个都有至少一个元素的交，它们都与不同，那么，就至少要有51个元素，不可能，因此属于每个集合。
说明：这种题目最怕把它想难了，想行太难了，就会觉得无从下手，做数学竞赛题就需要一方面在做题之前选好方向，另一方面就是大胆尝试去做。

例5：在一个含10个元素的集合的若干非空子集中，任意两个不同的子集的交集含有中元素的数目不多于2，这样的子集合有多少个。
分析：的一元素子集和二元素子集显然都是满足条件的，三元子集呢？如果有一个多于3元的子集，总可以把它拆为三元子集的并，增加子集的数量而不影响性质，而恰恰把全部三元子集都选上也符合题目要求。
解：中的单元素子集共10个，这10个都符合题目的要求。
中的含两个元素的集合共个，它们也符合要求。
中含三个元素的集合共个，也符合要求。
这表明，的子集合中，至少有个子集满足条件。
另一方面，假设的非空子集有多于175个具有题目中的条件。设这个子集族为，其中 则中必存在含有中的元素数超过3的集合，设，取，作差集，显然，，这表明与不能同为子集族中的成员，用替换，得到另一个子集族： ，容易看到也符合题目中的条件，并且，经过这样的替换后，中某个元素被含中元素少于的另一个的子集所替代，因为，中的元素数目有限。所以有限次替代后，总可使新的子集族中各元素含有中的元素数目不超过3，这就看出与矛盾这表明不存在符合题目条件的多于175个的的子集形成的子集族，即这样的子集族恰有175个。
说明：这道题是一类典型问题的代表，这种问题的解法就是先构造，然后证明更多或更少不行。在证明过程中尽量把它往构造出来的方向化规。
例6：在个元素组成的集合中取个不同的三元子集。证明：其中必有两个，它们恰有一个公共元。
分析：证明恰有一个公共元也许挺难。那么证只有两个或零个公共元不可能是否可行呢？如果具有两个公共元的集合与表示为、那么~有传递性。是否有用呢？
证明：设结论不真。则所给的3元子集要么不交，要么恰有两个公共元，如果子集与恰有两个公共元，则记。设是三个子集。可以证明如果，，则，于是所有给定的3元子集可以分类，使得同一类中任意两个不同子集都恰有两个公共元。而不同类的子集不相交。于是对每个子集类，有三种可能：（1）恰含3个元素的类。（2）恰含4个元素的类。（3）至少含5个元素的类。
在（1）下，3元子集类恰由一个3元子集组成。
在（2）下，子集类中至多有4个子集。
考虑（3） 设，，则还有一个，由，，有。因此对子集类中任意子集，由，，它包含与，于是类中子集个数比类中元素个数少2，于是，每个类中子集个数不超过元素个数，但是题中条件子集数大于元素个数，矛盾！
说明：此题为1979年美国竞赛题。题目难度较大，应该说是应用了高等代数中的一些思想。

1．求的所有子集元素的和之和。
　　2．小明去买东西，现在他有10元，希望分成10包，使在商店内他能买起的东西都可由包中的钱直接支付。
　　3．能否把整数集合分成3个子集，使得对每个整数，都属于不同的集合。
　　4．10名学生按下面的规则组成运动队，规则是：①每人可报名参加任何一个运动队；②每个运动队都不能完全包含于或重合于另一个运动队。问：最多几个队？每队分别多少人？

参考答案
　　1．我们可以发现对每个数，它出现在个子集之中，因此所有子集中的的和为，那么全部元素在全部子集之中的和为。
　　2．利用二进制来考虑此题，小明的前9包分别有钱 1分（2），10分（2），100分（2），1000分（2），10000分（2），100000分（2），1000000分（2），10000000分（2），100000000分（2），剩下一包装剩下的钱（以上数皆为二进制）就可以了。
　　3．不能。反证法。设存在合乎题中条件的一种分法，如果和同属于一个子集，则记为，否则记为，对，若分在三个集合中则称为好的。
　　都是好的。
　　，，而 ，故
　　在第二组中用代替，故是好的。故。
　　由此 即，但。矛盾！
有这样一个结论阶集合的子集若满足且则的最大值为，代入本题得为。

21世纪教育网