2022年高中數(shù)學(xué)競(jìng)賽輔導(dǎo)資料《容斥原理》

《2022年高中數(shù)學(xué)競(jìng)賽輔導(dǎo)資料《容斥原理》》由會(huì)員分享，可在線閱讀，更多相關(guān)《2022年高中數(shù)學(xué)競(jìng)賽輔導(dǎo)資料《容斥原理》（7頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、2022年高中數(shù)學(xué)競(jìng)賽輔導(dǎo)資料容斥原理相對(duì)補(bǔ)集：稱屬于A而不屬于B的全體元素，組成的集合為B對(duì)A的相對(duì)補(bǔ)集或差集，記作A-B。容斥原理：以表示集合A中元素的數(shù)目，我們有，其中為n個(gè)集合稱為A的階。n階集合的全部子集數(shù)目為。例題講解1對(duì)集合1，2，n及其每一個(gè)非空了集，定義一個(gè)唯一確定的“交替和”如下：按照遞減的次序重新排列該子集，然后交替地減或加后繼的數(shù)所得的結(jié)果，例如，集合的“交替和”是9-6+4-2+1=6.的“交替和”是6-5=1，的交替和是2。那么，對(duì)于n=7。求所有子集的“交替和”的總和。2某班對(duì)數(shù)學(xué)、物理、化學(xué)三科總評(píng)成績(jī)統(tǒng)計(jì)如下：優(yōu)秀的人數(shù)：數(shù)學(xué)21個(gè)，物理19個(gè)，化學(xué)20個(gè)，數(shù)

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

3、：存在一個(gè)元素，它屬于全部集合。7在個(gè)元素組成的集合中取個(gè)不同的三元子集。證明：其中必有兩個(gè)，它們恰有一個(gè)公共元。課后練習(xí)1一個(gè)集合含有10個(gè)互不相同的十進(jìn)制兩位數(shù)，證明：這個(gè)集合必有兩個(gè)無公共元素的子集合，這兩個(gè)子集元素和相等。2是否存在兩個(gè)以非頁整數(shù)為元素的集合A、B，使得任一個(gè)非負(fù)整數(shù)都可以被A、B之中各取一數(shù)之和唯一表出。3對(duì)每個(gè)使得在n元集合中，可以取出k個(gè)子集，其中任意兩個(gè)的交非合。4能否把分成兩個(gè)積相等的不交集合。課后練習(xí)答案1我們可以發(fā)現(xiàn)對(duì)每個(gè)數(shù)，它出現(xiàn)在個(gè)子集之中，因此所有子集中的的和為，那么全部元素在全部子集之中的和為。2利用二進(jìn)制來考慮此題，小明的前9包分別有錢 1分（2

4、），10分（2），100分（2），1000分（2），10000分（2），100000分（2），1000000分（2），10000000分（2），100000000分（2），剩下一包裝剩下的錢（以上數(shù)皆為二進(jìn)制）就可以了。3不能。反證法。設(shè)存在合乎題中條件的一種分法，如果和同屬于一個(gè)子集，則記為，否則記為，對(duì)，若分在三個(gè)集合中則稱為好的。都是好的。，而 ，故在第二組中用代替，故是好的。故。由此 即，但。矛盾！有這樣一個(gè)結(jié)論階集合的子集若滿足且則的最大值為，代入本題得為。例題答案：1分析；n=7時(shí)，集合7，6，5，4，3，2，1的非空子集有個(gè)，雖然子集數(shù)目有限，但是逐一計(jì)算各自的“交替和”再相加，

5、計(jì)算量仍然巨大，但是，根據(jù)“交替和”的定義，容易看到集合1，2，3，4，5，6，7與1，2，3，4，5，6的“交替和”是7；可以想到把一個(gè)不含7的集和A與的“交替和”之和應(yīng)為7。那么，我們也就很容易解決這個(gè)問題了。解：集合1，2，3，4，5，6，7的子集中，除去7外還有個(gè)非空子集合，把這個(gè)非空子集兩兩結(jié)組后分別計(jì)算每一組中“交替和”之和，結(jié)組原則是設(shè)這是把結(jié)合為一組，顯然，每組中，“交替和”之和應(yīng)為7，共有組.所以,所有“交替和”之和應(yīng)該為。說明：我們?cè)谶@道題的證明過程中用了這類題目最典型的解法。就是“對(duì)應(yīng)”的方法，“對(duì)應(yīng)”的方法在解決相等的問題中應(yīng)用得更多。2分析：自然地設(shè)A=數(shù)學(xué)總評(píng)優(yōu)秀的

6、人B=物理總評(píng)優(yōu)秀的人C=化學(xué)總評(píng)優(yōu)秀的人則已知|A|=21 |B|=19 |C|=20這表明全班人數(shù)在41至48人之間。僅數(shù)學(xué)優(yōu)秀的人數(shù)是可見僅數(shù)學(xué)優(yōu)秀的人數(shù)在4至11人之間。同理僅物理優(yōu)秀的人數(shù)在3至10人之間。同理僅化學(xué)優(yōu)秀的人數(shù)在5至12人之間。解：（略）。說明：先將具體的實(shí)際生活中的問題數(shù)學(xué)化，然后根據(jù)數(shù)學(xué)理論來解決這個(gè)問題不僅是競(jìng)賽中常見情況，也是在未來學(xué)習(xí)中數(shù)學(xué)真正有用的地方。3分析1：用“篩法”找出不超過120的質(zhì)數(shù)(素?cái)?shù))，計(jì)算它們的個(gè)數(shù)，從120中去掉質(zhì)數(shù)，再去掉“1”，剩下的即是合數(shù)。解法1：120以內(nèi)： 既不是素?cái)?shù)又不是合數(shù)的數(shù)有一個(gè)，即“1”； 素?cái)?shù)有2、3、5、7、

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個(gè)。所以不超過120的合數(shù)有12013089(個(gè))(附：篩法：從小到大按順序?qū)懗?120的所有自然數(shù)：先劃掉1，保留2，然后劃掉2的所有倍數(shù)4,6，120等；保留3，再劃掉所有3的倍數(shù)6,9117、120等；保留5，再劃掉5的所有倍數(shù)10,15，120；保留7，再劃掉7的所有倍數(shù)，這樣，上面數(shù)表中剩下的數(shù)就是120以內(nèi)的所有素?cái)?shù)，這種方法是最古老的尋找素?cái)?shù)的方法，叫做“埃斯托拉篩法”)說明：當(dāng)n不很大時(shí)，計(jì)算1n中的合數(shù)的個(gè)

