集合论、组合论方法.ppt

《集合论、组合论方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、专题8、集合论、组合论方法集合法对应法计数法（加法原理、容斥原理、乘法原理）抽屉原理图论方法组合论方法：集合论方法：容斥原理设全集Ω的子集A的基数用

2、A

3、表示,交集A∩B用AB表示,则抽屉原理如果将n+1件物体放到n个抽屉里去，那么至少有一个抽屉里放的物体不少于两件。抽屉原理3抽屉原理2抽屉原理1如果将多于m×n件物体任意放到n个抽屉中去，那么至少有一个抽屉里放的物体不少于m+1件。如果把无限个物体任意放到有限个抽屉中去，那么至少有一个抽屉中物体的个数是无限的。从1到500中的整数中，不能被3整除，

4、不能被5整除的数有多少个？【解】：500÷3=166（余2）500÷5=100500÷15=33（余5）500-166-100+33=267一、集合论方法AB3313367例题1集合论方法例2在8×8的方格棋盘上取两个小方格，这两个小方格构成的图形如下图1所示，它们有一个公共点.问有多少种不同的取法？解：7×7×2=98(种)图1对应法例题3在50名女学生中，穿的都是红裙子或者黄裙子、白上衣或者花上衣.已知：穿黄裙子的有31人穿白上衣的有18人，穿红裙子和花上衣的有14人，问穿黄裙子和白上衣的有多少

5、人？因此，穿黄裙子和白上衣的13。裙子上衣黄红合计花14白18合计3150325191813例题4在边长为1的正三角形中（包括边界上）任意放入5个点，求证：这5个点中必须有两点，它们之间的距离不大于0.5？【证明】:依次连接这个三角形三边的中点，把边长为1的三角形分成4个边长为0.5的三角形.把5个点放入三角形中，因为5>4，所以至少有一个三角形内包括它的周边有两个或两个以上的点，这样的两个点之间的距离不会超过0.5。抽屉原理例题5在图中所示的4×4的方格中，有多少个正方形？432133212221

6、1111二、组合论方法42+32+22+12=30（个）加法原理例题6袋中有25个红球，24个蓝球，23个黄球，15个白球及14个黑球，如果要确保摸出的球中有16个球的颜色相同，至少要从袋中摸取多少个球？【分析】：从最不利的情况考虑，开始摸出的白球和黑球共15+14=29，继续去摸，有摸出红、黄、蓝色球个15个，这种情况下要保证摸出的球中有16个颜色相同，必须再摸一个。抽屉原理15+14+3×15＋1=75（个）例题7某班参加田径运动会各项目的数统计如下参加径赛项目的有15人，参加跳类项目的有13人

7、，参加投掷类项目的有14人；既参加径赛、又参加跳类项目的有4人，既参加跳类、又参加投掷类项目的有5人，既参加径赛、又参加投掷类项目的有6人;三类项目都参加的有2人.【解】：(15＋13＋14)-(4＋5＋6)+2=29（人）容斥原理例8在哥尼斯堡的普莱格尔河上有七座桥，将河中的两个岛B，Ｄ与河岸Ａ，Ｃ连接，问一个散步者能否从某一地点出发，不重复的走遍每一座桥，并返回出发地?不可能图论方法某小学的一次画展上展出的画中，有16幅不是六年级的，有15幅不是五年级的。并且已知五、六年级共有25幅画参展，问一

8、至四年级共有多少幅画参展？练习【解】：[（16+15）-25]÷2=32.如图，从5×6的方格中，取出一个由三个方格组成的“L”形，问有多少种不同的取法？【解】：29+25+37-（15+13+16）+7=543、从1，3，5，…，29，31这16个奇数中，任取9个数，证明：其中一定有两个数之和是32.证明：抽屉原理4.已知三位数各位上数字的和等于10，这样的三位数一共有多少个？解：百位上为1时有10个百位上为2时有9个百位上为3时有8个.................百位上为9时有2个10+9+

9、8+...+3+2=545.18×18的小方格棋盘中，包含9×9个小方格的正方形有多少个？6.某年级有202人参加考试，满分100分，且得分都是整数，总得分为10101分，求证：至少有3人得分相同。7.10个苹果，每天至少吃1个，直到吃完，问有多少种不同的吃苹果的方案？抽屉原理10×10=10029=512