奥数 容斥原理

容斥原埋在很多计数问题中常用到数学上的一个包含与排除原理，也称为容斥原理为了说明这个原理，我们先介绍一些集合的初步知识。例1、桌上有两张圆纸片A、B假设圆纸片A的面积为30平方厘米，圆纸片B的面积为20平方厘米这两张圆纸片重叠部分的面积为10平方厘米则这两张圆纸片覆盖桌面的面积由容斥原理的公式（1）可以算出为: 厘米）。I AUB I =30+20-10=40 （平方例2、求在1至100的自然数中能被3或7整除的数的个数。分析解这类问题时首先要知道在一串连续自然数中能被给定整数整 除的数的个数规律是：在n个连续自然数中有且仅有一个数能被n整除. 根据这个规律我们可以很容易地求出在1至100中能被3整除的数的个数 为33个，被7整除的数的个数为14个，而其中被3和7都能整除的数有 4个，因而得到解：设A= 在1100的自然数中能被3整除的数,B=在1100的自然数中能被7整除的数，则1304180943AAB= 在1100的自然数中能被21整除的数。100一3=331,.| A 1=33。100一7=142,.| B I =14。 100一21=416,.| APB I =4。由容斥原理的公式（1）：l AUB 1=33+14-4=43。答：在1100的自然数中能被3或7整除的数有43个。例3、求在1100的自然数中不是5的倍数也不是6的倍数的数有多少 个？分析如果在1100的自然数中去掉5的倍数、6的倍数，剩下的数 就既不是5的倍数也不是6的倍数，即问题要求的结果。解：设A=在1100的自然数中5的倍数的数,B= 在1100的自然数中6的倍数的数,则问题就是更求AUB在集合1, 2,100中的补集AUBTL素个数为此先求I AUB I。100一50=20,| A I =20又100一6=164,I B I =16710030=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个）答：在1100的自然数中既不是5的倍数又不是6的倍数的数共67 个。我们也可以把公式（1）用于求几何图形的面积这时，A和B是平面 上的两个点集（即点的集合），都是几何图形.I A I,I B I,吩别表 示A的面积，B的面积，。例4、设下面图中正方形的边长为1厘米，半圆均以正方形的边为直径， 求图中阴影部分的面积。答：阴影面积为0.57平方厘米。上面的例子是把一组事物按两种不同的性质来分类后，求具有其中一 种性质的元素个数问题如果把一组事物按三种不同性质来分类后，求具 有其中一种性质的元素个数的公式该是什么样的呢？我们仍用图形来说 明它具有与公式（1）类似的公式：I AUBUC l = lAl + lBl + ICl-l APB I - I APC I - I BPCl + I APBPC I,(2)其中 AUBUC=AU(BUC), APBPC=AP(BPC)右图中三个圆A、B、C分别表示具有三种不同性质的集合，并如图用M1、M2、M3、M7表示由三个圆形成的内部互不重叠的部分所含元素的个数，可见：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 APBPC I,即公式(2) 成立。事实上这个规律还可推广到按多种性质来分类的情形设集合M中的每个元素至少具有t种性质中的一种，用n表示各个具有1种性质的集合1中的元素个数的和，n表示各个具有2种性质的集合中元素个数的和，2n表示具有t种性质的集合中元素的个数，则集合M中元素的个数m为:m=n -n +n-n+土 n1234t最后一项当t为偶数时取“-”号，否则取“+”号。