十三集合问题欧拉问题

1、十三集合问题容斥原理欧拉问题391.一个班有45个学生，都借了课外书，统计街课外书的情况是：全班借语文的有人，借数学的有32人，同时借语文书和数学书的有多少人？解：可以借助韦恩图来分析已知条件的关系。已知A=借语文书的人=39B=借数学书的人=32C=只借语文书的人D=只借数学书的人E=语文数学书都借的人AUB=45求：AABAAB=A+B-（AUB）=（C+E）+（E+D）-（C+E+D）=39+32-45=26人有10人即会演唱又会乐器，没有一无所长2.某宣传队有45人会演唱有14人会乐器,的人，这个宣传队有多少人？解：A=会演唱的人=45人B=会乐器的人=14人C=只会演唱的人,D=只会

2、乐器的人E=AAB=即会演唱又会乐器的人=10求：AUBAUB=A+BAAB=45+14-10=49人定理：1：aUb=A+B-ArlB证明：利用面积证明。很明显，两个圆所占得面积等于两个圆得面积和减去两圆相交部分的面积。因为相交部分是重叠的。定理2：|aUbUc=A+|B+CABBCCA+A，BC证明：文氏图分块标记如右图图：1245构成A,2356构成C,4567构成Bo三个圆为ABC所占的总面积为AUBUCoAAB+BnC+CPA=（图4+图5）+（图5+图6）+（图2+图5）=图2+图4+图6+3个图5AABAC为最中间面积即图5的面积。圆A+圆B+圆C=（图1+图2+图5+图4）+（

3、图4+图5+图6+图7）+（图2+图5+图6+图3）整个图形的面积AUBUC=图1+图2+图3+图4+图5+图6+图7=圆A+圆B+圆C-（图4+图5）（图5+图6）（图2+图5）+图5=A+B+CAABBAGCPA+AABAC定理三：|aUbUcUd|=|A+|b|+|+|d|-|AriB|-|Aq-|APiqbCc|bCd|cdi+|AnBnq+|AnBnD|+|Bncnd|a，bc，d证明从略。3. 一个学校有三门课程：数学、物理、化学。已知修这三门功课的学生分别有170,130,120人；同时修数学、物理两门课程的有45人，同时修数学、化学的有20人；同时修物理、化学的有22人；同时修

4、三门功课的有3人，问这学校共有多少人？解：令A为修数学课的学生集合；B为修物理的学生集合；C为修化学课的学生集合。A=170,B=130,C=20,AB|=45AC=20,BC=22,ABC=3aUbUc=A+B+C-aAb-bCccAA+ABC=170+130+120452022+3=336人答：全校有336人。4 .求a,b,c,d,e,f这六个字母的全排列中，不允许出现abe和df图像的排列数。解：设A为abe作为一个元素出现的排列集，B为af作为一个元素出现的排列集。AB为同时出现abe,df的排列集A=4!,B=5!,AB=3根据容斥原理，不允许出现abe和df图像的排列集为AB=6

