集合的构造与分拆

在数学中，集合是一个没有严格定义的概念；只要求可以分辨一个元素是否在集合中、重复出现的元素只按一个计算。集合中的元素没有顺序，它的基数（元素的个数）可以有限、可数无穷、或者连续。从一些已有的元素{a1, …an, …} 出发，我们有以下各种方法取构造集合：（1）用代数运算去生成新的元素及集合；（2）构造子集，甚至子集的子集；（3）作Descartes乘积；（4）按照等价关系构照商集。

USAMO 2004年有这么一道题：设a₁, . . . , a_n, 为整数，且最大公因数为1. 集合S按如下方式生成：(a) 对 i = 1, 2, …, n, a_i 属于 S. (b) 对 i, j = 1, . . . , n(可以相同), a_i - a_j 属于 S. (c) 对于任何整数x, y属于S, 如果 x + y 属于S, 则必有 x – y属于S. 那么，S就是所有整数的集合。由（b）可知，0在S中；由（c），-ai在S中；反复应用(b), (c)，a1, a2, …, an的任何整数组合都在S中。根据最大公因数为1，可知1在S中。

数字化地描述一个集合，可以采用特征函数；即f(A, x) = 1，若x在集合A中，否则，函数值为零；空集的特征函数恒为零。它具有以下性质，（1）f(A^B, x) = f(A, x)f(B, x),其中，A^B表示A和B的交集；（2）f(AUB, x) = f(A, x) + f(B, x) – f(A, x)f(B, x)，（3）f(A – B, x) = f(A, x)[1 – f(B, x)], A – B是差集，即从A中挖除B后所剩余的部分。

可以让一个集合加、减、乘或除以一个数，也就是集合中的每个数都加、减、乘、除以这个数。例如，定义集合列如下：A(1) =空集 , B(1) = {0}, A(n+1)= 1 + B(n), B(n+1)= A(n)UB(n) – A(n) ^B(n), 对所有正整数n。通过观察、归纳可知，当n > 1时，B(2n) = 2B(n), A(2n-1) = 2A(n) – 1, B(2n)中都是偶数，A(2n-1)中都是奇数；以及B(2n-1)= 2B(n) U A(2n-1)，A(2n) = 1 + B(2n-) = {1 + 2B(n)}U{1 + A(2n-1)}，为两个不相交的集合的并集，其中一个是奇整数，另一个是偶整数。还有0不在A(n)中，1在A(2n+1) 中。

容纳一个集合的全部信息，可以用生成函数。定义A(n)的生成函数为f(n, x) = sigma(x^k: k 在A(n)中)，规定空和为零：f(1,x) = 0, f(2,x) = f(3,x) = x, f(4, x) = x^2 + x。B(n)的生成函数为g(n, x)，g(1,x) = 1, g(2,x) = 1, g(3,x) = 1 + x, g(2^k, x) = 1。当n>1时，g(2n, x) = g(n, x^2), f(2n-1,x) = f(n,x^2)/x，g(2n-1,x) = g(n,x^2) + f(2n-1,x), f(2n, x) = xg(2n-1, x)。这些递推函数方程的解，是一个挑战。

给定一个集合S，我们可以从它的幂集（所有子集的集合，包括空集）中，取出部分子集，以满足一定要求，形成所谓的集簇；比如，拓扑结构中的开集三公理。在一个Sperner簇中，任何一个子集都不能包含其它子集；在一个Helly簇中，任何不相交的子簇都有界。

考虑一个有限的Sperner簇F，设|S| = n。用a(k)表示F中，含有k个元素的子集个数。我们需要估计a(k)的值。在一个阶数为n的集合中，k元子集的个数为C(n, k)。如果a(0) =1, 即F含有空集，它就没有其它子集了。同样，如果a(n) = 1，则除了S外，F也没有其它元素了。这两种是平凡情形。下设a(0) = a(n) = 0；在F中取一个k元子集，把这k个元素排成一列；在尾随S中的其它n-k个元素，一共可以形成k!(n-k)!个排列；由于F的子集互不包含，这些排列各不相同；因此有，sigma{a(k)k!(n-k)!, k = 1, 2, …, n – 1} ≤ n!。

