第三节 子集与集合的分划

高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编写

第三节 子集与子集的分划

一个集合可以写成若干个集合的并集，这是对集合分类讨论的常用方法.对于一个较为复杂的集合,我们在研究其性质时,往往可以划分成若干个小集合的并集进行研究,通过对这些小集合的性质的研究,可以达到化整为零、化繁为易的效果. 集合的分划反映了集合与子集之间的关系，这既是一类数学问题，也是数学中的解题策略——分类思想的基础，在近几年来的数学竞赛中经常出现，日益受到重视. 本讲主要介绍有关的概念、结论以及处理集合、子集与划分问题的方法.

【基础知识】

一．集合的分划 1.集合分划的概念：

把一个集合M分成若干个非空子集：（1）A1,A2,?,An.如果满足Ai?Aj??(1?i,j?n)；（2）

?Ai?1ni?M，那么称这些子集的全体为集合M的一个n－分划，其中每一个子集叫做

集合M的一个类. 2．加法原理

由集合分划的定义，容易证明有限的一个非常有用的性质：设A1,A2,?,An.是有限集n－分划，则Card(M)??Card(A)，这是一个基本的计数公式，被称为加法原理.

ii?1n3．最小数原理（极端原理）

最小数原理I:设M是正整数集的一个非空子集，则M中必有最小数.

最小数原理II:设M是实数集的一个有限的非空子集，则M中必有最小数. 推论：设M是实数集的一个有限非空子集，则M中必有最大数. 二．子集族

1．子集族的概念

我们可以将某些集合取来作为元素构成一个新的集合，例如A?{{1},{0,1}{0},?}就是含4个元素{1},{0,1}{0},?的集合，特别地，将集合M的若干个子集作为元素构成的集合M*

**叫做原集合的一个子集族.如上例中的A就是二元集A?{0,1}的全部子集构成的子集族.子集族中所含原来集合的子集的数目叫做该子集族的阶.例如子集族A的阶为4，即|A|?4. 2．C族

最简单的子集族是由有限集M的全体子集所构成的子集族，简称为C族. 3．C族的性质

设|M|?n，则集合M的全体子集所构成的集合M的阶为2.即

01n|M*|?Cn?Cn???Cn?2n.

**

*n

30

高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编写

4．R族

设Card(A)?n,M?{A若存在k(2?k?m?1)使得： 1,A2,?,An}是A的一个子集族，(1)M中任意k个Ai都相交；(2)M中任意(k?1)个Ai都不相交. 则称M为A的一个指数为k的R族.

kk定理：如果M?{A1,A2,?,An}是A的一个指数为的R族，Card(A)?n，则Cm?n.

5．K族

设A为一个n阶集合，M?{A1,A2,?,An}是A的一个子集族.若M中任何两个A的子集Ai和Aj互不包含，即Ai?Aj且Aj?Ai，则称M为集合A的一个K族. 定理：设M为n阶集合A的K族中阶数最高者，则Card(M)?Cn[]2n.

上述两个定理的证明有一定的麻烦程度，我们将其放在习题中，请读者自己完成其证明过程. 本讲的内容没有因定的方法，难度也较大，有些问题甚至就是一些数学专业论文中的一些结果或著名的定理，初学者若感到较为困难，可以耐心地多看几遍，多做几遍本讲中的例题与习题就会有所收获.

【典例精析】

【例1】（第43届美国中学数学竞赛）设S为集合{1,2,?,50}的子集，并且S中任意两个元素之和不能被7整除，那么S中元素最多有多少个？

〖分析〗对于两个不同的自然数m,n，m?n不被7整除也就是m?n被7除的余数不为0.我们将集合{1,2,?,50}按照其中元素被7除所得的余数相同与否进行归类，余数相同的组成一个集合，这样可得到7个子集.然后从这7个子集中适当地抽取满足题意的元素组成集合S即可.

【解法一】将集合{1,2,?,50}中的元素按被7除所得的余数相同分为7个子集，即：

A1?{1,8,15,22,29,36,43,50}；A2?{2,9,16,23,30,37,44}；A3?{3,10,17,24,31,38,45}；