5、!-(5!4!)3!=5825 .求从1到500的整数中被3或5除尽的个数。解：令A为从1到500的整数中被3除尽的数的集合，B为从1到500的整数中被5除尽的数的集合。=166,|B=(500=100AB=500=33IL15被3或5除尽的数的个数为aUb=A+B-a1B=166+100-33=233因A=NA,其中N是集合U的元素的个数，即不属于A的元素个数等于集合的全体，去掉属于A的元素的个数。定理4.aAb=n-aUb=n-（a+b）+aTb定理5.AnBnc=NaUbUc=n(a+b+c)+aCb+bCc+cCa-abHc6 .一次期末考试，某班有15人数学得满分，有12人语文得满分

6、，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？解：由定理1得：15+12-4=237 .电视台向100人调查前一天收看电视的情况，有62人看过2频道，34人看过8频道，其中11人两个频道都看过。两个频道都没看过的有多少人？解：由定理4得：100（62+3411）=158 .某校六班有学生45人，每人在暑假里都参加体育训练队，其中参加足球队的有25人，参加排球队的有22人，参加游泳队的有24人，足球、排球都参加的有12人，足球、游泳都参加的有9人，排球、游泳都参加的有8人，问：三项都参加的有多少人？已知：ABC=45,A=25,B=22,C=24,AB=12,BC=9,C

7、A=8求：ABC=?解：.aUbUc=A+B+CABBcCA+aAbAc:.ABC=ABC|A_B_C|ABBC|-|CA=45-25-22-24+12+9+8=3人9 .分母是1001的最简分数一共有多少个？分析：这一题实际上就是找分子中不能与1001进行约分的数。由于1001=7X11X13,所以就是找不能被7,11,13整除的数。解答：11001中，有7的倍数1001/7=143（个）；有11的倍数1001/11=91（个），有13的倍数1001/13=77（个）；有7X11=77的倍数1001/77=13（个），有7X13=91的倍数1001/91=11（个），有11X13=143的倍

8、数1001/143=7（个）.有1001的倍数1个。由容斥原理知：在11001中，能被7或11或13整除的数有（143+91+77）（13+11+7）+1=281（个），从而不能被7、11或13整除的数有1001281=720（个）.也就是说，分母为1001的最简分数有720个。10 .某个班的全体学生在进行了短跑、游泳、投掷三个项目的测试后，有4名学生在这三个项目上都没有达到优秀，其余每人至少有一项达到了优秀，达到了优秀的这部分学生情况如下表：短跑游泳投掷短跑、游泳短跑、投掷游泳、投掷短跑、游泳、投掷1718156652求这个班的学生共有多少人?分析：这个班的学生数，应包括达到优秀和没有达到

9、优秀的。4+17+18+15665+2=39(人)11.一个班有42人，参加合唱队的有30人，参加美术组的有25人，有5人什么都没有参加，求两种都参加的有多少人？解：AnB=A+B_AUB(30+25+5)-42=18人12.在一根木棍上有三种刻度线，第一种刻度线将木棍分成10等份，第二种将木棍分成12等份，第三种将木棍分成15等份。如果沿每条刻度线将木棍锯断，木棍总共被锯成多少段？分析：很显然，要计算木棍被锯成多少段，只需要计算出木棍上共有多少条不同的刻度线，在此基础上加1就是段数了。若按将木棍分成10等份的刻度线锯开，木棍有9条刻度线。在此木棍上加上将木棍分成12等份的11条刻度线，显然刻

10、度线有重复的，如5/10和6/12都是1/2。同样再加上将木棍分成15等份的刻度线，也是如此。所以，我们应该按容斥原理的方法来解决此问题。用容斥原理的那一个呢？想一想，被计数的事物有那几类？每一类的元素个数是多少？解答解一：(10,12,15)=60,设木棍60厘米60+10=6厘米，60+12=5厘米，60+15=4厘米10等分的为第一种刻度线，共101=9条12等分的为第二种刻度线，共121=11条15等分的为第三种刻度线，过151=14条第一种与第二种刻度线重合的(6,第一种与第三种刻度线重合的(6,第二种与第三种刻度线重合的(5,5)=30,60+301=21=1条4)=12,60+1

11、21=51=4条4)=20,60+201=31=2条三种刻度线重合的没有，(6、5、4)=60因此，共有刻度线9+11+14142=27条，木棍总共被锯成27+1=28段。解二：总长看成单位1分别分成10、12、15段。1/10与1/12的最小公倍数1/2,1/10与1/15的最小公倍数1/5,1/12与1/15的最小公倍数1/3,1/10,1/12和1/15的最小公倍数为1,有10+12+15(2+5+3)+1=28注：分数的的最大公约数和最小公倍数的求法，分母的最小公倍数作分母，分子的最大公约数作分子，这个数就是分数的最大公约数即|a,c=3cL分母的最大公约数作分母，d(b,d分子的最小

12、公倍数作分子，这个数就是分数的最小公倍数即-,-=郭。例如求3/4和bdb,dJ25/18的最大公约数和最小公倍数数，:4,18=36,(3,25)=13/4和25/18的最大公约数是1/36。(4,18)=2,3,25=75,3/4和25/18的最小公倍数是75/2。解三：10、12、15的最小公倍数是60,假设木棍就是长60,1、那么，分成10等份的每份6,刻度就是0,6,12,18,24,30,36,42,48,54,602、分成12等分的每份就是5,0,5,10,15,20,25,30,35,40,45,50,55,603、分成15等分的每份就是4,0,4,8,12,16,20,24,

13、28,32,36,40,44,48,52,56,604、把相同刻度的合并，就是有刻度如下：0,4,5,6,8,10,12,15,16,18,20,24,25,28,30,32,35,36,40,42,44,45,48,50,52,54,55,56,6013.在1到1000的自然数中，能被3或5整除的数共有多少个？不能被3或5整除的数共有多少个？分析：显然，这是一个重复计数问题（当然，如果不怕麻烦你可以分别去数3的倍数,5的倍数）。我们可以把“能被3或5整除的数”分别看成A类元素和B类元素，能“同时被3或5整除的数（15的倍数）”就是被重复计算的数，即“既是A类又是B类的元素”。求的是“A类或B

14、类元素个数”。我们还不能直接计算，必须先求出所需条件。1000+3=333,1,能被3整除的数有333个（想一想，这是为什么？）同理，可以求出其他的条件。解：设A是能被3整除的数，B为能被5整除的数，则A1等二333,B1等=2。0,AB=66aUb=AB-aHb=333+20066=467,1000-467=533欧拉问题欧拉的遗产问题：有一位父亲，临终前嘱咐他的儿子这样来分他的财产：第一个儿子分的100克郎和剩下财产的的土；第二个儿子分的200克郎和剩下财产的的，；第三个儿子分的300克郎和剩下财产的的第四个儿子分的400克郎和剩下财产的的2；,;按这种分发一直分下去，最后每个儿子得到的一

15、样多。问这位父亲共有几个儿子？每个儿子分得多少财产？这位父亲共留下多少财产？解法一：设这位父亲共有n个儿子，最后一个儿子为第n个儿子，则倒数第二个就是第n-1个儿子。第一个儿子分得的财产=100x因为每个儿子所分得财产数相等，即100（n1）+剩余的10=100n所以剩余财产的+剩下的,第二个儿子分得的财产=100x2+剩下的,1第三个儿子分得的财广=100X3+剩下的石第n1个儿子分得的财广=100x（n-1）+一，一1剩下的石，第n个儿子分得的财产=100n1=100n100(n-i)=100克郎。那么，剩余的财产为100二=1000克郎。1010一，、，1、因为这1000的石就是100克

16、郎给了第n-1个儿子，所以最后一个儿子分得1000-100=900克郎，从而得出这位父亲有900T00=9个儿子。共留下财产9009=8100克郎解法二：设这位父亲留下的的财产一共有n克郎，则第一个儿子所得的财产为119100+10(n-100)剩n100+(n-100)=而n-90；第二个儿子所得的财广为200.19n-90_200=_9_n+171剩n-90-.1n+171=-81n-26110|1010010100100第三个儿子所得的财产为3001如n_261_300=_81n243.910100100048181729乘Un-261-n243.9=n-504.9100|10001000191因为每个儿子所得的财广同样多，所以100+元(n100)=痂n+