集合講義(二)

1、集合(二)【經(jīng)驗談】集合是數(shù)學(xué)中的重要基礎(chǔ)知識，不論是高考還是數(shù)學(xué)競賽中都少不了它的一席之地。本文將幫助你徹底掌握集合知識。【內(nèi)容綜述】集合是組合數(shù)學(xué)的基礎(chǔ)，也是高中數(shù)學(xué)競賽中的重要組成部分。希望大家通過本講學(xué)習(xí)開拓思路，靈活解題，另外，要想解好集合題目，相關(guān)知識也很重要?！纠}分析】例1：設(shè)，是有限集合的50個子集，每個子集都含有的半數(shù)以上的元素，證明：存在子集，它至多含5個元素，并且和集合，中每一個集合至少有一個公共元。分析：我們知道，這種題目并沒有什么特別好的辦法，只能一個一個把這5個元素找出來，我們還是可以先將題目簡化成簡單形式，看是否方便理解一些，但這里我們就不這么做了。證明：設(shè)集合

2、中元素個數(shù)為n，子集，中每一個都含以上的元素，即所有這些子集的元素個數(shù)大于 由抽屜原理，必有集合的元素，它至少屬于26個子集，同理可證，對每個，在子集，中至少有個子集，它們具有公共元素，在集合中取出一個元素，它至少屬于26個子集，并作為集合 中五個元素之一，去掉包含這個元素的26個子集，在余下24個子集中取一個元素，它至少屬于13個子集，去掉這13個子集，在余下的11個子集中取一個元素，它至少屬于6個子集，在余下5個子集中取一個元素，它屬于3個子集，剩下兩個子集再取一個公共元素就可以了，于是，求得集合的至多5個元素（在上述過程中所取的元素可能重復(fù)，所以可能小于5），它們構(gòu)成集合，而子集，中每一

3、個都至少含有它的一個元素。說明：這道題目當(dāng)和均較小時也就可以作為小學(xué)生競賽題，而數(shù)目增大以后卻成為了英國高中競賽題目，假設(shè)我們在分析較小的數(shù)時可以把規(guī)律找出，而這是很簡單的，那么整道題目也就迎刃而解了，這就告訴我們，做這類整數(shù)問題時，應(yīng)該時時刻刻想到先將數(shù)目變小看看規(guī)律，然后再做題目本身。 例2：有11人管理一個保險柜，可以在柜上加若干把鎖，每把鎖可以有若干把鑰匙，問：如何加鎖和如何分配各鎖的鑰匙，才能使任何6個人可以把保險柜打開，但任意5個人卻不能。分析：我們反過來想一下，假設(shè)，是11個人打不開的鎖的集合，從11個人中任意找5個人的可能性有種情況。要想把它們都區(qū)別開，也就是說至少要有462把

4、鎖。那么再對462把鎖進(jìn)行構(gòu)造就可以了。解：設(shè)加把鎖，又設(shè)，是這11個人各自打不開的鎖的集合，從11個集合中任選5個并集都不相同，故至少應(yīng)有鎖把，為分配好各鎖的鑰匙，設(shè)鎖號依次為1號，2號，462號，同時把11個人任取5個的組合也編上1至462號，然后把鎖和組合一一對應(yīng)起來，給每個人發(fā)鑰匙時，他所在的組的號的鑰匙不給他，其他鑰匙都給他，這時就滿足題設(shè)了。說明：這個構(gòu)造難度很大，這主要原因還是因數(shù)目太大了，也應(yīng)該先從小的數(shù)目做起，最后回到原題。例3：把個元素的集合分為若干個兩兩不交的子集，按照下述規(guī)則將某一個子集中某些元素挪到另一個子集：從前一子集挪到后一子集的元素個數(shù)等于后一子集的元素個數(shù)（前

5、一子集的元素個數(shù)應(yīng)不小于后一子集的元素個數(shù)），證明：可以經(jīng)過有限次挪動，使得到的子集與原集合相重合。分析：首先考慮到是一個很特殊的數(shù)，其次我們發(fā)現(xiàn)若兩個集合的元素個數(shù)除以2的若干次冪后若為奇數(shù)，那么，它們之間挪后就應(yīng)為偶數(shù)這一事實，若還不能想到解答就試一下，時的情況，相信解答就不會難找到了。證明：考慮含奇數(shù)個元素的子集（如果有這樣的子集），因為所有子集所含元素的個數(shù)總和是偶數(shù)，所以具有奇數(shù)個元素的子集個數(shù)也是偶數(shù)，任意將所有含有奇數(shù)個元素的子集配成對，對每對子集按題目要求的規(guī)則移動：從較大的子集挪出一些元素，添加到較小的子集，挪出的元素個數(shù)為較小子集的元素個數(shù)，于是得到的所有子集的元素個數(shù)都是