A4?{4,11,18,25,32,39,46}；A5?{5,12,19,26,33,40,47}；A6?{6,13,20,27,34,41,48}；

A0?{7,14,21,28,35,42,49}.

可知S最多包含A0的一个元素，而如果S包含其它任何一个子集中一个元素时，则它可以包含这个子集中的所有元素；另外，S不有同时包含A1,A6中的元素；同样，S不能同时包含A2,A5和A3,A4中的元素.故S中的元素最多有1+8+7+7=23个. 【解法二】将{1,2,?,50}按照模7分成7类：

31

高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编写

K1?{1,8,15,22,29,36,43,50}；K2?{2,9,16,23,30,37,44}；K3?{3,10,17,24,31,38,45}； K4?{4,11,18,25,32,39,46}；K5?{5,12,19,26,33,40,47}；K6?{6,13,20,27,34,41,48}；

K0?{7,14,21,28,35,42,49}.

下面证明S?K1?K2?K3?{7}为满足要求的元素最多的集合. 首先对a,b?S,a?b有3种可能：

（1）a,b?Ki(1?i?3)，则a?b?2i(mod7)，则a?b不能被7整除；

（2）a?Ki,b?Kj(1?i?j?3)，则a?b?i?j(mod7)，则a?b不能被7整除； （3）a?Ki,b?7(1?i?3)，则a?b?i(mod7)，则a?b不能被7整除. 综上知，S中任何两个元素之和不能被7整除.

其次证明，若S中添加1个元素c，则必存在S中的一个元素与c的和能被7整除. 添加的c有4种可能：

（1）c?K4，则c与K3中的元素之和能被7整除； （2）c?K5，则c与K2中的元素之和能被7整除； （3）c?K6，则c与K1中的元素之和能被7整除； （4）c?K0，则c与7的和能被7整除.

综上知，S中的元素不能再添加.所以S中元素数目的最大值为：

Card(S)?Crad(K1)?Card(K2)?Card(K3)?1?23.

〖说明〗本题实际上是集合的划分问题，从以上的解答过程可以看出，利用余数构造集合的划分是解决本题的关键，也是解决集合问题的一种常用的手段. 解法二中，首先按模7的剩余类对集合{1,2,?,50}中的元素进行分类的想法是自然的.后面的解答中又进行了两次分类，但是这两个分类的理由已经蕴涵中最初的分类之中了.

【例2】对于一个由非负整数组成的集合S，定义rs(n)为满足条件的有序对(s1,s2)的对数：

s1?S,s2?S,s1?s2且s1?s2?n.问：是否能将非负整数集分划为两个集合A和B，使得

对任意n，均有rA(n)?rB(n)?

〖分析〗整数有多种表示形式，其中二进制表示的每位数字只有0和1这两种选择.由于是将S分划为两个集合A、B，对每个因定的n，满足s1?s2?n的非负整数对(s1,s2)是有限

32

高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编写

的，用二进制来讨论(s1,s2)在A和B中的分配情况似乎较有利.

【解】存在上述分划.将所有二进制下数码1出现偶数个的非负整数归入集合A，其余的非负整数归入B，则A、B是非负整数N的分划.

注意到，对A中满足a1?a2?n,a1?a2,a1,a2?A的数对(a1,a2)，由于a1?a2，因此在二进制表示下a1与a2在该位上的数码，分别得到b1,b2，则b1,b2?B且因此rA(n)?rB(n). b1?b2,b1?b2?n.这个将(a1,a2)对应到(b1,b2)的映射是一一对应的，

〖说明〗本题中构造一一映射成为求解的关键，这个构造使得我们将要求证的问题简单地转

