当前位置:首页 >> 学科竞赛 >>

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

集合(二)
【经验谈】 集合是数学中的重要基础知识, 不论是高考还是数学竞赛中都少不了它的一席之地。 本 文将帮助你彻底掌握集合知识。 【内容综述】 集合是组合数学的基础, 也是高中数学竞赛中的重要组成部分。 希望大家通过本讲学习 开拓思路,灵活解题,另外,要想解好集合题目,相关知识也很重要。 【例题分析】 例 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.不能。反证法。设存在合乎题中条件的一种分法,如果 记为 ,否则记为 ,对 ,若 和 同属于一个子集,则 为好的。 都 是好的。 , 在第二组中用 代替 由此 盾! 有这样一个结论 阶集合的子集 若满足 且 则 的最大值 ,而 ,故 是好的。故 即 ,但 ,故 。 。矛

分在三个集合中则称



,代入本题得为




相关文章:
高中数学奥赛系列辅导材料 集合(二).doc
高中数学奥赛系列辅导材料 集合(二) - 集合(二) 【经验谈】 集合是数学中的
【配套K12】高中数学奥赛系列辅导材料 集合(二)教案.doc
【配套K12】高中数学奥赛系列辅导材料 集合(二)教案 - 小初高试卷教案类 集合(二) 【经验谈】 集合是数学中的重要基础知识, 不论是高考还是数学竞赛中都少不...
高中数学奥赛系列辅导材料 集合(一).doc
高中数学奥赛系列辅导材料 集合(一) - 集合(一) 内容综述: 本讲先介绍了以
高中数学竞赛系列辅导材料(1)--集合1.doc
高中数学竞赛系列辅导材料(1)--集合1_学科竞赛_高中教育_教育专区。www.100...所以 n ( n+1 ) (n+2) (n+3) (n+4) (n+5) 0、1 ...
【K12教育学习资料】高中数学奥赛系列辅导资料 集合(1)....doc
【K12教育学习资料】高中数学奥赛系列辅导资料 集合(1)教案 - 教育是最好的老师,小学初中高中资料汇集 集合(一) 内容综述: 本讲先介绍了以下一些重要的概念:集合...
高中数学奥赛辅导系列集合与简易逻辑.doc
高中数学奥赛辅导系列集合与简易逻辑 - 集合与简易逻辑 一、基础知识: 1. 元素与集合:a∈A,b 2. 集合集合:A ? B,A 3. 4. 5. 6. A B,A B...
高中数学奥赛辅导系列3-集合与简易逻辑.pdf
高中数学奥赛辅导系列3-集合与简易逻辑 - 集合与简易逻辑 一、基础知识: 1. 元素与集合:a∈A,bA 2. 集合集合:AB,AB,AB,A∩B,A∪B,A,…… 3. 差集...
配套K12高中数学奥赛辅导系列集合与简易逻辑.doc
配套K12高中数学奥赛辅导系列集合与简易逻辑 - 小学+初中+高中+努力=大学 集合与简易逻辑 一、基础知识: 1. 元素与集合:a∈A,b?A 2. 集合集合:A? ...
2019-2020年高中数学竞赛辅导资料《集合》.doc
2019-2020 年高中数学竞赛辅导资料集合集合的划分反映了集合与子集之
配套K12高中数学奥赛系列辅导材料 数论函数教案.doc
配套K12高中数学奥赛系列辅导材料 数论函数教案_数学_高中教育_教育专区。小学
高中数学奥赛系列辅导材料赋值法在函数方程中的应用教案.pdf
高中数学奥赛系列辅导材料赋值法在函数方程中的应用教案_数学_高中教育_教育专区。
【K12教育学习资料】高中数学奥赛系列辅导材料 数论函....doc
【K12教育学习资料】高中数学奥赛系列辅导材料 数论函数教案_数学_高中教育_教育专区。教育是最好的老师,小学初中高中资料汇集 数论函数 【内容综述】 本讲介绍数论...
高中数学奥赛辅导系列集合与简易逻辑.doc
高中数学奥赛辅导系列集合与简易逻辑 - 集合与简易逻辑 一、基础知识: 1. 元素与集合:a∈A,b?A 2. 集合集合:A ? B,A?B,A?B,A∩B,A∪B, ?...
高中数学奥赛系列辅导资料:数学学习中的学法指导.doc
高中数学奥赛系列辅导资料:数学学习中的学法指导_学科竞赛_高中教育_教育专区。...§2 大概念 小计算 要学好数学,一定要重视概念的学习 例 8.已知集合 的值。...
高中数学奥赛系列辅导材料11:动点轨迹方程的求法.doc
高中数学奥赛系列辅导材料11:动点轨迹方程的求法 高中竞赛数学精品资料高中竞赛数学精品资料隐藏>> 动点轨迹方程的求法一,直接法 按求动点轨迹方程的一般步骤求,其过...
[推荐学习]高中数学奥赛系列辅导资料 数学学习中的学法....doc
[推荐学习]高中数学奥赛系列辅导资料 数学学习中的学法指导教案_数学_高中教育_...§2 大概念 小计算 要学好数学,一定要重视概念的学习 例 8.已知集合 的值。...
配套K12高中数学奥赛系列辅导材料 赋值法在函数方程中....doc
配套K12高中数学奥赛系列辅导材料 赋值法在函数方程中的应用教案_数学_高中教育_...2x(x ?1) (2) (3) 例 10 f (x)的定义域在非负实数集合上并取非负数...
高中数学奥赛系列辅导材料赋值法在函数方程中的应用.doc
高中数学奥赛系列辅导材料赋值法在函数方程中的应用_数学_高中教育_教育专区。高中数学奥赛系列辅导材料赋值法在函数方程中的应用,高中数学必修三变量与赋值,高中数学...
【推荐】高中数学奥赛系列辅导材料数论函数教案.pdf
【推荐】高中数学奥赛系列辅导材料数论函数教案_数学_高中教育_教育专区。小学 +
半导体元件系列应用参数 - 百度文库.txt
Y2系列电机参数表 y系列电机技术参数 y系列电机参数 存储系列参数表 系列元件引脚图 y2系列电机参数 高中数学奥赛辅导系列 Y2系列电动机参数 4.5 分1906人阅读 ...
更多相关标签: