集合講義(二)

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

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

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

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

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

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

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

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

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

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

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