集合的妙用

周粟，武汉英中在校生，爱好编程与算法。

身边有很多同学告诉我，他们觉得 集合 的知识很少在解题时被运用到。然而 ， 集合论 是离散数学中十分重要的一块。这次就给大家看看 集合 的一些妙用。

先说说有趣的“ 罗素悖论 ”( 悖论(paradox)来自希腊语“para+dokein”，意思是“多想一想”。这个词的意义比较丰富.它包括一切与人的直觉和日常经验相矛盾的数学结论.那些结论会使我们惊异无比.悖论是自相矛盾的命题 ) 。

一位理发师称道 ：“我为所有不给自己理发的人理发，但我也只为他们理发。”另外一个人问道：“那您的头发由谁来理呢？”理发师顿时哑口无言了。第一眼可能发现不了这个故事的有趣之处，那我们来分析一波吧。如果理发师不给自己理发，他就要给自己理；如果他给自己理发，就说明他不只给不自己理发的人理发。所以不管怎样，理发师所说的情况不可能发生。也就是这一个小小的悖论，造成了第三次数学危机。

理发师悖论可以表达成 集合论 的 形式，就是 罗素悖论 。

R={x | x不属于x }，然后现在问R是否属于R。如果R不属于R，那么根据定义，R属于R；如果R属于R，那么根据定义，R不属于R。

刚刚考完的 2017 年 AMC12 中有这样一道题：

求出所有这样正整数的个数。从左到右，它的各位数字递增或递减。

建议大家先自己思考思考再往下看，这道题在考场上还难住了不少同学。但实际上，这是一道非常简单的题。首先，这样的整数个位上肯定不会有重复的数字，所以我们设 集合

A={1,2,3,4,5,6,7,8,9,0} ，

B={1,2,3,4,5,6,7,8,9} 。

那么，选择 A 的任何一个非空 子集 ，然后将子集的所有元素从大到小排列，一定是个满足条件的整数；选择 B 的任何一个非空子集，将子集的所有元素从小到大排列，一定也是一个满足条件的整数。所以我们要求的就是 A 和 B 的子集个数。 A 有 10 个元素，每个元素可能存在于一个子集，也可能不存在，所以不同的子集个数是 2^10 ，非空的有 2^10-1 个；同理， B 的非空子集有 2^9-1 个。由于题目要求正整数，所以 A 的一个子集 {0} 不能取；另外 A 的非空子集与 B 有交集，也就是 {1},{2}, ……， {9} 。所以总个数 =(2^10-1)+(2^9-1)-1-9=1524 个 。

还有一道相似的题， 有两条直线，一条上有 5 个点，另一条上有 6 个点，将第一条直线上的所有点与第二条直线上的所有点相连。那么这些连线交点一共有多少个？（不考虑有两个交点重合的情况）

找不到合适的方法，这也是一道很难的题。能够理解连接任意两对来自两条直线上的点都能产生一个交点（如下图），很快答案就出来了。也就是说，从第一条直线的五个点的集合中挑出两个不同的元素，再从另一条直线的六个点的集合中挑出两个不同的元素，对应一个交点。所以个数 =C(6,2)*C(5,2)=150 个交点。

再例如 费马小定理 ： p 是质数，且不整除