《奧數(shù) 容斥原理》由會員分享，可在線閱讀，更多相關(guān)《奧數(shù) 容斥原理（6頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、容斥原埋
在很多計數(shù)問題中常用到數(shù)學(xué)上的一個包含與排除原理，也稱為容斥
原理?為了說明這個原理，我們先介紹一些集合的初步知識。
例1、桌上有兩張圓紙片A、B?假設(shè)圓紙片A的面積為30平方厘米，圓
紙片B的面積為20平方厘米?這兩張圓紙片重疊部分的面積為10
平方厘米?則這兩張圓紙片覆蓋桌面的面積由
容斥原理的公式（1）可以算出為: 厘米）。
I AUB I =30+20-10=40 （平方
例2、求在1至100的自然數(shù)中能被3或7整除的數(shù)的個數(shù)。
分析解這類問題時首先要知道在一串連續(xù)自然數(shù)中能被給定整數(shù)整 除的數(shù)的個數(shù)規(guī)律是：在n個連續(xù)自然數(shù)中有且
2、僅有一個數(shù)能被n整除. 根據(jù)這個規(guī)律我們可以很容易地求出在1至100中能被3整除的數(shù)的個數(shù) 為33個，被7整除的數(shù)的個數(shù)為14個，而其中被3和7都能整除的數(shù)有 4個，因而得到
解：設(shè)A= ｛在1?100的自然數(shù)中能被3整除的數(shù)｝,
B=｛在1?100的自然數(shù)中能被7整除的數(shù)｝，則
1304180943
AAB= ｛在1?100的自然數(shù)中能被21整除的數(shù)｝。
???100一3=33???1,.?.| A 1=33。
???100一7=14???2,.?.| B I =14。
? 100一21=4???16,.?.| APB I =4。
由容斥原理的公式（1）：l AUB 1=
3、33+14-4=43。
答：在1?100的自然數(shù)中能被3或7整除的數(shù)有43個。
例3、求在1?100的自然數(shù)中不是5的倍數(shù)也不是6的倍數(shù)的數(shù)有多少 個？
分析如果在1?100的自然數(shù)中去掉5的倍數(shù)、6的倍數(shù)，剩下的數(shù) 就既不是5的倍數(shù)也不是6的倍數(shù)，即問題要求的結(jié)果。
解：設(shè)A=｛在1?100的自然數(shù)中5的倍數(shù)的數(shù)｝,
B= ｛在1?100的自然數(shù)中6的倍數(shù)的數(shù)｝,
則問題就是更求AUB在集合｛1, 2, 100｝中的補(bǔ)集AUB^TL素個
數(shù)?為此先求I AUB I。
???100一50=20,???| A I =20
又???100一6=16???4,?I B I =16
4、
7100^30=3-10,
???| APB I =3,
I AUB I = I A I + I B I - I APB I =20+16-3=33。
■ I 丨 AUB I =100- I AUB I =100-33= 67 C個）□
答：在1?100的自然數(shù)中既不是5的倍數(shù)又不是6的倍數(shù)的數(shù)共67 個。
我們也可以把公式（1）用于求幾何圖形的面積?這時，A和B是平面 上的兩個點集（即點的集合），都是幾何圖形.I A I,I B I,…吩別表 示A的面積，B的面積，…。
例4、設(shè)下面圖中正方形的邊長為1厘米，半圓均以正方形的邊為直徑， 求圖中陰影部分的面積。
5、答：陰影面積為0.57平方厘米。
上面的例子是把一組事物按兩種不同的性質(zhì)來分類后，求具有其中一 種性質(zhì)的元素個數(shù)問題?如果把一組事物按三種不同性質(zhì)來分類后，求具 有其中一種性質(zhì)的元素個數(shù)的公式該是什么樣的呢？我們?nèi)杂脠D形來說 明它具有與公式（1）類似的公式：
I AUBUC l = lAl + lBl + ICl-l APB I - I APC I - I BP
Cl + I APBPC I, (2)
其中 AUBUC=AU(BUC), APBPC=AP(BPC)?
右圖中三個圓A、B、C分別表示具有三種不同性質(zhì)的集合，并如圖
用M1、M2、M3、…、M7表示由三個圓形成的內(nèi)部互不
6、重疊的部分所
含元素的個數(shù)，可見：
I AUBUC I=M1+M2+???+M7
= (M1+M4+M6+M7) + (M2+M4+M5+M7) + (M3+M5+
M6+M7) -[ (M4+M7) + (M5+M7) + (M6+M7) ]+M7
= IAI + IBI + ICI-I APB I - I BPC I - I APC I + I APB
PC I,
即公式(2) 成立。
事實上這個規(guī)律還可推廣到按多種性質(zhì)來分類的情形?設(shè)集合M中的
每個元素至少具有t種性質(zhì)中的一種，用n表示各個具有1種性質(zhì)的集合
1
中的元素個數(shù)的和，n表示各個具有2種性質(zhì)的集合中元素個數(shù)的和，?…
2
n表示具有t種性質(zhì)的集合中元素的個數(shù)，則集合M中元素的個數(shù)m為:
m=n -n +n-n+…土 n
1 2 3 4 t
最后一項當(dāng)t為偶數(shù)時取“-”號，否則取“+”號。
奧數(shù) 容斥原理
