初一競賽講座15（容斥原理）

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

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

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

4、的自然數(shù)中，所有自然數(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=816所以，1到10

5、0的自然數(shù)中，所有既不是2的倍數(shù)又不是3的倍數(shù)的整數(shù)之和S=505025501683816=1633A?BABS=20100(1010066334100)(336621001365)630=630例5某班的全體學(xué)生進行了短跑、游泳、籃球三個項目的測試，有4名學(xué)生在這三個項目都沒有達到優(yōu)秀，其余每人至少有一個項目達到優(yōu)秀，這部分學(xué)生達到優(yōu)秀的項目、人數(shù)如下表：短跑游泳籃球短跑、游泳游泳、籃球籃球、短跑短跑、游泳、籃球1718156652求

6、這個班的學(xué)生數(shù)。(第三屆華杯賽復(fù)賽試題)解：有4名學(xué)生在這三個項目都沒有達到優(yōu)秀，在每個單項上達到優(yōu)秀的人數(shù)分別是17、18、15，因而，總?cè)藬?shù)是1718154=54。但其中有人獲得兩項優(yōu)秀，所以上面的計數(shù)產(chǎn)生了重復(fù)，重復(fù)人數(shù)應(yīng)當(dāng)減去，即總?cè)藬?shù)變?yōu)椋?4665=37又考慮到獲得三項優(yōu)秀的人，他們一開始被重復(fù)計算了三次，但在后來又被重復(fù)減去了三次，所以最后還要將他們加進去。即這個班學(xué)生數(shù)為：372=39。例6從1到1000000這一百萬個

7、自然數(shù)中，能被11整除而不能被13整除的數(shù)多還是能被13整除而不能被11整除的數(shù)多？(第20屆全俄九年級試題)解：設(shè)1到1000000這一百萬個自然數(shù)中，能被11整除而不能被13整除的數(shù)有m個，能被13整除而不能被11整除的數(shù)有n個，既能被11又能被13整除的數(shù)有p個。而在1到1000000這一百萬個自然數(shù)中，能被11整除數(shù)有90909個，∴mp=90909在1到1000000這一百萬個自然數(shù)中，能被13整除數(shù)有76923個，∴np=7

8、6923∴mpnp∴mn，即能被11整除而不能被13整除的數(shù)比能被13整除而不能被11整除的數(shù)多。例750名學(xué)生面向老師站成一行，老師先讓大家從左到右按1，2，3，…依次報數(shù)，再讓報數(shù)是4的倍數(shù)的同學(xué)向后轉(zhuǎn)，接著又讓報數(shù)是6的倍數(shù)同學(xué)向后轉(zhuǎn)，問此時還有多少同學(xué)面向老師？(1995年華杯賽試題)分析：首先沒有轉(zhuǎn)的同學(xué)仍面向老師，即報數(shù)既不是4的倍數(shù)，也不是6的倍數(shù)的同學(xué)仍面向老師，其次，報數(shù)既是4的倍數(shù)，也是6的倍數(shù)，即是12的倍數(shù)同學(xué)連

9、續(xù)轉(zhuǎn)了兩次，仍面向老師。解：報數(shù)是4的倍數(shù)的同學(xué)有12個，報數(shù)是6的倍數(shù)的同學(xué)有8個，報數(shù)是12的倍數(shù)的同學(xué)有4個，所以根據(jù)容斥原理得：報數(shù)既不是4的倍數(shù)，也不是6的倍數(shù)的同學(xué)有501284=34個。報數(shù)既是4的倍數(shù)，也是6的倍數(shù)，即是12的倍數(shù)同學(xué)有4個。所以此時還應(yīng)有344=38個同學(xué)面向老師。評注：若將同學(xué)數(shù)50改成n，問此時還有多少同學(xué)面向老師？可以得出一個一般的結(jié)論：?????????????????????12264nnnn