当前位置:首页 >> 学科竞赛 >> 高中数学奥赛系列辅导资料:集合(2)

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


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

集合是组合数学的基础, 也是高中数学竞赛中的重要组成部 分。希望大家通过本讲学习开拓思路,灵活解题,另外,要想解好集 合题目,相关知识也很重要。
【例题分析】 例 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 的集合,设 , , 这表明

, 作差集

, 显然



不能同为子集族

中的成员,用 ,容易看到

替换

,得到另一个子集族: , 所替

也符合题目中的条件,并且 的另一个 的子集

经过这样的替换后, 代,因为

中某个元素

被含

中元素少于

, 中的元素数目有限。所以有限次替代后,总可使新的子集族中各元素含有 与 矛盾,这表明不存

中的元素数目不超过 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 世纪教育网


更多相关文档:

高中数学奥赛系列辅导资料:集合(1)

高中数学奥赛系列辅导资料:集合(1)_学科竞赛_高中教育_教育专区。集合(一)内容...所以 n· (n+1)· (n+2)· (n+3)· (n+4)· (n+5) 1、4、2 ...

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

高中数学奥赛系列辅导资料:集合(2)_学科竞赛_高中教育_教育专区。集合(二) 【经验谈】 集合是数学中的重要基础知识, 不论是高考还是数学竞赛中都少不了它的一席...

高中数学奥赛系列辅导材料2:集合(一)

高中数学奥赛系列辅导材料2:集合(一)高中数学奥赛系列辅导材料2:集合(一)隐藏>> 高中数学奥赛系列辅导材料 1 集合( 一) 集合 (内容综述: 内容综述 本讲先介绍...

高中数学奥赛系列辅导材料 集合(一)

高中数学奥赛系列辅导材料 集合(一)_学科竞赛_高中教育_教育专区。集合(一)内容...所以 n· ( n+1 )· (n+2)· (n+3)· (n+4)· (n+5) 0 、 ...

高中数学奥赛系列辅导材料2:集合(二)

高中数学奥赛系列辅导材料2:集合(二)高中数学奥赛系列辅导材料2:集合(二)隐藏>> 高中数学奥赛系列辅导材料 2 集合( 集合(二) 【经验谈】 经验谈】 集合是数学...

高中数学奥赛辅导系列1-集合(一)

n 阶集合的全部子集数目为 。 A , B , C 为三个集合,就有下面的定律。 ( 1)分配律 1 高中数学奥赛辅导系列 1---集合 1 ( 2)零律 ( 3)排中律 (...

高中数学竞赛系列辅导材料(1)--集合1

高中数学竞赛系列辅导材料(1)--集合1_学科竞赛_高中教育_教育专区。www.100...所以 n· ( n+1 )· (n+2)· (n+3)· (n+4)· (n+5) 0、1 ...

高中数学奥赛系列辅导材料 数学竞赛训练题

高中数学奥赛系列辅导材料 数学竞赛训练题_学科竞赛_高中教育_教育专区。数学竞赛...(A)-7 2.1999- (A)-2001 (B)7 (C)- (D) 的值等于( ) (B)1997 ...

高中数学奥赛系列辅导资料:数列奥赛竞赛练兵

高中数学奥赛系列辅导资料:数列奥赛竞赛练兵_学科竞赛_高中教育_教育专区。数列奥赛...2ax数列奥赛竞赛练兵一、选择题 1.(2000 年全国高中数学联赛)给定正数 p,q,...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com