高中數(shù)學(xué)奧賽系列輔導(dǎo)資料：集合(2)

1、高中數(shù)學(xué)奧賽系列輔導(dǎo)資料：集合(2) 集合(二) 【經(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ù)以上中每一個(gè) 的元素，證明：存在子集，它至多含5個(gè)元素，并且和集合 集合至少有一個(gè)公共元。 分析：我們知道，這種題目并沒(méi)有什么特別好的辦法，只能一個(gè)一個(gè)把這5個(gè)元素找出來(lái)，我們還是可以先將題目

2、簡(jiǎn)化成簡(jiǎn)單形式，看是否方便理解一些，但這里我們就不這么做了。 證明：設(shè)集合 中元素個(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è)公共元素就可以了，于是，求得集合

3、可能小于5），它們構(gòu)成集合素。 說(shuō)明：這道題目當(dāng)和均較小時(shí)也就可以作為小學(xué)生競(jìng)賽題，而數(shù)目增大以后卻成為 的至多5個(gè)元素（在上述過(guò)程中所取的元素可能重復(fù)，所以，而子集 ， ， 中每一個(gè)都至少含有它的一個(gè)元 了英國(guó)高中競(jìng)賽題目，假設(shè)我們?cè)诜治鲚^小的數(shù)時(shí)可以把規(guī)律找出，而這是很簡(jiǎn)單的，那么整道題目也就迎刃而解了，這就告l 有462把鎖。那么再對(duì)462把鎖進(jìn)行構(gòu)造就可以了。 解：設(shè)加把鎖，又設(shè) ， ， 是這11個(gè)人各自打不開(kāi)的鎖的集合，從11個(gè) 把，為分配好各鎖的鑰匙，設(shè)鎖號(hào) 集合中任選5個(gè)并集都不相同，故至少應(yīng)有鎖 依次為1號(hào)，2號(hào)，462號(hào)，同時(shí)把11個(gè)人任取5個(gè)的組合也編上1至462號(hào)，然后把

4、鎖和組合一一對(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ù)（前一子集的元素個(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í)，若還不能

5、想到解答就試一下 ， 時(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ù)都是偶數(shù)，現(xiàn)在考慮元素個(gè)數(shù)不被4整除的子集，如果因此設(shè) ，則總共有兩個(gè)元素，它們?cè)谕粋€(gè)子集， ，因?yàn)樽蛹脑貍€(gè)數(shù)的總數(shù)被4整除，因此這樣的子集的個(gè)數(shù)為偶數(shù)，任意 將這樣的子集配成對(duì)，對(duì)每一對(duì)子集施行滿足題目要求的挪動(dòng)，于是得到的每個(gè)子

6、集數(shù)均可被4整除，依此做下去，最后得到的每個(gè)子集元素個(gè)數(shù)均可被子集，它的元素個(gè)數(shù)為 ，證畢。 整除，也就是只能有一個(gè) 說(shuō)明：這道題的證明中隱含了一種單一變量在變化時(shí)變化方向相同這一性質(zhì)，就這道題來(lái)說(shuō)，一直在增加的就是各子集元素個(gè)數(shù)被2的多少次冪整除的這個(gè)冪次數(shù)，這是一大類(lèi)問(wèn)題，除了這種變化量，還要經(jīng)?？紤]變化中的不變量。 例4：給定1978個(gè)集合，每個(gè)集合都含有40個(gè)元素，已知其中任意兩個(gè)集合都恰有一個(gè)公共元，證明：存在一個(gè)元素，它屬于全部集合。 分析：我們可以先去找一個(gè)屬于很多個(gè)集合的元素，最好它就是我們要找的那一個(gè)。 證明：考慮給定的1978個(gè)集合中任意一個(gè)集合此，存在集合，而集合合 ，

7、，它和其它1977個(gè)集合都相交，因 中每個(gè)元素至多屬于49個(gè) ，使得它至少屬于其中50個(gè)集合，否則，集合恰有40個(gè)元素，所以除 外至多有1960個(gè)集合，不可能，因此設(shè)屬于集 ，下面證明它屬于給定的1978個(gè)集合中任一個(gè)。 ， ， 的任一個(gè)集合 ，設(shè) ，則 與 ， ， ， 每 對(duì)于除了 一個(gè)都有至少一個(gè)元素的交，它們都與不同，那么，就至少要有51個(gè)元素，不可能， 因此屬于每個(gè)集合。 說(shuō)明：這種題目最怕把它想難了，想行太難了，就會(huì)覺(jué)得無(wú)從下手，做數(shù)學(xué)競(jìng)賽題就需要一方面在做題之前選好方向，另一方面就是大膽嘗試去做。 例5：在一個(gè)含10個(gè)元素的集合有 的若干非空子集中，任意兩個(gè)不同的子集的交集含 中元

8、素的數(shù)目不多于2，這樣的子集合有多少個(gè)。 分析： 的一元素子集和二元素子集顯然都是滿足條件的，三元子集呢？如果有一個(gè) 多于3元的子集，總可以把它拆為三元子集的并，增加子集的數(shù)量而不影響性質(zhì)，而恰恰把全部三元子集都選上也符合題目要求。 解： 中的單元素子集共10個(gè)，這10個(gè)都符合題目的要求。 個(gè)，它們也符合要求。 個(gè)，也符合要求。 個(gè)子集滿足條件。 ， 中的含兩個(gè)元素的集合共中含三個(gè)元素的集合共這表明， 的子集合中，至少有 另一方面，假設(shè)其中 ，取 的非空子集有多于175個(gè)具有題目中的條件。設(shè)這個(gè)子集族為 則 中必存在含有 中的元素?cái)?shù)超過(guò)3的集合，設(shè)， ，這表明 ，作差集，顯然 與不能同為子集族

9、 中的成員，用 ，容易看到被含 替換，得到另一個(gè)子集族： ，所替 也符合題目中的條件，并且 的另一個(gè) 的子集 經(jīng)過(guò)這樣的替換后，代，因?yàn)?中某個(gè)元素中元素少于 ，中的元素?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è)元素組成的集合中取 個(gè)不同的三元子集。證明：其中必有兩個(gè)，它們 恰有一個(gè)公共元。 分析：證明恰有一個(gè)

10、公共元也許挺難。那么證只有兩個(gè)或零個(gè)公共元不可能是否可行呢？如果具有兩個(gè)公共元的集合 與 表示為 、那么有傳遞性。是否有用呢？ 與， 證明：設(shè)結(jié)論不真。則所給的3元子集要么不交，要么恰有兩個(gè)公共元，如果子集恰有兩個(gè)公共元，則記則 。設(shè) 是三個(gè)子集。可以證明如果 ， ，于是所有給定的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)中至多有4個(gè)子集。 考慮（3） 設(shè) ， ，則還有一個(gè)，由，由

11、 ， ， ， ，有 。因此對(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分（2），10000000分（2），100000000分