集合的構造與分拆

在數學中，集合是一個沒有嚴格定義的概念；隻要求可以分辨一個元素是否在集合中、重複出現的元素隻按一個計算。集合中的元素沒有順序，它的基數（元素的個數）可以有限、可數無窮、或者連續。從一些已有的元素{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的倍數。這可以通過解不定方程求出。如果要讓乘積相等，必須先把每個數作質因數分解，再看看所有質因數能否平均分配，還要猜猜試試才能得到答案。