高级中学数学竞赛讲义0集合与简单逻辑(3)

-*

【解】（1）集合I可划分为三个不相交的子集；A\B，B\A，中的每个元素恰属于其中一个子集，10个元素共有310种可能，每一种可能确定一个满足条件的集合对，所以集合对有310个。

（2）I的子集分三类：空集，非空真子集，集合I本身，确定一个子集分十步，第一步，1或者属于该子集或者不属于，有两种；第二步，2也有两种，…，第10步，0也有两种，由乘法原理，子集共有个，非空真子集有1022个。

5．配对方法。

例5 给定集合的个子集：，满足任何两个子集的交集非空，并且再添加I的任何一个其他子集后将不再具有该性质，求的值。

【解】将I的子集作如下配对：每个子集和它的补集为一对，共得对，每一对不能同在这个子集中，因此，；其次，每一对中必有一个在这个子集中出现，否则，若有一对子集未出现，设为C 1A与A，并设，则，从而可以在个子集中再添加，与已知矛盾，所以。综上，。

6．竞赛常用方法与例题。

定理4 容斥原理: 用表示集合A的元素个数，则

，此结论可以推广到个集合的情况，即

定义8 集合的划分：若，且，则这些子集的全集叫I的一个-划分。

定理5 最小数原理：自然数集的任何非空子集必有最小数。

定理6 抽屉原理：将个元素放入个抽屉，必有一个抽屉放有不少于个元素，也必有一个抽屉放有不多于个元素；将无穷多个元素放入个抽屉必有一个抽屉放有无穷多个元素。

例6 求1，2，3，…，100中不能被2，3，5整除的数的个数。

【解】记，

，由容斥原理，

，所以不能被2，3，5整除的数有

个。

例7 S是集合{1，2，…，2004}的子集，S中的任意两个数的差不等于4或7，问S中最多含有多少个元素？

【解】将任意连续的11个整数排成一圈如右图所示。由题目条件可知每相邻两个数至多有一个属