8、數(shù)困難不大；但當(dāng)n很大時(shí)，利用篩法就很困難、很費(fèi)時(shí)了，必須另覓他途。分析2受解法1的啟發(fā)，如果能找出1n中質(zhì)數(shù)的個(gè)數(shù)m，則n1m就是不超過n的合數(shù)的個(gè)數(shù)。由初等數(shù)論中定理：a是大于1的整數(shù)。如果所有不大于a的質(zhì)數(shù)都不能整除a，那么a是質(zhì)數(shù)。因?yàn)?20121112，12011，所以不超過120的合數(shù)必是2或3或5或7的倍數(shù)，所以只要分別計(jì)算出不超過120的2、3、5、7的倍數(shù)，再利用“容斥原理”即可。解法2：設(shè)S1a13120,2a；S2b1b120,3b；S3c13120,5c；S4=d1d120,7d，則有：card(S1)120/2=60，card(S2)120/340，card(S3)1

9、20/524，card(S4)120/717；(n表示n的整數(shù)部分，例如2,42，)card(S1S2)120/2320，card(S1S3)120/2512，card(S1S4)120/278，card(S2S3)120/358，card(S2S4)120/375，card(S3S4)120/573，card(S1S2S3)120/2354，card(S1S2S4)120/2372，card(S1S3S4)120/2571，card(S2S3S4)120/3571，card(S1S2S3S4)120/23570card(S1S2S3S4)card(S1)card(S2)card(S3)car

10、d(S4)card(S1S2)card(S1S3)card(S1S4)card(S2S3)card(S2S4)card(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是質(zhì)數(shù)93489即不超過120的合數(shù)共有89個(gè)。4分析：在與一個(gè)人A合作的人中我們找到B。再說明一定有人與A和B都合作過為C。最后再說明有人與A、B、C都合作過為D，那么A、B、C、D就是找的人了。 證明：一個(gè)人A。不妨設(shè)B與之合作。那么

11、。即C與A和B均合作過，分別表示與A、B合作過的人的集合。同樣地，。所以存在。則A、B、C、D就是所求，證畢。說明：把一個(gè)普通的敘述性問題轉(zhuǎn)化為集合的語言描述的問題通常為解題的關(guān)鍵之處，也是同學(xué)們需加強(qiáng)的。5分析：首先考慮到是一個(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)：從較

12、大的子集挪出一些元素，添加到較小的子集，挪出的元素個(gè)數(shù)為較小子集的元素個(gè)數(shù)，于是得到的所有子集的元素個(gè)數(shù)都是偶數(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ù)為，證畢。說明：這道題的證明中隱含了一種單一變量在變化時(shí)變化方向相同這一性質(zhì)，就這道題來說，一直在增加的就是各子集元素個(gè)數(shù)被2的多少次冪整除的這個(gè)冪次數(shù)，這是一大

13、類問題，除了這種變化量，還要經(jīng)?？紤]變化中的不變量。6分析：我們可以先去找一個(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è)集合。說明：這種題目最怕把它想難了，想行太難了，就會(huì)覺得無從下手，做數(shù)

14、學(xué)競(jìng)賽題就需要一方面在做題之前選好方向，另一方面就是大膽嘗試去做。7分析：證明恰有一個(gè)公共元也許挺難。那么證只有兩個(gè)或零個(gè)公共元不可能是否可行呢？如果具有兩個(gè)公共元的集合與表示為、那么有傳遞性。是否有用呢？證明：設(shè)結(jié)論不真。則所給的3元子集要么不交，要么恰有兩個(gè)公共元，如果子集與恰有兩個(gè)公共元，則記。設(shè)是三個(gè)子集。可以證明如果，則，于是所有給定的3元子集可以分類，使得同一類中任意兩個(gè)不同子集都恰有兩個(gè)公共元。而不同類的子集不相交。于是對(duì)每個(gè)子集類，有三種可能：（1）恰含3個(gè)元素的類。（2）恰含4個(gè)元素的類。（3）至少含5個(gè)元素的類。在（1）下，3元子集類恰由一個(gè)3元子集組成。在（2）下，子集類中至多有4個(gè)子集?？紤]（3） 設(shè)，則還有一個(gè)，由，有。因此對(duì)子集類中任意子集，由，它包含與，于是類中子集個(gè)數(shù)比類中元素個(gè)數(shù)少2，于是，每個(gè)類中子集個(gè)數(shù)不超過元素個(gè)數(shù)，但是題中條件子集數(shù)大于元素個(gè)數(shù)，矛盾！說明：此題為1979年美國(guó)競(jìng)賽題。題目難度較大，應(yīng)該說是應(yīng)用了高等代數(shù)中的一些思想。