6、偶數(shù)，現(xiàn)在考慮元素個數(shù)不被4整除的子集，如果，則總共有兩個元素，它們在同一個子集，因此設(shè)，因為子集的元素個數(shù)的總數(shù)被4整除，因此這樣的子集的個數(shù)為偶數(shù)，任意將這樣的子集配成對，對每一對子集施行滿足題目要求的挪動，于是得到的每個子集數(shù)均可被4整除，依此做下去，最后得到的每個子集元素個數(shù)均可被整除，也就是只能有一個子集，它的元素個數(shù)為，證畢。說明：這道題的證明中隱含了一種單一變量在變化時變化方向相同這一性質(zhì)，就這道題來說，一直在增加的就是各子集元素個數(shù)被2的多少次冪整除的這個冪次數(shù)，這是一大類問題，除了這種變化量，還要經(jīng)?？紤]變化中的不變量。例4：給定1978個集合，每個集合都含有40個元素，已知

7、其中任意兩個集合都恰有一個公共元，證明：存在一個元素，它屬于全部集合。分析：我們可以先去找一個屬于很多個集合的元素，最好它就是我們要找的那一個。證明：考慮給定的1978個集合中任意一個集合，它和其它1977個集合都相交，因此，存在，使得它至少屬于其中50個集合，否則，集合中每個元素至多屬于49個集合，而集合恰有40個元素，所以除外至多有1960個集合，不可能，因此設(shè)屬于集合，下面證明它屬于給定的1978個集合中任一個。對于除了，的任一個集合，設(shè)，則與，每一個都有至少一個元素的交，它們都與不同，那么，就至少要有51個元素，不可能，因此屬于每個集合。說明：這種題目最怕把它想難了，想行太難了，就會覺

8、得無從下手，做數(shù)學(xué)競賽題就需要一方面在做題之前選好方向，另一方面就是大膽嘗試去做。例5：在一個含10個元素的集合的若干非空子集中，任意兩個不同的子集的交集含有中元素的數(shù)目不多于2，這樣的子集合有多少個。分析：的一元素子集和二元素子集顯然都是滿足條件的，三元子集呢？如果有一個多于3元的子集，總可以把它拆為三元子集的并，增加子集的數(shù)量而不影響性質(zhì)，而恰恰把全部三元子集都選上也符合題目要求。解：中的單元素子集共10個，這10個都符合題目的要求。中的含兩個元素的集合共個，它們也符合要求。中含三個元素的集合共個，也符合要求。這表明，的子集合中，至少有個子集滿足條件。另一方面，假設(shè)的非空子集有多于175個

9、具有題目中的條件。設(shè)這個子集族為，其中 則中必存在含有中的元素數(shù)超過3的集合，設(shè)，取，作差集，顯然，這表明與不能同為子集族中的成員，用替換，得到另一個子集族： ，容易看到也符合題目中的條件，并且，經(jīng)過這樣的替換后，中某個元素被含中元素少于的另一個的子集所替代，因為，中的元素數(shù)目有限。所以有限次替代后，總可使新的子集族中各元素含有中的元素數(shù)目不超過3，這就看出與矛盾，這表明不存在符合題目條件的多于175個的的子集形成的子集族，即這樣的子集族恰有175個。說明：這道題是一類典型問題的代表，這種問題的解法就是先構(gòu)造，然后證明更多或更少不行。在證明過程中盡量把它往構(gòu)造出來的方向化規(guī)。例6：在個元素組成

10、的集合中取個不同的三元子集。證明：其中必有兩個，它們恰有一個公共元。分析：證明恰有一個公共元也許挺難。那么證只有兩個或零個公共元不可能是否可行呢？如果具有兩個公共元的集合與表示為、那么有傳遞性。是否有用呢？證明：設(shè)結(jié)論不真。則所給的3元子集要么不交，要么恰有兩個公共元，如果子集與恰有兩個公共元，則記。設(shè)是三個子集?？梢宰C明如果，則，于是所有給定的3元子集可以分類，使得同一類中任意兩個不同子集都恰有兩個公共元。而不同類的子集不相交。于是對每個子集類，有三種可能：（1）恰含3個元素的類。（2）恰含4個元素的類。（3）至少含5個元素的類。在（1）下，3元子集類恰由一個3元子集組成。在（2）下，子集類

11、中至多有4個子集。考慮（3） 設(shè)，則還有一個，由，有。因此對子集類中任意子集，由，它包含與，于是類中子集個數(shù)比類中元素個數(shù)少2，于是，每個類中子集個數(shù)不超過元素個數(shù)，但是題中條件子集數(shù)大于元素個數(shù)，矛盾！說明：此題為1979年美國競賽題。題目難度較大，應(yīng)該說是應(yīng)用了高等代數(shù)中的一些思想。1求的所有子集元素的和之和。2小明去買東西，現(xiàn)在他有10元，希望分成10包，使在商店內(nèi)他能買起的東西都可由包中的錢直接支付。3能否把整數(shù)集合分成3個子集，使得對每個整數(shù)，都屬于不同的集合。410名學(xué)生按下面的規(guī)則組成運(yùn)動隊，規(guī)則是：每人可報名參加任何一個運(yùn)動隊；每個運(yùn)動隊都不能完全包含于或重合于另一個運(yùn)動隊。問：最多幾個隊？每隊分別多少人？參考答案1我們可以發(fā)現(xiàn)對每個數(shù)，它出現(xiàn)在個子集之中，因此所有子集中的的和為，那么全部元素在全部子集之中的和為。2利用二進(jìn)制來考慮此題，小明的前9包分別有錢 1分（2），10分（2），100分（2），1000分（2），10000分（2），100000分（2），1000000分