高中數(shù)學競賽講義-容斥原理

1、高考資源網(wǎng)（） 您身邊的高考專家§24容斥原理相對補集：稱屬于A而不屬于B的全體元素，組成的集合為B對A的相對補集或差集，記作A-B。容斥原理：以表示集合A中元素的數(shù)目，我們有，其中為n個集合稱為A的階。n階集合的全部子集數(shù)目為。例題講解1對集合1，2，n及其每一個非空了集，定義一個唯一確定的“交替和”如下：按照遞減的次序重新排列該子集，然后交替地減或加后繼的數(shù)所得的結果，例如，集合的“交替和”是9-6+4-2+1=6.的“交替和”是6-5=1，的交替和是2。那么，對于n=7。求所有子集的“交替和”的總和。2某班對數(shù)學、物理、化學三科總評成績統(tǒng)計如下：優(yōu)秀的人數(shù)：數(shù)學21個，物理19

2、個，化學20個，數(shù)學物理都優(yōu)秀9人，物理化學都優(yōu)秀7人?；瘜W數(shù)學都優(yōu)秀8人。這個班有5人任何一科都不優(yōu)秀。那么確定這個班人數(shù)以及僅有一科優(yōu)秀的三科分別有多少個人。3計算不超過120的合數(shù)的個數(shù)41992位科學家，每人至少與1329人合作過，那么，其中一定有四位數(shù)學家兩兩合作過。5把個元素的集合分為若干個兩兩不交的子集，按照下述規(guī)則將某一個子集中某些元素挪到另一個子集：從前一子集挪到后一子集的元素個數(shù)等于后一子集的元素個數(shù)（前一子集的元素個數(shù)應不小于后一子集的元素個數(shù)），證明：可以經(jīng)過有限次挪動，使得到的子集與原集合相重合。6給定1978個集合，每個集合都含有40個元素，已知其中任意兩個集合都恰

3、有一個公共元，證明：存在一個元素，它屬于全部集合。7在個元素組成的集合中取個不同的三元子集。證明：其中必有兩個，它們恰有一個公共元。例題答案：1分析；n=7時，集合7，6，5，4，3，2，1的非空子集有個，雖然子集數(shù)目有限，但是逐一計算各自的“交替和”再相加，計算量仍然巨大，但是，根據(jù)“交替和”的定義，容易看到集合1，2，3，4，5，6，7與1，2，3，4，5，6的“交替和”是7；可以想到把一個不含7的集和A與的“交替和”之和應為7。那么，我們也就很容易解決這個問題了。解：集合1，2，3，4，5，6，7的子集中，除去7外還有個非空子集合，把這個非空子集兩兩結組后分別計算每一組中“交替和”之和，

4、結組原則是設這是把結合為一組，顯然，每組中，“交替和”之和應為7，共有組.所以,所有“交替和”之和應該為。說明：我們在這道題的證明過程中用了這類題目最典型的解法。就是“對應”的方法，“對應”的方法在解決相等的問題中應用得更多。2分析：自然地設A=數(shù)學總評優(yōu)秀的人B=物理總評優(yōu)秀的人C=化學總評優(yōu)秀的人則已知|A|=21 |B|=19 |C|=20這表明全班人數(shù)在41至48人之間。僅數(shù)學優(yōu)秀的人數(shù)是可見僅數(shù)學優(yōu)秀的人數(shù)在4至11人之間。同理僅物理優(yōu)秀的人數(shù)在3至10人之間。同理僅化學優(yōu)秀的人數(shù)在5至12人之間。解：（略）。說明：先將具體的實際生活中的問題數(shù)學化，然后根據(jù)數(shù)學理論來解決這個問題不僅

5、是競賽中常見情況，也是在未來學習中數(shù)學真正有用的地方。3分析1：用“篩法”找出不超過120的質數(shù)(素數(shù))，計算它們的個數(shù)，從120中去掉質數(shù)，再去掉“1”，剩下的即是合數(shù)。解法1：120以內： 既不是素數(shù)又不是合數(shù)的數(shù)有一個，即“1”； 素數(shù)有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97、101、103、107、109、113、共30個。所以不超過120的合數(shù)有12013089(個)(附：篩法：從小到大按順序寫出1120的所有自然數(shù)：先劃掉1，保留2，然后劃掉2的所有倍數(shù)4,6，120等；保留3，再

6、劃掉所有3的倍數(shù)6,9117、120等；保留5，再劃掉5的所有倍數(shù)10,15，120；保留7，再劃掉7的所有倍數(shù)，這樣，上面數(shù)表中剩下的數(shù)就是120以內的所有素數(shù)，這種方法是最古老的尋找素數(shù)的方法，叫做“埃斯托拉篩法”)說明：當n不很大時，計算1n中的合數(shù)的個數(shù)困難不大；但當n很大時，利用篩法就很困難、很費時了，必須另覓他途。分析2受解法1的啟發(fā)，如果能找出1n中質數(shù)的個數(shù)m，則n1m就是不超過n的合數(shù)的個數(shù)。由初等數(shù)論中定理：a是大于1的整數(shù)。如果所有不大于a的質數(shù)都不能整除a，那么a是質數(shù)。因為120<121112，120<11，所以不超過120的合數(shù)必是2或3或5或7的倍數(shù)，

