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

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

2019-2020年高中數(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ù)學(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ì)算不超過(guò)120的合數(shù)的個(gè)數(shù) 4．1992位科學(xué)家，每人至少與1329人合作過(guò)，那么，其中一定有四位數(shù)學(xué)家兩兩合作過(guò)。 5．把個(gè)元素的集合分為若干個(gè)兩兩不交的子集，按照下述規(guī)則將某一個(gè)子集中某些元素挪到另一個(gè)子集：從前一子集挪到后一子集的元素個(gè)數(shù)等于后一子集的元素個(gè)數(shù)（前一子集的元素個(gè)數(shù)應(yīng)不小于后一子集的元素個(gè)數(shù)），證明：可以經(jīng)過(guò)有限次挪動(dòng)，使得到的子集與原集合相重合。 6．給定1978個(gè)集合，每個(gè)集合都含有40個(gè)元素，已知其中任意兩個(gè)集合都恰有一個(gè)公共元，證明：存在一個(gè)元素，它屬于全部集合。 7．在個(gè)元素組成的集合中取個(gè)不同的三元子集。證明：其中必有兩個(gè)，它們恰有一個(gè)公共元。 課后練習(xí) 1．一個(gè)集合含有10個(gè)互不相同的十進(jìn)制兩位數(shù)，證明：這個(gè)集合必有兩個(gè)無(wú)公共元素的子集合，這兩個(gè)子集元素和相等。 2．是否存在兩個(gè)以非頁(yè)整數(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)制來(lái)考慮此題，小明的前9包分別有錢 1分（2），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ì)算各自的“交替和”再相加，計(jì)算量仍然巨大，但是，根據(jù)“交替和”的定義，容易看到集合{1，2，3，4，5，6，7}與{1，2，3，4，5，6}的“交替和”是7；可以想到把一個(gè)不含7的集和A與的“交替和”之和應(yīng)為7。那么，我們也就很容易解決這個(gè)問(wèn)題了。 　　解：集合{1，2，3，4，5，6，7}的子集中，除去{7}外還有個(gè)非空子集合，把這個(gè)非空子集兩兩結(jié)組后分別計(jì)算每一組中“交替和”之和，結(jié)組原則是設(shè)這是把結(jié)合為一組，顯然，每組中，“交替和”之和應(yīng)為7，共有組.所以,所有“交替和”之和應(yīng)該為。 　　說(shuō)明：我們?cè)谶@道題的證明過(guò)程中用了這類題目最典型的解法。就是“對(duì)應(yīng)”的方法，“對(duì)應(yīng)”的方法在解決相等的問(wèn)題中應(yīng)用得更多。 2．分析：自然地設(shè)A={數(shù)學(xué)總評(píng)優(yōu)秀的人} 　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ù)是 　　 可見(jiàn)僅數(shù)學(xué)優(yōu)秀的人數(shù)在4至11人之間。 同理僅物理優(yōu)秀的人數(shù)在3至10人之間。 同理僅化學(xué)優(yōu)秀的人數(shù)在5至12人之間。 解：（略）。 說(shuō)明：先將具體的實(shí)際生活中的問(wèn)題數(shù)學(xué)化，然后根據(jù)數(shù)學(xué)理論來(lái)解決這個(gè)問(wèn)題不僅是競(jìng)賽中常見(jiàn)情況，也是在未來(lái)學(xué)習(xí)中數(shù)學(xué)真正有用的地方。 3．分析1：用“篩法”找出不超過(guò)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、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è)。所以不超過(guò)120的合數(shù)有120－1－30＝89(個(gè))(附：篩法：從小到大按順序?qū)懗?－120的所有自然數(shù)： 　　先劃掉1，保留2，然后劃掉2的所有倍數(shù)4,6，…120等；保留3，再劃掉所有3的倍數(shù)6,9…117、120等；保留5，再劃掉5的所有倍數(shù)10,15，…120；保留7，再劃掉7的所有倍數(shù)，…這樣，上面數(shù)表中剩下的數(shù)就是120以內(nèi)的所有素?cái)?shù)，這種方法是最古老的尋找素?cái)?shù)的方法，叫做“埃斯托拉‘篩法’”) 　　說(shuō)明：當(dāng)n不很大時(shí)，計(jì)算1－n中的合數(shù)的個(gè)數(shù)困難不大；但當(dāng)n很大時(shí)，利用篩法就很困難、很費(fèi)時(shí)了，必須另覓他途。 　　[分析2]受解法1的啟發(fā)，如果能找出1－n中質(zhì)數(shù)的個(gè)數(shù)m，則n－1－m就是不超過(guò)n的合數(shù)的個(gè)數(shù)。由初等數(shù)論中定理：a是大于1的整數(shù)。如果所有不大于√a的質(zhì)數(shù)都不能整除a，那么a是質(zhì)數(shù)。因?yàn)?20<121＝112，√120<11，所以不超過(guò)120的合數(shù)必是2或3或5或7的倍數(shù)，所以只要分別計(jì)算出不超過(guò)120的2、3、5、7的倍數(shù)，再利用“容斥原理”即可。 　　解法2：設(shè)S1＝{a∣1≤3≤120,2∣a}；S2＝{b∣1≤b≤120,3∣b}；S3＝{c∣1≤3≤120,5∣c}；S4={d∣1≤d≤120,7∣d}，則有： 　　card(S1)＝[120/2]=60，card(S2)＝[120/3]＝40，card(S3)＝[120/5]＝24，card(S4)＝[120/7]＝17； 　　([n]表示n的整數(shù)部分，例如[2,4]＝2，…) 　　card(S1∩S2)＝[120/23]＝20，card(S1∩S3)＝[120/25]＝12， 　　card(S1∩S4)＝[120/27]＝8，card(S2∩S3)＝[120/35]＝8， 　　card(S2∩S4)＝[120/37]＝5，card(S3∩S4)[120/57]＝3， 　　card(S1∩S2∩S3)[120/235]＝4，card(S1∩S2∩S4)＝[120/237]＝2， 　　card(S1∩S3∩S4)＝[120/257]＝1，card(S2∩S3∩S4)＝[120/357]＝1， 　　card(S1∩S2∩S3∩S4)＝[120/2357]＝0 　　∴card(S1∪S2∪S3∪S4)＝card(S1)＋card(S2)＋card(S3)＋card(S4)－card(S1∩S2)－card(S1∩S3)－card(S1∩S4)－card(S2∩S3)－card(S2∩S4)－card(S3∩S4)＋card(S1∩S2∩S3)＋card(S1∩S2∩S4)＋card(S1∩S3∩S4)＋card(S2∩S3∩S4)－card(S1∩S2∩S3∩S4)＝(60＋40＋24＋17)-(20+12+8+8+5+3)+(4+2+1+1)-0＝141-56＋8＝93 　　∵2，3，5，7是質(zhì)數(shù) 　　∴93－4＝89 　　即不超過(guò)120的合數(shù)共有89個(gè)。 4．分析：在與一個(gè)人A合作的人中我們找到B。再說(shuō)明一定有人與A和B都合作過(guò)為C。最后再說(shuō)明有人與A、B、C都合作過(guò)為D，那么A、B、C、D就是找的人了。 證明：一個(gè)人A。不妨設(shè)B與之合作。那么 。即C與A和B均合作過(guò)，分別表示與A、B合作過(guò)的人的集合。同樣地，。 　　所以存在。則A、B、C、D就是所求，證畢。 說(shuō)明：把一個(gè)普通的敘述性問(wèn)題轉(zhuǎn)化為集合的語(yǔ)言描述的問(wè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)：從較大的子集挪出一些元素，添加到較小的子集，挪出的元素個(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ù)為，證畢。 說(shuō)明：這道題的證明中隱含了一種單一變量在變化時(shí)變化方向相同這一性質(zhì)，就這道題來(lái)說(shuō)，一直在增加的就是各子集元素個(gè)數(shù)被2的多少次冪整除的這個(gè)冪次數(shù)，這是一大類問(wèn)題，除了這種變化量，還要經(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è)集合。 說(shuō)明：這種題目最怕把它想難了，想行太難了，就會(huì)覺(jué)得無(wú)從下手，做數(shù)學(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ù)不超過(guò)元素個(gè)數(shù)，但是題中條件子集數(shù)大于元素個(gè)數(shù)，矛盾！ 說(shuō)明：此題為1979年美國(guó)競(jìng)賽題。題目難度較大，應(yīng)該說(shuō)是應(yīng)用了高等代數(shù)中的一些思想。