集合论、组合论方法.ppt

专题8、集合论、组合论方法,集合法 对应法,计数法（加法原理、容斥原理、乘法原理） 抽屉原理 图论方法,组合论方法：,集合论方法：,容斥原理,设全集的子集A的基数用|A|表示,交集AB 用AB表示,则,抽屉原理,如果将n+1件物体放到n个抽屉里去，那么至少有一 个抽屉里放的物体不少于两件。,抽屉原理3,抽屉原理2,抽屉原理1,如果将多于mn件物体任意放到n个抽屉中去，那么至少有一个抽屉里放的物体不少于m+1件。,如果把无限个物体任意放到有限个抽屉中去，那么至少有一个抽屉中物体的个数是无限的。,从1 到500 中的整数中，不能被3整除，不 能被5整除的数有多少个？,【解】： 5003=166（余2） 5005=100 50015=33（余5） 500-166-100+33=267,一、集合论方法,A,B,33,133,67,例题 1,集合论方法,例2,在 88 的方格棋盘上取两个小方格，这两个小 方格构成的图形如下图1所示，它们有一个公共点. 问 有多少种不同的取法？,解： 772=98(种),图1,对应法,例题3,在50 名女学生中，穿的都是红裙子或者黄 裙子、白上衣或者花上衣. 已知：穿黄裙子的有31人 穿白上衣的有18人，穿红裙子和花上衣的有14人， 问穿黄裙子和白上衣的有多少人？,因此，穿黄裙子和白上衣的13。,32,5,19,18,13,例题4,在边长为 1 的正三角形中（包括边界上） 任意放入5个点，求证：这5个点中必须有两点， 它们之间的距离不大于 0.5 ？,【证明】: 依次连接这个三角形三边的中点，把边长为1 的三角形分成4个边长为0.5 的三角形 .把5个点放入三角形中，因为 54，所以至少有一个三角形内包括它的周边有两个或两个以上的点，这样的两个点之间的距离不会超过0.5 。,抽屉原理,例题5,在图中所示的 44 的方格中，有多少 个正方形？,二、组合论方法,42 + 32 + 22 + 12 = 30 （个）,加法原理,例题6,袋中有25个红球，24个蓝球，23个黄球，15 个白球及14个黑球，如果要确保摸出的球中有16个球 的颜色相同，至少要从袋中摸取多少个球？,【分析】：从最不利的情况考虑，开始摸出的 白球和黑球共 15+14=29，继续去摸，有摸出 红、黄、蓝色球个15个，这种情况下要保证摸 出的球中有16个颜色相同，必须再摸一个。,抽屉原理,15 + 14 + 3 151= 75 （个）,例题7,某班参加田径运动会各项目的数统计如下 参加径赛项目的有 15人，参加跳类项目的有 13人， 参加投掷类项目的有 14人； 既参加径赛、又参加跳类项目的有 4人， 既参加跳类、又参加投掷类项目的有 5人， 既参加径赛、又参加投掷类项目的有 6人; 三类项目都参加的有2人.,【解】： (151314) - (456) + 2 = 29 （人）,容斥原理,例8,在哥尼斯堡的普莱格尔河上有七座桥，将河中的两个岛B，与河岸，连接，问一个散步者能否从某一地点出发 ，不重复的走遍每一座桥，并返回出发地?,不可能,图论方法,某小学的一次画展上展出的画中，有16幅不 是六年级的，有15幅不是五年级的。并且已知 五、六年级共有25幅画参展，问一至四年级共 有多少幅画参展？,练习,【解】： （16+15）- 25 2 = 3,2. 如图，从 56 的方格中，取出一个由三个 方格组成的“L”形，问有多少种不同的取法？,【解】： 29+25+37 -（15+13+16）+7=54,3、 从 1， 3， 5， ，29， 31 这16个奇数中，任取9个数，证明：其中一定有两个数之和是 32.,证明： 抽屉原理,4. 已知三位数各位上数字的和等于10， 这样的三位数一共有多少个？,解： 百位上为 1 时有 10 个 百位上为 2 时有 9 个 百位上为 3 时有 8 个 . 百位上为 9 时有 2 个 10 + 9 + 8 + . + 3 + 2 = 54,5. 1818的小方格棋盘中，包含99个小方 格的正方形有多少个？ 6. 某年级有202人参加考试，满分100分，且 得分都是整数，总得分为10101分，求证：至 少有3人得分相同。 7. 10个苹果，每天至少吃1个，直到吃完，问 有多少种不同的吃苹果的方案？,抽屉原理,1010=100,29 = 512,