初一數(shù)學(xué)競(jìng)賽系列講座(15)容斥原理

1、初一數(shù)學(xué)競(jìng)賽系列講座(15)容斥原理一、知識(shí)要點(diǎn)1、容斥原理在計(jì)數(shù)時(shí)，常常遇到這樣的情況，作合并運(yùn)算時(shí)會(huì)把重復(fù)的部分多算，需要減去；作排除運(yùn)算時(shí)會(huì)把重復(fù)部分多減，需要加上，這就是容斥原理。它的基本形式是：記A、B是兩個(gè)集合，屬于集合A的東西有個(gè)，屬于集合B的東西有個(gè)，AB既屬于集合A又屬于集合B的東西記為，有個(gè)；屬于集合A或?qū)儆诩疊A?BA?合B的東西記為，有個(gè)，則有：=BA?BA?BA?ABBA?容斥原理可以用一個(gè)直觀的圖形來(lái)解釋。如

2、圖，左圓表示集合A，右圓表示集合B，兩圓的公共部分表示，兩圓合起來(lái)的部分表示，BA?BA?由圖可知：=BA?ABBA?容斥原理又被稱作包含排除原理或逐步淘汰原則。二、例題精講例1在1到200的整數(shù)中，既不能被2整除，又不能被3整除的整數(shù)有多少個(gè)？分析：根據(jù)容斥原理，應(yīng)是200減去能被2整除的整數(shù)個(gè)數(shù)，減去能被3整除的整數(shù)個(gè)數(shù)，還要加上既能被2整除又能被3整除，即能被6整除的整數(shù)個(gè)數(shù)。解：在1到200的整數(shù)中，能被2整除的整數(shù)個(gè)數(shù)為：2?

3、1，2?2，…，2?100，共100個(gè)；在1到200的整數(shù)中，能被3整除的整數(shù)個(gè)數(shù)為：3?1，3?2，…，3?66，共66個(gè)；在1到200的整數(shù)中，既能被2整除又能被3整除，即能被6整除的整數(shù)個(gè)數(shù)為：6?1，6?2，…，6?33，共33個(gè)；所以，在1到200的整數(shù)中，既不能被2整除，又不能被3整除的整數(shù)個(gè)數(shù)為：2001006633=67(個(gè))例2求1到100的自然數(shù)中，所有既不是2的倍數(shù)又不是3的倍數(shù)的整數(shù)之和S。解：1到100的自然數(shù)

4、中，所有自然數(shù)的和是：123…100=50501到100的自然數(shù)中，所有2的倍數(shù)的自然數(shù)和是：2?12?2…2?50=2?(123…50)=2?1275=25501到100的自然數(shù)中，所有3的倍數(shù)的自然數(shù)和是：3?13?2…3?33=3?(123…33)=3?561=16831到100的自然數(shù)中，所有既是2的倍數(shù)又是3的倍數(shù)，即是6的倍數(shù)的自然數(shù)和是：6?16?2…6?16=6?(123…16)=6?136=816A?BAB例5某班的全

5、體學(xué)生進(jìn)行了短跑、游泳、籃球三個(gè)項(xiàng)目的測(cè)試，有4名學(xué)生在這三個(gè)項(xiàng)目都沒(méi)有達(dá)到優(yōu)秀，其余每人至少有一個(gè)項(xiàng)目達(dá)到優(yōu)秀，這部分學(xué)生達(dá)到優(yōu)秀的項(xiàng)目、人數(shù)如下表：短跑游泳籃球短跑、游泳游泳、籃球籃球、短跑短跑、游泳、籃球1718156652求這個(gè)班的學(xué)生數(shù)。(第三屆華杯賽復(fù)賽試題)解：有4名學(xué)生在這三個(gè)項(xiàng)目都沒(méi)有達(dá)到優(yōu)秀，在每個(gè)單項(xiàng)上達(dá)到優(yōu)秀的人數(shù)分別是17、18、15，因而，總?cè)藬?shù)是1718154=54。但其中有人獲得兩項(xiàng)優(yōu)秀，所以上面的計(jì)數(shù)產(chǎn)

6、生了重復(fù)，重復(fù)人數(shù)應(yīng)當(dāng)減去，即總?cè)藬?shù)變?yōu)椋?4665=37又考慮到獲得三項(xiàng)優(yōu)秀的人，他們一開(kāi)始被重復(fù)計(jì)算了三次，但在后來(lái)又被重復(fù)減去了三次，所以最后還要將他們加進(jìn)去。即這個(gè)班學(xué)生數(shù)為：372=39。例6從1到1000000這一百萬(wàn)個(gè)自然數(shù)中，能被11整除而不能被13整除的數(shù)多還是能被13整除而不能被11整除的數(shù)多？(第20屆全俄九年級(jí)試題)解：設(shè)1到1000000這一百萬(wàn)個(gè)自然數(shù)中，能被11整除而不能被13整除的數(shù)有m個(gè)，能被13整除而

7、不能被11整除的數(shù)有n個(gè)，既能被11又能被13整除的數(shù)有p個(gè)。而在1到1000000這一百萬(wàn)個(gè)自然數(shù)中，能被11整除數(shù)有90909個(gè)，∴mp=90909在1到1000000這一百萬(wàn)個(gè)自然數(shù)中，能被13整除數(shù)有76923個(gè)，∴np=76923∴mpnp∴mn，即能被11整除而不能被13整除的數(shù)比能被13整除而不能被11整除的數(shù)多。例750名學(xué)生面向老師站成一行，老師先讓大家從左到右按1，2，3，…依次報(bào)數(shù)，再讓報(bào)數(shù)是4的倍數(shù)的同學(xué)向后轉(zhuǎn)，

8、接著又讓報(bào)數(shù)是6的倍數(shù)同學(xué)向后轉(zhuǎn)，問(wèn)此時(shí)還有多少同學(xué)面向老師？(1995年華杯賽試題)分析：首先沒(méi)有轉(zhuǎn)的同學(xué)仍面向老師，即報(bào)數(shù)既不是4的倍數(shù)，也不是6的倍數(shù)的同學(xué)仍面向老師，其次，報(bào)數(shù)既是4的倍數(shù)，也是6的倍數(shù)，即是12的倍數(shù)同學(xué)連續(xù)轉(zhuǎn)了兩次，仍面向老師。解：報(bào)數(shù)是4的倍數(shù)的同學(xué)有12個(gè)，報(bào)數(shù)是6的倍數(shù)的同學(xué)有8個(gè)，報(bào)數(shù)是12的倍數(shù)的同學(xué)有4個(gè)，所以根據(jù)容斥原理得：報(bào)數(shù)既不是4的倍數(shù)，也不是6的倍數(shù)的同學(xué)有501284=34個(gè)。報(bào)數(shù)既是