在所有的组合数C(n, k)中，最大的一个是C(n, fl(n/2))。在F中，如果它包含一个k元子集，它就不能再包含此子集的任何子集或者扩集；也就是说，其它n-k个元素要自成一体。因此，F的最大阶数就是C(n, fl(n/2))。

再探讨一下有限的Helly簇。设A =A1UA2U...UAn为一个有限集，记S = {A₁, A₂, …, A_n}. 如果(i) S中任何k个集合都有交集（非空），（ii）任何k+1个集合的交集都是空集，那么一定有，|A| ≥ C(n,k) 且 |A_i| ≤ |A| - C(n-1,k).

还可以对一个给定的集合进行拆分。设S是一个阶为n的有限集S，可以把其元素编号，不妨就记下其标号，设为S = {1, 2, …, n}。它共有2^n个子集，包括空集。我们通常被要求，把S拆分为一些不相交的子集的并集。拆分的方式是数之不尽的；最常见的是，按照模m的同余类拆分。例如（Euclid竞赛中的一个问题），给定3k个连续整数，要求所有这种三元子集的个数，使得三个数之和为3的倍数；可以把按照模3的同余类，分成3个子集，每个子集含有k个数。为了三数之和被3整除，可以在同一个子集中取三个不同的数，也可以在在每个子集中各取一个数。

还有IMO 1995年的一个问题：给定质数p > 2，要求集合{1，2，…, 2p} 的这种p元子集的个数，使其中各数之和能够被p整除。把这2p个数按照模p分成p个同余类Ck = {k, k + p}, k = 1, 2, …, p。如果每个类中取一个构成一个p元子集，各数之和可以被p整除，这样的子集共有2^p个。还可以在Cp中取一个数，其它p-1类配成对：Ck与C(p-k)，k = 1, …, (p-1)/2 = q；可以某一对中的四个数全取，另一对不取，其它q-2对或2q – 4类中各取一数，共有2^(p-3)C(q,2)种方式。也可以两对全取、两对不取，其它q-4对各取一数；如此递推，最后把总数相加。

对于以下问题：求集合{1，2，…, 2000}的子集个数，使其中各数之和能被5除尽，可以用生成函数的方法。一个子集 {a1, a2,…, ak} 可与一项X^(a1 + a2 + …+ak)对应；多项式(1+x)(1+x^2)…(1+x^2000) 的展开式中，x^(5j)的系数就表示各数之和等于5j的子集的个数。可以用5次单位根求出这些系数之和。

也可以按照整数元素的前几位数字分类。例如AIME 2004的一道题：给定n= 2004个2的幂S = {1, 2, 4, …, 2^(n-1)}，假设2^(n-1)有k=604位数字（在10进制下），且首位数字为1。用S1表示所有以1开头的幂次；此集中的一个数如果乘以2（2^(n-1)除外），就会以2, 或3开头；这些数构成子集S2U{2^n}; 它与S1一一对应。S1中的一个数如果除以2（1除外），就会以5, 6, 7, 8, 或9开头，这些数字构成子集S5U{5}；此集也与S1一一对应，从而具有一样的阶数。剩下就是以4开头的那些幂次了，这些数构成子集S4;它的阶数可以用n – 3|S1|+ 2求出，而|S1| = k,因为给定一个位数，恰有一个2的幂次以1开头。

第三种拆分方式是，每个子集具有相同的和（或积或平反和等），至少也得让其和（积）尽量靠近。在Euclid 2003年的一道题中，要求把S = {1, 2, …, n} 写成3个不相交子集A，B，C的并，使得每个子集的元素之和相等（n(n+1)/2必须被3除尽），而且C包括所有3的倍数，A只含奇数，B只含偶数。即C = {3, 6, …, 3fl(n/3)}, A，B中没有3的倍数。这可以通过解不定方程求出。如果要让乘积相等，必须先把每个数作质因数分解，再看看所有质因数能否平均分配，还要猜猜试试才能得到答案。