第六讲容斥原理.doc

第六讲容斥原理包含与排除一、什么是容斥原理【例1】在1至300的自然数中，（1）能被6整除或能被7整除的数有_个；（2）既不能被6整除又不能被7整除的数有_个。【例2】在1至100的自然数中，（1）能被2或3或5整除的数有_个；（2）不能被2整除，也不能被3整，又不能被5整除的数有_个。【容斥原理1】如果有S个东西，其中具有性质A的有a个，具有性质B的有b个，既具有性质A又具有性质B的有c个，那么具有性质A或性质B的（即A+B）有a+b-c个，既不具有性质A也不具有性质B的有S（a+b-c）个。【容斥原理2】如果有S个东西，其中具有性质A的有a个，具有性质B的有b个，具有性质C的有c个，既具有性质A又具有性质B的有d个，既具有性质A又具有性质C的有e个，既具有性质B又具有性质C的有f个，既具有性质A又具有性质B还具有性质C的有g个，既不具有性质A也不具有性质B也不具有性质C的有s（a+b+c-d-e-f+g）个。二、解决包含与排除的一般方法或步骤（1）利用上面公式（20）通过画图【例3】把1至7的自然数填入圆中，使每条直线上3个数的和都等于12。【例4】一张扑克牌面积49平方厘米，两张扑克牌在桌上覆盖的面积是多少？练习：1、某老师工作至今，数学课上了18年，信息技术课上了7年，其中既上数学课又上信息技术课6年，另有一年只做管理工作没上课，请问：这位老师共工作了几年？2、我班有54名学生。其中26人参加了数学竞赛，18人参加了英语竞赛，有7人既参加了数学竞赛又参加了英语竞赛。那么（1）只参加数学竞赛的有多少人？（2）参加竞赛的一共多少人？（3）没有参加竞赛的共有多少人？3、某班有60人爱好数学，50人爱好语文，47人爱好体育，30人既爱好数学又爱好语文，20人既爱好语文又爱好体育，35人既爱好体育又爱好数学，15人三方面都爱好。那么，三方面至少爱好一项的有多少人？其中只爱好数学一项的有多少人？【例5】桌面上有3张纸片。圆形纸片面积是26平方厘米，方形纸片面积是22平方厘米，三角形纸片面积是16平方厘米。圆形与方形纸片重叠部分是7平方厘米，圆形与三角形纸片重叠部分是6平方厘米，方形与三角形纸片重叠部分是5平方厘米，3种纸片的公共部分是2平方厘米。3种纸片一共盖住桌面的面积是多少？练习：1、在1到10000的自然数中，能被5或7整除的数有多少个？不能被5也不能被7整除的数又有多少个？ABC2、某班有学生42人，其中参加运动队的有26人，参加文艺队的有22人，全班每人至少参加一个队。这个班两队都参加的有多少人？3、设A表示30的所有质因数，B表示42的所有质因数，C表示210的所有质因数，D表示6的所有质因数。求（1）A与C的公共部分的数；（2）B与C的公共部分的数；（3）A、B、C、D的公共部分的数；（4）A、B、C、D一共有多少个数？4、如图，A、B、C分别代表面积为55、64、37的3张不同形状的纸片，它们放在一起盖住桌面的面积为117，且A与B、B与C、C与A公共部分面积分别为17、14、13，求A、B、C三张纸片公共部分（即阴影部分）的面积。第七讲抽屉原则【实验】在平面上任意画六点，每三点都不在一条直线上。把每两点连接起来，再用红蓝两色任意地涂抹，同学之间相互比较，多做几次看看，有什么发现？这说明，在任意性下其实往往藏有某种必然性！一、什么是抽屉原则【抽屉原则一】把n+1个东西，任意分放到n个抽屉里，那么必有一个抽屉里至少有 个东西。【抽屉原则二】把m个东西，任意地分放到n个抽屉里，必有一个抽屉里至少放有K个东西。其中(当n整除m时)或（当n不整除m时）。反之，可得【抽屉原则三】把m个东西，任意分到n个抽屉，必有一只抽屉里至多有个东西。抽屉原则实质性思想是：把一些东西分成若干份，那么必有一份不少于平均数，也必有一份不多于平均数。【利用抽屉原则解决问题的关键】寻找或构造恰当的抽屉及确定要分到抽屉里去的东西。【例1】一年365天，现有366人，则其中至少有两个人生日相同。【例2】抽屉里有10双手套，从中取11只出来，其中至少有两只是完整配对的。【例3】试证：任意五个自然数中，必有两个数的差是4的倍数。【例4】某校有2030名学生。老师让每个同学用2、0、0、3这四个（1）任意写出一个四位数，则至少有_个人写出的四位数相同。（2）任意写出一个自然数（一位数、两位数、三位数、四位数均可），则至少有 人写出的数相同。【例5】再证：若是自然数1、2、3、9的一个任意的排列，则必为偶数。【推广例5】任给n个自然数，再将它们重新排列为，那么必是偶数。【练习】1、设a1、a2、a3为三个任意的整数，b1、b2、b3为a1、a2、a3的任意排列。求证：a1b1、a2b2、a3b3中至少有一个是偶数。2、证明：从16个自然数中，一定可以找出两个数，它们的差是15的倍数。3、把一个最简分数写成小数形式时，必是有限小数或是无限循环小数，试证之。利用抽屉原则解决问题的关键，也是难点之所在，就是巧妙地构造恰当的抽屉。【例6】学校组织高三年级的55位同学去参观清华大学、北京大学及故宫，规定每人至少去一处，至多去两处，那么至少有几个人参观的地方完全相同？【例7】在边长为1的正方形内，任意给定13个点。求证：必有4点，以这4点为顶点的四边形的面积不超过（若四点共线，则认为这个四边形的面积为零）【例8】把125本书分给某班同学，已知其中有人分到4本，问该班最少有多少人？【练习】1、在边长为1的正三角形内有5个点，证明其中有一对点，它们的距离不超过0.5。2、在边长为1的线段上任意给定2000个点。试证：其中必有两点，它们之间的距离不大于。3、证明实验的结果：有6个点，任意3点不在一条直线上，每两点用一条红色或蓝色线段联结，那么这些线段围成的三角形中，至少有2个单色三角形（即三边同色）4、某班学生每人都订阅了少年报、中国文史报、中学生数学中的一种或几种。已知他们中至少有4个人订的刊物完全相同，问该班最少有多少人？第八讲统筹与优化一、什么是统筹与优化从田忌赛马与烧水泡茶说起完成一件事，怎样规划安排，才能用最小的投入、最快的速度，取得最好的效果，这就是统筹优化问题。二、实例【故事】解放军智越沙漠车场A 6名B 5名C 7名D 3名E 4名F 3名【例1】某车场每天有3辆车子经过A、B、C、D、E、F6个货站进行循环运输。每辆车在A站装货，需装卸工6名；在B站卸货，需装卸工5名；在C站装货，需装卸工7名；在D站卸货，需装卸工3名；在E站装货，需装卸工4名；在F站卸货，需装卸工3名。如果每站按装卸需要的人数安排固定工人，则需要装卸工30人。为了节约工人可以安排一些工人跟车走，一些工人固定在各站，请问如何安排才能用最少的装卸工人完成装卸任务？【解】（1）如果各站都不留工人，每辆车跟工人7人，三辆车共21人，这样，这三辆车开到各站，都能满足装卸的需要，这种安排方法，节约7人。（2）如果每辆车安排跟车工人6人，C站保留1人，这样每辆车到站后，也都能满足装卸需要，但总工人数为63+1=19人，节约11人。（3）如果每辆车安排跟车工人5人，A站留1人，C站保留2人，这样每辆车到站后，也都能满足装卸需要，但总工人数为53+1+2=18人，节约12人；（4）如果每辆车安排跟车工人4人，A站留2人，B站留1人，C站保留3人，F站留1人，这样每辆车到站后，也都能满足装卸需要，但总工人数为43+2+1+3+1=19人，比方法（3）多1人。（5）同理，如果每辆车安排跟车少于4人，则需工人总数都比18人多。因此，本题的最好安排方法是第（3）种，最少需要工人18人。购票人上每人门票价13元11元9元【例2】乐园报名，怎样交费才划算？【例3】（1995年北京市初二年级数学竞赛题）团体购买公园门票，标价如下：今有甲乙两个旅游团，若分别购买门票，两团总计应付门票费1314元，若两团合在一起作为一个团体购票，总计支付门票费1008元，问两个旅游团各有多少人？【练习】1、27只乒乓球中有一只是次品，次品比正品轻一点，现有一天平，最少称几次，一定能把次品找到？2、有一个80人的旅游团，其中男50人，女30人，他们住的旅馆有11人、7人和5人的三种房间，男、女分住不同房间，他们至少要住多少个房间？3、现有10箱手表，已知9箱是全钢的，1箱是半钢的（外表区分不出来），全钢重20克，半钢的重18克，能不能只称一次就把这箱半钢表从中挑出来？4、有一桶装着8千克水，另有能装5千克和3千克的空瓶各一个，用这三种容器至少要倒多少次，才能将8千克水平分成两个4千克？【问题故事】我国古代曾流行“斗蟋蟀”游戏，有人还用斗蟋蟀的胜败进行赌博。这样就有了买卖蟋蟀的交易。一位老人把抓到的90只蟋蟀，分给三个儿子，让他们到市场卖掉。老人为了考考三个儿子的智力，对他们说：“我这儿有90只蟋蟀，你们拿去卖掉。老大拿50只，老二拿30只，老三拿10只。卖价高低你们自己定