7、所以只要分別計算出不超過120的2、3、5、7的倍數(shù)，再利用“容斥原理”即可。解法2：設S1a13120,2a；S2b1b120,3b；S3c13120,5c；S4=d1d120,7d，則有：card(S1)120/2=60，card(S2)120/340，card(S3)120/524，card(S4)120/717；(n表示n的整數(shù)部分，例如2,42，)card(S1S2)120/2×320，card(S1S3)120/2×512，card(S1S4)120/2×78，card(S2S3)120/3×58，card(S2S4)120/3×7

8、5，card(S3S4)120/5×73，card(S1S2S3)120/2×3×54，card(S1S2S4)120/2×3×72，card(S1S3S4)120/2×5×71，card(S2S3S4)120/3×5×71，card(S1S2S3S4)120/2×3×5×70card(S1S2S3S4)card(S1)card(S2)card(S3)card(S4)card(S1S2)card(S1S3)card(S1S4)card(S2S3)card(S2S4)card(

9、S3S4)card(S1S2S3)card(S1S2S4)card(S1S3S4)card(S2S3S4)card(S1S2S3S4)(60402417)-(20+12+8+8+5+3)+(4+2+1+1)-0141-568932，3，5，7是質數(shù)93489即不超過120的合數(shù)共有89個。4分析：在與一個人A合作的人中我們找到B。再說明一定有人與A和B都合作過為C。最后再說明有人與A、B、C都合作過為D，那么A、B、C、D就是找的人了。 證明：一個人A。不妨設B與之合作。那么。即C與A和B均合作過，分別表示與A、B合作過的人的集合。同樣地，。所以存在。則A、B、C、D就是所求，證畢。說明：把一

10、個普通的敘述性問題轉化為集合的語言描述的問題通常為解題的關鍵之處，也是同學們需加強的。5分析：首先考慮到是一個很特殊的數(shù)，其次我們發(fā)現(xiàn)若兩個集合的元素個數(shù)除以2的若干次冪后若為奇數(shù)，那么，它們之間挪后就應為偶數(shù)這一事實，若還不能想到解答就試一下，時的情況，相信解答就不會難找到了。證明：考慮含奇數(shù)個元素的子集（如果有這樣的子集），因為所有子集所含元素的個數(shù)總和是偶數(shù)，所以具有奇數(shù)個元素的子集個數(shù)也是偶數(shù)，任意將所有含有奇數(shù)個元素的子集配成對，對每對子集按題目要求的規(guī)則移動：從較大的子集挪出一些元素，添加到較小的子集，挪出的元素個數(shù)為較小子集的元素個數(shù)，于是得到的所有子集的元素個數(shù)都是偶數(shù)，現(xiàn)在考

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

12、那一個。證明：考慮給定的1978個集合中任意一個集合，它和其它1977個集合都相交，因此，存在，使得它至少屬于其中50個集合，否則，集合中每個元素至多屬于49個集合，而集合恰有40個元素，所以除外至多有1960個集合，不可能，因此設屬于集合，下面證明它屬于給定的1978個集合中任一個。對于除了，的任一個集合，設，則與，每一個都有至少一個元素的交，它們都與不同，那么，就至少要有51個元素，不可能，因此屬于每個集合。說明：這種題目最怕把它想難了，想行太難了，就會覺得無從下手，做數(shù)學競賽題就需要一方面在做題之前選好方向，另一方面就是大膽嘗試去做。7分析：證明恰有一個公共元也許挺難。那么證只有兩個或零個公共元不可能是否可行呢？如果具有兩個公共元的集合與表示為、那么有傳遞性。是否有用呢？證明：設結論不真。則所給的3元子集要么不交，要么恰有兩個公共元，如果子集與恰有兩個公共元，則記。設是三個子集?？梢宰C明如果，則，于是所有給定的3元子集可以分類，使得同一類中任意兩個不同子集都恰有兩個公共元。而不同類的子集不相交。于是對每個子集類，有三種可能：（1）恰含3個元素的類。（2）恰含4個元素的類。（3）至