且。
说明:复杂的问题先考虑简单的特殊的情况是一种最常用的方法,从中找到
共性后就很容易得到原题目有答案了。
1.一个集合含有10个互不相同的十进制两位数,证明:这个集合必有两个无公共元素的子集合,这两个子集元素和相等。
2.是否存在两个以非页整数为元素的集合A、B,使得任一个非负整数都可以被A、B之中各取一数之和唯一表出。
3.对每个两个的交非合。
4.能否把
分成两个积相等的不交集合。
使得在n元集合中,可以取出k个子集,其中任意
参考答案
1.10个元素的集合共有
子集中数字之和小于元素和,设为
2.十进制
个非空子集,每一个这个集合的非空
,由抽屉原则知,必有两个子集,它们有相同的
满足题目要求条件。为第1位。
为第i位,考虑如下的A、B:
A为奇位为o的那些非负整数组成。B为偶位为o的那些非负整数组成。不难验证这样的AB是符合题目要求的。3.在集合
类子集的个数为集合
中取定一个元素的子集的个数,即为
,并只考虑含。因此
的子集,这。另一方面,
设从集合X至少取出个子集,将集合X的所有子集分成对。每一对由一
个子集与它的补集组成,由抽屉原则,所取子集至少有两个组成一对,因此它们不交,于是
。
4.对7取模,由于(mod7).
所以n·(n+1)·(n+2)·(n+3)·(n+4)·(n+5)0、1、4、2(mod7),所以集合
足要求的集合。
(mod7),而若能拆分应为
不能拆成满
均不能为7的位数,所以
集合(二)
【经验谈】
集合是数学中的重要基础知识,不论是高考还是数学竞赛中都少不了它的一席之地。本文将帮助你彻底掌握集合知识。
【内容综述】
集合是组合数学的基础,也是高中数学竞赛中的重要组成部分。希望大家通过本讲学习开拓思路,灵活解题,另外,要想解好集合题目,相关知识也很重要。【例题分析】
例1:设
,
,…
是有限集合
的50个子集,每个子集都含有
,
…
的半数以上中每一个
的元素,证明:存在子集,它至多含5个元素,并且和集合
集合至少有一个公共元。
分析:我们知道,这种题目并没有什么特别好的办法,只能一个一个把这5个元素找出来,我们还是可以先将题目简化成简单形式,看是否方便理解一些,但这里我们就不这么做了。
证明:设集合
中元素个数为n,子集
,
,…
中每一个都含
以上的元素,
即所有这些子集的元素个数大于由抽屉原理,必有集合的元素,它至少属
于26个子集,同理可证,对每个个子集,它们具有公共元素,在集合合
,在子集,,…,中至少有
中取出一个元素,它至少属于26个子集,并作为集
中五个元素之一,去掉包含这个元素的26个子集,在余下24个子集中取一个元素,
它至少属于13个子集,去掉这13个子集,在余下的11个子集中取一个元素,它至少属于6个子集,在余下5个子集中取一个元素,它属于3个子集,剩下两个子集再取一个公共元素就可以了,于是,求得集合可能小于5),它们构成集合
的至多5个元素(在上述过程中所取的元素可能重复,所以,而子集
,
,…
中每一个都至少含有它的一个元素。
说明:这道题目当和均较小时也就可以作为小学生竞赛题,而数目增大以后却成为了英国高中竞赛题目,假设我们在分析较小的数时可以把规律找出,而这是很简单的,那么整道题目也就迎刃而解了,这就告诉我们,做这类整数问题时,应该时时刻刻想到先将数目变小看看规律,然后再做题目本身。
例2:有11人管理一个保险柜,可以在柜上加若干把锁,每把锁可以有若干把钥匙,
问:如何加锁和如何分配各锁的钥匙,才能使任何6个人可以把保险柜打开,但任意5个人却不能。
分析:我们反过来想一下,假设个人中任意找5个人的可能性有
,
,…
是11个人打不开的锁的集合,从11
种情况。要想把它们都区别开,也就是说至少要
有462把锁。那么再对462把锁进行构造就可以了。
解:设加把锁,又设
,
,…
是这11个人各自打不开的锁的集合,从11个
把,为分配好各锁的钥匙,设锁号
集合中任选5个并集都不相同,故至少应有锁
依次为1号,2号,…462号,同时把11个人任取5个的组合也编上1至462号,然后把锁和组合一一对应起来,给每个人发钥匙时,他所在的组的号的钥匙不给他,其他钥匙都给他,这时就满足题设了。
说明:这个构造难度很大,这主要原因还是因数目太大了,也应该先从小的数目做起,最后回到原题。
例3:把个元素的集合分为若干个两两不交的子集,按照下述规则将某一个子集中某
些元素挪到另一个子集:从前一子集挪到后一子集的元素个数等于后一子集的元素个数(前一子集的元素个数应不小于后一子集的元素个数),证明:可以经过有限次挪动,使得到的子集与原集合相重合。
分析:首先考虑到
是一个很特殊的数,其次我们发现若两个集合的元素个数除以2
的若干次幂后若为奇数,那么,它们之间挪后就应为偶数这一事实,若还不能想到解答就试一下
,
时的情况,相信解答就不会难找到了。
证明:考虑含奇数个元素的子集(如果有这样的子集),因为所有子集所含元素的个数总和是偶数,所以具有奇数个元素的子集个数也是偶数,任意将所有含有奇数个元素的子集配成对,对每对子集按题目要求的规则移动:从较大的子集挪出一些元素,添加到较小的子集,挪出的元素个数为较小子集的元素个数,于是得到的所有子集的元素个数都是偶数,现在考虑元素个数不被4整除的子集,如果因此设
,则总共有两个元素,它们在同一个子集,
,因为子集的元素个数的总数被4整除,因此这样的子集的个数为偶数,任意
将这样的子集配成对,对每一对子集施行满足题目要求的挪动,于是得到的每个子集数均可被4整除,依此做下去,最后得到的每个子集元素个数均可被子集,它的元素个数为
,证毕。
整除,也就是只能有一个
说明:这道题的证明中隐含了一种单一变量在变化时变化方向相同这一性质,就这道题来说,一直在增加的就是各子集元素个数被2的多少次幂整除的这个幂次数,这是一大类问题,除了这种变化量,还要经常考虑变化中的不变量。
例4:给定1978个集合,每个集合都含有40个元素,已知其中任意两个集合都恰有一个公共元,证明:存在一个元素,它属于全部集合。
分析:我们可以先去找一个属于很多个集合的元素,最好它就是我们要找的那一个。
证明:考虑给定的1978个集合中任意一个集合此,存在集合,而集合合
,
…
,它和其它1977个集合都相交,因
中每个元素至多属于49个
,使得它至少属于其中50个集合,否则,集合恰有40个元素,所以除
外至多有1960个集合,不可能,因此设属于集
,下面证明它属于给定的1978个集合中任一个。,
,…
的任一个集合
,设
,则
与
,
,
,…
对于除了
每一个都有至少一个元素的交,它们都与不同,那么,就至少要有51个元素,不可能,
因此属于每个集合。
说明:这种题目最怕把它想难了,想行太难了,就会觉得无从下手,做数学竞赛题就需要一方面在做题之前选好方向,另一方面就是大胆尝试去做。
例5:在一个含10个元素的集合有
的若干非空子集中,任意两个不同的子集的交集含
中元素的数目不多于2,这样的子集合有多少个。分析:
的一元素子集和二元素子集显然都是满足条件的,三元子集呢?如果有一个
多于3元的子集,总可以把它拆为三元子集的并,增加子集的数量而不影响性质,而恰恰把全部三元子集都选上也符合题目要求。
解:
中的单元素子集共10个,这10个都符合题目的要求。
个,它们也符合要求。个,也符合要求。
个子集满足条件。
,
中的含两个元素的集合共中含三个元素的集合共这表明,
的子集合中,至少有
另一方面,假设其中
,取与
的非空子集有多于175个具有题目中的条件。设这个子集族为
则
中必存在含有
中的元素数超过3的集合,设,替换
,这表明
,得到另一个子集族:
,作差集不能同为子集族
,显然中的成员,用
高中数学奥赛系列辅导材料
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)