化成了二进制下的数码个数问题，这种方法在涉及到集合所有子集问题中很常见.

}的两个子集，满足A【例3】（2007年全国高中数学联赛）已知A与B是集合{1,2,?,100与B的元素个数相同，且A?B为空集，若n?A时总有2n?2?B，则A?B的元素个数最多为（ ）

A．62 B．66 C．68 D．74

【解】先证Crad(A?B)?66，只须证Crad(A)?33，为此只须证若A是{1,2,?,49}的任一个34元子集，则必存在n?A，使得2n?2?A，证明如下： 将{1,2,?,49}分成如下33个集合：

{1,4},{3,8},{5,12},?,{23,48}共12个； {2,6},{10,22},{14,30},{18,38}共4个； {25},{27},{29},?,{49}共13个； {26},{34},{42},{46}共4个.

由于A是{1,2,?,49}的34元子集，从而由抽屉原理可知上述33个集合中至少有一个2元子集中的数均属于A，即存在n?A，使得2n?2?A.

如取A?{1,3,5,?,23,2,10,14,18,25,27,29,?,49,26,34,42,46}，B?{2n?2|n?A}，则

A,B满足题设条件Crad(A?B)?66.

〖说明〗在我们的经验中，有些数学问题涉及的对象较为复杂，统一地解决有困难，于是就将这些对象分成“不重不漏”的若干类，然后再逐类的解决，这就是分类解决问题的方法.这种方法在竞赛中是常用的.

}，A?M且当x?A时15x?A，【例4】（1995年全国高中数学联赛）设M?{1,2,?1995求Card(A)的最大值.

〖分析〗???133,?当k?9,10,11,?,133时，k与15k不能同时在A??13??1995?.只需再构造一个集合A，使得Card(A)?1870即可. 中.Card(A)?1995?125?1870

33

高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编写

,?,133时，k与15k不能同时在A中.故至少有133-8=125个数【解】由题设当k?9,10,11. 不在集合A中，即Card(A)?1995?125?1870,?,1995}满足题意，此时另一方面，M的子集A可取{1,2,?,8}?{134,135Card(A)?1870.故Card(A)的最大值为1870.

〖说明〗本题是要求满足一定条件的某个集合的子集的元素个数的最大值.先证明这个子集

的元素个数不大于某个常数，然后再构造一个集合，它的元素个数正好是这个常数，此时这个常数就是我们所要求的最大值. 本题解答中得到x与15x(x?9,10,?,35)这两个数中至少有一个不属于A是非常巧妙的一步，便得求解过程简单明了解.

【例5】把2个元素的集合分为若干个两两不交的子集，按照下述规则将某一个子集中某些元素挪到另一个子集：从前一子集挪到后一子集的元素个数等于后一子集的元素个数（前一子集的元素个数应不小于后一子集的元素个数），证明：可以经过有限次挪动，使得到的子集与原集合相重合.

〖分析〗首先考虑到2是一个很特殊的数，其次我们发现若两个集合的元素个数除以2的若干次幂后若为奇数，那么，它们之间挪后就应为偶数这一事实，若还不能想到解答就试一下n?2,n?3时的情况，相信解答就不会难找到了.

【证明】考虑含奇数个元素的子集（如果有这样的子集），因为所有子集所含元素的个数总和是偶数，所以具有奇数个元素的子集个数也是偶数，任意将所有含有奇数个元素的子集配成对，对每对子集按题目要求的规则移动：从较大的子集挪出一些元素，添加到较小的子集，挪出的元素个数为较小子集的元素个数，于是得到的所有子集的元素个数都是偶数，现在考虑元素个数不被4整除的子集，如果n?1，则总共有两个元素，它们在同一个子集，因此设n?2，因为子集的元素个数的总数被4整除，因此这样的子集的个数为偶数，任意将这样的子集配成对，对每一对子集施行满足题目要求的挪动，于是得到的每个子集数均可被4整除，依此做下去，最后得到的每个子集元素个数均可被2整除，也就是只能有一个子集，它的元素个数为2，证毕.

〖说明〗这道题的证明中隐含了一种单一变量在变化时变化方向相同这一性质，就这道题来说，一直在增加的就是各子集元素个数被2的多少次幂整除的这个幂次数，这是一大类问题，除了这种变化量，还要经常考虑变化中的不变量.

【例6】（2005年全国高中数学联赛）设r,s,t为整数，集合{a|a?2r?2s?2t,0?t?s?r}nnnn,13,14,?，则a36? 中的数由小到大组成数列{an}：7,112【解】∵r,s,t为整数且0?t?s?r，∴r最小取2，此时符合条件的数有C2?1

2r?3，s,t可在0,1,2中取，符合条件有的数有C3?3

34

本文来源：https://www.bwwdw.com/article/44dd.html