初一數學競賽系列講座(15)容斥原理

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

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

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

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

5、體學生進行了短跑、游泳、籃球三個項目的測試，有4名學生在這三個項目都沒有達到優(yōu)秀，其余每人至少有一個項目達到優(yōu)秀，這部分學生達到優(yōu)秀的項目、人數如下表：短跑游泳籃球短跑、游泳游泳、籃球籃球、短跑短跑、游泳、籃球1718156652求這個班的學生數。(第三屆華杯賽復賽試題)解：有4名學生在這三個項目都沒有達到優(yōu)秀，在每個單項上達到優(yōu)秀的人數分別是17、18、15，因而，總人數是1718154=54。但其中有人獲得兩項優(yōu)秀，所以上面的計數產

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

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

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