《组合数学课件.优秀PPT.ppt》由会员分享，可在线阅读，更多相关《组合数学课件.优秀PPT.ppt（58页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、组合数学组合数学西北工业高校附属中学焦和平1一概论一概论pp组合数学是一个古老而又年轻的数学分支。组合数学是一个古老而又年轻的数学分支。组合数学是一个古老而又年轻的数学分支。组合数学是一个古老而又年轻的数学分支。组合数学中的著名问题组合数学中的著名问题 地图着色问题地图着色问题地图着色问题地图着色问题中国邮差问题中国邮差问题中国邮差问题中国邮差问题船夫过河问题船夫过河问题船夫过河问题船夫过河问题任务安排问题任务安排问题任务安排问题任务安排问题2 组合数学主要探讨一组离散对象满足确组合数学主要探讨一组离散对象满足确定条件的支配，探讨的内容大致有四方面：定条件的支配，探讨的内容大致有四方面：pp1
2、 1存在性：有没有满足条件的支配？存在性：有没有满足条件的支配？存在性：有没有满足条件的支配？存在性：有没有满足条件的支配？pp2 2计数：满足条件的支配有多少种？计数：满足条件的支配有多少种？计数：满足条件的支配有多少种？计数：满足条件的支配有多少种？pp3 3构造：给出满足条件的支配的具体构造。构造：给出满足条件的支配的具体构造。构造：给出满足条件的支配的具体构造。构造：给出满足条件的支配的具体构造。pp4 4优化：在众多满足要求的支配中，按确定的标优化：在众多满足要求的支配中，按确定的标优化：在众多满足要求的支配中，按确定的标优化：在众多满足要求的支配中，按确定的标准挑出最优的支配。准挑
3、出最优的支配。准挑出最优的支配。准挑出最优的支配。3二、数学竞赛中的主要问题二、数学竞赛中的主要问题p1组合数学中的存在性问题组合数学中的存在性问题p11抽屉原理抽屉原理p 抽屉原理是一件简洁明白的事实：抽屉原理是一件简洁明白的事实：n+1个物品放入个物品放入n个抽屉中，则至少有一个抽屉，其个抽屉中，则至少有一个抽屉，其中有两个或更多的物品。中有两个或更多的物品。p 一般地：一般地：m个物品放入个物品放入n个抽屉中，则个抽屉中，则至少有一个抽屉不少于至少有一个抽屉不少于a个，其中个，其中4抽屉原理抽屉原理p一般地：m个物品放入n个抽屉中，则至少有一个抽屉不少于a个，其中5抽屉原理的变式抽屉原理
4、的变式抽屉原理的变式抽屉原理的变式6例例例例1 1单位圆内随意投放六点，求证至少有两点距离单位圆内随意投放六点，求证至少有两点距离单位圆内随意投放六点，求证至少有两点距离单位圆内随意投放六点，求证至少有两点距离不大于不大于不大于不大于1 1。pp解答：取六点中一点解答：取六点中一点解答：取六点中一点解答：取六点中一点A A A A，若若若若A A A A为单位圆的圆心，为单位圆的圆心，为单位圆的圆心，为单位圆的圆心，结论明显成立。结论明显成立。结论明显成立。结论明显成立。若若若若A A不是圆心不是圆心不是圆心不是圆心OO，则如图将，则如图将，则如图将，则如图将单位圆划分为六个中心角为单位圆划分
5、为六个中心角为单位圆划分为六个中心角为单位圆划分为六个中心角为6060度的扇形度的扇形度的扇形度的扇形,若阴影部若阴影部若阴影部若阴影部分内尚有六点中另一点分内尚有六点中另一点分内尚有六点中另一点分内尚有六点中另一点,则结论成立则结论成立则结论成立则结论成立.若阴影部分若阴影部分若阴影部分若阴影部分内没有六点中除内没有六点中除内没有六点中除内没有六点中除A A点外的点点外的点点外的点点外的点,则另五点则另五点则另五点则另五点(物品物品物品物品)在其在其在其在其余四个扇形余四个扇形余四个扇形余四个扇形(抽屉抽屉抽屉抽屉)中中中中,由抽屉原理由抽屉原理由抽屉原理由抽屉原理,必有某个扇形必有某个扇形
6、必有某个扇形必有某个扇形(抽屉抽屉抽屉抽屉)含有至少两个含有至少两个含有至少两个含有至少两个(物品物品物品物品),),故结论成立故结论成立故结论成立故结论成立.7例例例例2 2平面上任给平面上任给平面上任给平面上任给20052005个点，其中任两点距离均大于个点，其中任两点距离均大于个点，其中任两点距离均大于个点，其中任两点距离均大于 ，求证：必有，求证：必有，求证：必有，求证：必有223223个点彼此之间距离都不小于个点彼此之间距离都不小于个点彼此之间距离都不小于个点彼此之间距离都不小于2 2。pp解答解答解答解答:将平面按图分成九个将平面按图分成九个将平面按图分成九个将平面按图分成九个抽屉
7、抽屉抽屉抽屉,i,i,i,i号小方格全体为第号小方格全体为第号小方格全体为第号小方格全体为第i i i i个抽屉个抽屉个抽屉个抽屉.2005.2005.2005.2005个点分放在九个点分放在九个点分放在九个点分放在九个抽屉中个抽屉中个抽屉中个抽屉中,至少有一个抽屉至少有一个抽屉至少有一个抽屉至少有一个抽屉含有含有含有含有223223223223个点个点个点个点,由于由于由于由于2005200520052005个个个个点中任两点距离均大于点中任两点距离均大于点中任两点距离均大于点中任两点距离均大于 ,所以此所以此所以此所以此223223223223个点距离均大个点距离均大个点距离均大个点距离均
8、大于于于于,它们中没有两点属于同它们中没有两点属于同它们中没有两点属于同它们中没有两点属于同一小方格一小方格一小方格一小方格,而同号方格又不而同号方格又不而同号方格又不而同号方格又不在同一方格中的任两点距在同一方格中的任两点距在同一方格中的任两点距在同一方格中的任两点距离都不小于离都不小于离都不小于离都不小于2.2.2.2.1 1 1 12 2 2 2 3 3 3 31 1 1 12 2 2 2 3 3 3 31 1 1 12 2 2 2 3 3 3 34 4 4 45 5 5 5 6 6 6 64 4 4 45 5 5 5 6 6 6 64 4 4 45 5 5 5 6 6 6 67 7 7
9、 78 8 8 8 9 9 9 97 7 7 78 8 8 8 9 9 9 97 7 7 78 8 8 8 9 9 9 91 1 1 12 2 2 2 3 3 3 31 1 1 12 2 2 2 3 3 3 31 1 1 12 2 2 2 3 3 3 34 4 4 45 5 5 5 6 6 6 64 4 4 45 5 5 5 6 6 6 64 4 4 45 5 5 5 6 6 6 67 7 7 78 8 8 8 9 9 9 97 7 7 78 8 8 8 9 9 9 97 7 7 78 8 8 8 9 9 9 91 1 1 12 2 2 2 3 3 3 31 1 1 12 2 2 2 3 3
10、3 31 1 1 12 2 2 2 3 3 3 34 4 4 45 5 5 5 6 6 6 64 4 4 45 5 5 5 6 6 6 64 4 4 45 5 5 5 6 6 6 67 7 7 78 8 8 8 9 9 9 97 7 7 78 8 8 8 9 9 9 97 7 7 78 8 8 8 9 9 9 98pp本题牵扯到本题牵扯到本题牵扯到本题牵扯到A A A A的子集以及子集中各数之和两个探讨的子集以及子集中各数之和两个探讨的子集以及子集中各数之和两个探讨的子集以及子集中各数之和两个探讨对象，分别探讨它们有多少种。对象，分别探讨它们有多少种。对象，分别探讨它们有多少种。对象，分别探讨
11、它们有多少种。15151515元子集元子集元子集元子集A A A A的子集的子集的子集的子集共个共个共个共个 ，不空真子集共，不空真子集共，不空真子集共，不空真子集共 个，真子个，真子个，真子个，真子集中各数之和集中各数之和集中各数之和集中各数之和S S S S满足满足满足满足 =27979=27979=27979=27979，pp子集中各数和的种数不超过子集中各数和的种数不超过子集中各数和的种数不超过子集中各数和的种数不超过27979279792797927979，将，将，将，将32766327663276632766个子个子个子个子集放入集放入集放入集放入27979279792797927
12、979类和（抽屉）中，至少有一类和中含类和（抽屉）中，至少有一类和中含类和（抽屉）中，至少有一类和中含类和（抽屉）中，至少有一类和中含有两个子集，即有有两个子集，即有有两个子集，即有有两个子集，即有 B B B B与与与与C C C C中各数和相中各数和相中各数和相中各数和相等。若等。若等。若等。若 ，则结论成立；若，则结论成立；若，则结论成立；若，则结论成立；若 ，则以，则以，则以，则以pp 代替代替代替代替B B B B，C C C C，结论亦成立。，结论亦成立。，结论亦成立。，结论亦成立。9101 1 1 12 2 2 2 极端原理极端原理极端原理极端原理 利用探讨“极端”对象来实现问题
13、解决的解题方法称为用极端原理解题，常用的极端原理基于下述简洁的事实：1）由实数组成的有限集合，必有一个最大数，也有一个最小数。2）由自然数组成的任何非空集合中，必有一个最小的自然数。为了确定或否定组合数学问题的存在性，极端原理有着重大的作用。考察极端状况，探讨极端对象，无形中给问题的探讨增加了一个条件，所以更有利于问题的解决；用反证法时，探讨极端状况，使冲突更简洁暴露。11例例例例5 5 对平面上不全共线的对平面上不全共线的对平面上不全共线的对平面上不全共线的n n个点，求证：必存在一个点，求证：必存在一个点，求证：必存在一个点，求证：必存在一条恰好通过两点的直线。条恰好通过两点的直线。条恰好
14、通过两点的直线。条恰好通过两点的直线。解答：对解答：对解答：对解答：对n n个点中的任两点作连线个点中的任两点作连线个点中的任两点作连线个点中的任两点作连线mm，并取连线外的点并取连线外的点并取连线外的点并取连线外的点P P（必存在），（必存在），（必存在），（必存在），考察考察考察考察P P到到到到mm的距离的距离的距离的距离d d（P P，mm），），），），由于点为有限个，连线由于点为有限个，连线由于点为有限个，连线由于点为有限个，连线mm为有限条，为有限条，为有限条，为有限条，组合（组合（组合（组合（P P，mm）也只能有有限个，用极端原理设）也只能有有限个，用极端原理设）也只能有有限
15、个，用极端原理设）也只能有有限个，用极端原理设d d（P P，mm）为最小。）为最小。）为最小。）为最小。下面证明，下面证明，下面证明，下面证明，mm恰通过恰通过恰通过恰通过n n点中点中点中点中2 2点：点：点：点：过点过点过点过点P P作作作作mm的垂线，设垂足为的垂线，设垂足为的垂线，设垂足为的垂线，设垂足为A.A.若若若若mm上至少有上至少有上至少有上至少有n n点中的点中的点中的点中的3 3点，则至少有点，则至少有点，则至少有点，则至少有2 2点在点在点在点在A A的同侧，设的同侧，设的同侧，设的同侧，设B B，C C在在在在A A的同侧，且的同侧，且的同侧，且的同侧，且ABAC,A
16、B3n3）名乒乓球选手单打竞赛若干场后）名乒乓球选手单打竞赛若干场后）名乒乓球选手单打竞赛若干场后）名乒乓球选手单打竞赛若干场后,随意两随意两随意两随意两名选手已赛过的对手恰好都不完全相同名选手已赛过的对手恰好都不完全相同名选手已赛过的对手恰好都不完全相同名选手已赛过的对手恰好都不完全相同,求证求证求证求证:总可以从中去掉一名选手总可以从中去掉一名选手总可以从中去掉一名选手总可以从中去掉一名选手,使得余下的选手中使得余下的选手中使得余下的选手中使得余下的选手中,随意随意随意随意两个选手已赛过的对手仍旧都不完全相同两个选手已赛过的对手仍旧都不完全相同两个选手已赛过的对手仍旧都不完全相同两个选手已
17、赛过的对手仍旧都不完全相同.pp证明证明证明证明:若不存在可去选手若不存在可去选手若不存在可去选手若不存在可去选手,则则则则A A不是可去选手不是可去选手不是可去选手不是可去选手,去掉去掉去掉去掉A A后后后后.至至至至少存在选手少存在选手少存在选手少存在选手B B和和和和C,C,他们赛过的对手完全相同他们赛过的对手完全相同他们赛过的对手完全相同他们赛过的对手完全相同,故故故故B B和和和和C C确定确定确定确定没有赛过没有赛过没有赛过没有赛过;B;B和和和和C C中恰有一人中恰有一人中恰有一人中恰有一人(不妨设为不妨设为不妨设为不妨设为B)B)与与与与A A赛过赛过赛过赛过(否则否则否则否则
18、B B和和和和C C在未去掉在未去掉在未去掉在未去掉A A时赛过的对手完全相同时赛过的对手完全相同时赛过的对手完全相同时赛过的对手完全相同),),如图如图如图如图:同时同时同时同时C C也不是可去选手也不是可去选手也不是可去选手也不是可去选手,C,C代替代替代替代替A,A,如上述探讨可知如上述探讨可知如上述探讨可知如上述探讨可知,有有有有D D和和和和E,E,其中其中其中其中D D和和和和C C赛过赛过赛过赛过,E E和和和和C C未赛过未赛过未赛过未赛过,去掉去掉去掉去掉C C后后后后,D,D和和和和E E赛过的对手赛过的对手赛过的对手赛过的对手相同相同相同相同.D.D不会是不会是不会是不会
19、是A,B(A,B(因因因因A,BA,B与与与与C C未赛过未赛过未赛过未赛过),D),D与与与与B B赛过赛过赛过赛过(因因因因D D和和和和C C赛过赛过赛过赛过,去掉去掉去掉去掉A A后后后后,B,C,B,C对手相同对手相同对手相同对手相同).).去掉去掉去掉去掉C C后后后后,D,D和和和和E E赛过的对手相同赛过的对手相同赛过的对手相同赛过的对手相同.所以所以所以所以E E与与与与B B也赛过也赛过也赛过也赛过.141.3 构造法和不变性原理构造法和不变性原理pp通过干脆构作出解答来实现问题的解决称为用构通过干脆构作出解答来实现问题的解决称为用构通过干脆构作出解答来实现问题的解决称为用
20、构通过干脆构作出解答来实现问题的解决称为用构造法解题造法解题造法解题造法解题;对探讨问题分析其变更对探讨问题分析其变更对探讨问题分析其变更对探讨问题分析其变更,找出其中不变找出其中不变找出其中不变找出其中不变的量、不变的关系或不变的性质，抓住变中的的量、不变的关系或不变的性质，抓住变中的的量、不变的关系或不变的性质，抓住变中的的量、不变的关系或不变的性质，抓住变中的“不变不变不变不变”以促使问题的解决称为用不变性原理解题。以促使问题的解决称为用不变性原理解题。以促使问题的解决称为用不变性原理解题。以促使问题的解决称为用不变性原理解题。pp对于组合数学的存在性问题，常用构造法给出确对于组合数学的
21、存在性问题，常用构造法给出确对于组合数学的存在性问题，常用构造法给出确对于组合数学的存在性问题，常用构造法给出确定的答案，而不变性原理常可给出否定的结论。定的答案，而不变性原理常可给出否定的结论。定的答案，而不变性原理常可给出否定的结论。定的答案，而不变性原理常可给出否定的结论。不变性原理中最简洁、最好用的是奇偶性分析。不变性原理中最简洁、最好用的是奇偶性分析。不变性原理中最简洁、最好用的是奇偶性分析。不变性原理中最简洁、最好用的是奇偶性分析。15例例例例8 8 8 8 有一个凸有一个凸有一个凸有一个凸n n n n边形（边形（边形（边形（n4n4n4n4）全部顶点用红绿蓝三色）全部顶点用红绿
22、蓝三色）全部顶点用红绿蓝三色）全部顶点用红绿蓝三色染色，三种颜色都出现，且随意两相邻顶点不同色，染色，三种颜色都出现，且随意两相邻顶点不同色，染色，三种颜色都出现，且随意两相邻顶点不同色，染色，三种颜色都出现，且随意两相邻顶点不同色，求证：可用在求证：可用在求证：可用在求证：可用在n n n n边形内不交的对角线将多边形分成边形内不交的对角线将多边形分成边形内不交的对角线将多边形分成边形内不交的对角线将多边形分成n-2n-2n-2n-2个三角形，使每个三角形的三顶点都不同色。个三角形，使每个三角形的三顶点都不同色。个三角形，使每个三角形的三顶点都不同色。个三角形，使每个三角形的三顶点都不同色。
23、pp解答解答解答解答:若某种颜色的点只有一个若某种颜色的点只有一个若某种颜色的点只有一个若某种颜色的点只有一个,则易知结论成立则易知结论成立则易知结论成立则易知结论成立.若若若若每种颜色的顶点至少有二个每种颜色的顶点至少有二个每种颜色的顶点至少有二个每种颜色的顶点至少有二个,且相邻顶点颜色不同且相邻顶点颜色不同且相邻顶点颜色不同且相邻顶点颜色不同,则必有连续三个顶点则必有连续三个顶点则必有连续三个顶点则必有连续三个顶点k,k+1,k+2k,k+1,k+2恰为三色恰为三色恰为三色恰为三色,将此三角形将此三角形将此三角形将此三角形从凸从凸从凸从凸n n边形中割下边形中割下边形中割下边形中割下,那么
24、余下的是规模更小的凸多边形那么余下的是规模更小的凸多边形那么余下的是规模更小的凸多边形那么余下的是规模更小的凸多边形,若仍旧每种颜色的顶点至少有二个若仍旧每种颜色的顶点至少有二个若仍旧每种颜色的顶点至少有二个若仍旧每种颜色的顶点至少有二个,可接着割去一个三色三角形可接着割去一个三色三角形可接着割去一个三色三角形可接着割去一个三色三角形,最终可得某种颜色只有一个最终可得某种颜色只有一个最终可得某种颜色只有一个最终可得某种颜色只有一个,可以如图给出分划可以如图给出分划可以如图给出分划可以如图给出分划.16例例例例9 9 能否把能否把能否把能否把1 1，1 1，2 2，2 2，3 3，3 3，200
25、52005，20052005这这这这40104010个数排成一列，使得两个个数排成一列，使得两个个数排成一列，使得两个个数排成一列，使得两个1 1之间有一个数，两个之间有一个数，两个之间有一个数，两个之间有一个数，两个2 2之间有二个数，之间有二个数，之间有二个数，之间有二个数，两个，两个，两个，两个20052005之间有之间有之间有之间有20052005个数个数个数个数.17p证明：充分性：可用构造法作出，如图，正方形可剖分成6个钝角三角形，又任一钝角三角形总可分成两个钝角三角形。p 必要性：先找出随意钝角三角形剖分中不变的关系。p 对剖分法的剖分点进行分类：在正方形边界上的剖分点或在某一剖
26、分三角形边上但不是该三角形顶点的内剖分点称为第一类剖分点；不在三角形边上的内剖分点称为其次类剖分点。如图中F，G，H为第一类剖分点，E为其次类剖分点。1819（2）随意凸四边形（各种情形）可剖分成钝角三角形（锐角三角形）的充要条件又各是什么？202组合数学中的计数问题组合数学中的计数问题p21 加法原理和乘法原理加法原理和乘法原理p加法原理：设事务加法原理：设事务A有有m种选取方式，事务种选取方式，事务B有有n种选取种选取方式，事务方式，事务A和事务和事务B没有共同选取方式，则选没有共同选取方式，则选A或选或选B有有m+n种方式。种方式。p乘法原理：设事务乘法原理：设事务A有有m种选取方式，事
27、务种选取方式，事务B有有n种选取种选取方式，则选取方式，则选取A以后再选以后再选B共有共有mn种方式。种方式。p 2122例例例例12.12.三个数三个数三个数三个数14471447、10051005、12311231有很多相同之处：它有很多相同之处：它有很多相同之处：它有很多相同之处：它们都有四位数，最高位都是们都有四位数，最高位都是们都有四位数，最高位都是们都有四位数，最高位都是1 1，都恰有两个相同的数，都恰有两个相同的数，都恰有两个相同的数，都恰有两个相同的数字，一共有多少个这样的数。字，一共有多少个这样的数。字，一共有多少个这样的数。字，一共有多少个这样的数。232.2 映射与计数映
28、射与计数24例例例例13.13.在数列在数列在数列在数列1 1，9 9，8181，9200592005中删去最高位是中删去最高位是中删去最高位是中删去最高位是9 9的项，问余下的数列有多少项？的项，问余下的数列有多少项？的项，问余下的数列有多少项？的项，问余下的数列有多少项？25例例14.14.圆周上有圆周上有n n个点每两个点连一线段，假设任三个点每两个点连一线段，假设任三条线段在圆内不共点，于是三条两两相交的线段构条线段在圆内不共点，于是三条两两相交的线段构成一个三角形，试求这些三角形的个数？成一个三角形，试求这些三角形的个数？26例例例例15.15.设凸设凸设凸设凸n n边形的随意边形的
29、随意边形的随意边形的随意3 3条对角线不相交于行内一点，条对角线不相交于行内一点，条对角线不相交于行内一点，条对角线不相交于行内一点，求它的对角线在行内的交点总数。求它的对角线在行内的交点总数。求它的对角线在行内的交点总数。求它的对角线在行内的交点总数。27例例例例16.16.今有编号为今有编号为今有编号为今有编号为1 1，2 2，1010的钥匙与编号为的钥匙与编号为的钥匙与编号为的钥匙与编号为1 1，2 2，1010的箱的箱的箱的箱子，每把钥匙只能打开与之号数相同的箱子，现将全部钥匙都放子，每把钥匙只能打开与之号数相同的箱子，现将全部钥匙都放子，每把钥匙只能打开与之号数相同的箱子，现将全部钥
30、匙都放子，每把钥匙只能打开与之号数相同的箱子，现将全部钥匙都放进这些箱子中，每只箱子放一把，然后锁上，那么至少有多少种进这些箱子中，每只箱子放一把，然后锁上，那么至少有多少种进这些箱子中，每只箱子放一把，然后锁上，那么至少有多少种进这些箱子中，每只箱子放一把，然后锁上，那么至少有多少种不同的放法，使得至少要撬开两只箱子才能将箱子全部打开？若不同的放法，使得至少要撬开两只箱子才能将箱子全部打开？若不同的放法，使得至少要撬开两只箱子才能将箱子全部打开？若不同的放法，使得至少要撬开两只箱子才能将箱子全部打开？若恰撬开两只箱子才能将箱子全部打开，又有多少放法？恰撬开两只箱子才能将箱子全部打开，又有多少
31、放法？恰撬开两只箱子才能将箱子全部打开，又有多少放法？恰撬开两只箱子才能将箱子全部打开，又有多少放法？28 证明：我们将不定方程证明：我们将不定方程证明：我们将不定方程证明：我们将不定方程 的任意一组非的任意一组非的任意一组非的任意一组非负整数解负整数解负整数解负整数解 对应于一个由对应于一个由对应于一个由对应于一个由n n个圆圈个圆圈个圆圈个圆圈“”“”，k-1k-1个竖线个竖线个竖线个竖线“|”“|”组成的如下排列：组成的如下排列：组成的如下排列：组成的如下排列：|，其，其，其，其中第一根竖线中第一根竖线中第一根竖线中第一根竖线“|”“|”的左侧恰有的左侧恰有的左侧恰有的左侧恰有x1x1个
32、圆圈个圆圈个圆圈个圆圈“”“”；第；第；第；第i-1i-1根根根根竖线竖线竖线竖线“|”“|”与第与第与第与第i i根竖线根竖线根竖线根竖线“|”“|”之间恰有之间恰有之间恰有之间恰有xixi个圆圈个圆圈个圆圈个圆圈“”“”；第第第第i-1i-1根竖线根竖线根竖线根竖线“|”“|”的右侧恰有的右侧恰有的右侧恰有的右侧恰有xkxk个圆圈个圆圈个圆圈个圆圈“”“”。显然，不。显然，不。显然，不。显然，不定方程的不同的解对应于不同的排列，且每一个这样的对定方程的不同的解对应于不同的排列，且每一个这样的对定方程的不同的解对应于不同的排列，且每一个这样的对定方程的不同的解对应于不同的排列，且每一个这样的
33、对应于不定方程的一组非负整数解，因此，我们建立的对应应于不定方程的一组非负整数解，因此，我们建立的对应应于不定方程的一组非负整数解，因此，我们建立的对应应于不定方程的一组非负整数解，因此，我们建立的对应是一个双射。是一个双射。是一个双射。是一个双射。又因为由又因为由又因为由又因为由n n个圆圈个圆圈个圆圈个圆圈“”“”及及及及k-1k-1根竖线根竖线根竖线根竖线“|”“|”组成的组成的组成的组成的n+k-1n+k-1个个个个元素的全排列数为元素的全排列数为元素的全排列数为元素的全排列数为 ，所以，不定方程，所以，不定方程，所以，不定方程，所以，不定方程 的一组非负整数解组的组数为的一组非负整数
34、解组的组数为的一组非负整数解组的组数为的一组非负整数解组的组数为 。2923容斥原理容斥原理30例例18.18.一个学校只有3门课程：数学、物理、化学，已知修这3门课程的学生分别有170、130、120人；同时修数学、物理两门课的学生有45人；同时修数学、化学两门课的学生有20人；同时修物理、化学两门课的学生有22人；同时修三门课的学生有3人。问这个学校共有多少学生？31例例19.求a，b，c，d，e，f这六个字母的全排列中不允许出现ace和df图像的排列数。3233例例例例21.21.求由求由求由求由a a，b b，c c，d d这这这这4 4个字符构成的个字符构成的个字符构成的个字符构成的
35、n n位数字串中，位数字串中，位数字串中，位数字串中，a a，b b，c c至少出现一次的符号串的数目。至少出现一次的符号串的数目。至少出现一次的符号串的数目。至少出现一次的符号串的数目。3435同理3637练习题1给定2003个集合，每个集合都恰含有44个元素，并且每两个集合都恰有一个公共元素，试求这2003个集合的并集中有多少个元素？2平面内给定200个不同的点，证明：其中距离为单位长的点对数小于2050。3以正n边形的顶点为顶点的梯形共有多少个？38杂杂 题题39 例例1 1 运动会开了运动会开了n n天（天（n1n1）,共发出共发出m m个奖牌个奖牌,第一天发出第一天发出1 1个加余下
36、奖牌的个加余下奖牌的,其次天发出其次天发出2 2个加余下奖牌的个加余下奖牌的,如此接如此接着下去着下去,最终最终,第第n n天发出天发出n n个奖牌恰无剩余个奖牌恰无剩余.问运动会共开问运动会共开了几天了几天?共发出多少个奖牌共发出多少个奖牌?404142例例2.几个人在一起几个人在一起几个人在一起几个人在一起,使得其中存在有相同生日的概率使得其中存在有相同生日的概率使得其中存在有相同生日的概率使得其中存在有相同生日的概率至少为二分之一至少为二分之一至少为二分之一至少为二分之一.即即即即23232323人中人中人中人中,至少有一至少有一至少有一至少有一对对对对生日相同的概率超生日相同的概率超生
37、日相同的概率超生日相同的概率超过过过过二分之一二分之一二分之一二分之一 43例例例例3.3.甲乙二人玩，在黑板上写数的游戏，规则是二人轮番甲乙二人玩，在黑板上写数的游戏，规则是二人轮番甲乙二人玩，在黑板上写数的游戏，规则是二人轮番甲乙二人玩，在黑板上写数的游戏，规则是二人轮番在黑板上写一个不超过在黑板上写一个不超过在黑板上写一个不超过在黑板上写一个不超过p p的自然数，但禁止再写出黑板上已的自然数，但禁止再写出黑板上已的自然数，但禁止再写出黑板上已的自然数，但禁止再写出黑板上已有的因数。甲先起先写，轮到谁写而无法写出时就告负。有的因数。甲先起先写，轮到谁写而无法写出时就告负。有的因数。甲先起先
38、写，轮到谁写而无法写出时就告负。有的因数。甲先起先写，轮到谁写而无法写出时就告负。（1 1）当）当）当）当p=10p=10时，游戏者中谁有获胜策略？时，游戏者中谁有获胜策略？时，游戏者中谁有获胜策略？时，游戏者中谁有获胜策略？（2 2）当）当）当）当p=1000p=1000时，游戏者中谁有获胜策略？时，游戏者中谁有获胜策略？时，游戏者中谁有获胜策略？时，游戏者中谁有获胜策略？解答：（解答：（解答：（解答：（1 1）甲有获胜策略，他可以先写）甲有获胜策略，他可以先写）甲有获胜策略，他可以先写）甲有获胜策略，他可以先写6 6，于是按规则不，于是按规则不，于是按规则不，于是按规则不能再写能再写能再写
39、能再写1 1，2 2，3 3。其余。其余。其余。其余6 6个数分成个数分成个数分成个数分成3 3组：（组：（组：（组：（4 4，5 5）（）（）（）（7 7，9 9）（8 8，1010）无论乙写哪一个，甲就写同组的另一个。）无论乙写哪一个，甲就写同组的另一个。）无论乙写哪一个，甲就写同组的另一个。）无论乙写哪一个，甲就写同组的另一个。（2 2）考察写数原则相同但取数范围不是由）考察写数原则相同但取数范围不是由）考察写数原则相同但取数范围不是由）考察写数原则相同但取数范围不是由1 1到到到到10001000而是由而是由而是由而是由2 2到到到到10001000的这个游戏。假如这个游戏先写者有必胜
40、策略，的这个游戏。假如这个游戏先写者有必胜策略，的这个游戏。假如这个游戏先写者有必胜策略，的这个游戏。假如这个游戏先写者有必胜策略，那么甲对原来的游戏只要照搬就行了。因为甲写下一个自那么甲对原来的游戏只要照搬就行了。因为甲写下一个自那么甲对原来的游戏只要照搬就行了。因为甲写下一个自那么甲对原来的游戏只要照搬就行了。因为甲写下一个自然数后，乙是不能写然数后，乙是不能写然数后，乙是不能写然数后，乙是不能写1 1的。假如新游戏先写数的人没有获的。假如新游戏先写数的人没有获的。假如新游戏先写数的人没有获的。假如新游戏先写数的人没有获胜策略，即他只能告负，那么甲在原游戏中可以先写胜策略，即他只能告负，那
41、么甲在原游戏中可以先写胜策略，即他只能告负，那么甲在原游戏中可以先写胜策略，即他只能告负，那么甲在原游戏中可以先写1 1，从而将失败留给了乙。可见，甲总有获胜策略。从而将失败留给了乙。可见，甲总有获胜策略。从而将失败留给了乙。可见，甲总有获胜策略。从而将失败留给了乙。可见，甲总有获胜策略。44p例例4.甲乙两人在画有个方格的正方形场地上做游甲乙两人在画有个方格的正方形场地上做游戏戏:甲先在场地中心画一个星号甲先在场地中心画一个星号,乙则在放有星号乙则在放有星号的格子四周的的格子四周的8个格子中任选个格子中任选1个方格画一个圆圈个方格画一个圆圈.然后甲再在某个与已画有标记的格子挨着的空格然后甲再
42、在某个与已画有标记的格子挨着的空格中画一个星号中画一个星号,并一干脆着下去并一干脆着下去.假如甲成功地将假如甲成功地将星号画入场地四角的任何一个角上的方格中星号画入场地四角的任何一个角上的方格中,就算就算他获胜他获胜.求证求证:不论乙怎么做不论乙怎么做,甲总可以获胜甲总可以获胜.45例例5.5.在33的正方形表格中填上如图所示的9个数字,将该表进行如下操作:每次操作是对表中相邻两数同时加上一个数(相邻是指有公共边的两小格),问能否经过若干次操作使得（1）表格中各数均为0；（2）表格中四个角的数为1,其余均为0.03267049546解答:(1)能够得到.事实上经过5次操作即可.03267049
43、50106704950 1 06 7 00 5 501067000001001000000000000047(2)考虑这种操作的一般形式:abcdefghk为此,设表格中第一行的数从左到右为a,b,c.其次行的数从左到右为d,e,f.第三行的数从左到右为g,h,k.按操作规则,随意相邻的数都加同一个数,因此操作的每一步均不变更S=(a+c+e+g+k)-(b+d+h+f)的值.而表格的初始状态S的值为S=(0+2+7+4+5)-(3+6+9+0)=0要达到的状态S的值为S=(1+1+0+1+1)-(0+0+0+0)=4因此不能实现满足题目要求的操作.a b cd e fg h k48例例6.凸
44、凸n边边形的随意形的随意3条条对对角角线线不相交于形内一点，不相交于形内一点，求求这这些些对对角角线线将凸将凸n边边形分成的区域的个数形分成的区域的个数.4950515253例例7.已知平面上有4条直线,其中任何两条都相交,任何三条都不交于一点,于是在每条直线上都交得3个交点,它们从直线上截出两条线段,共得到8条线段.问这8条线段的长度能否分别为 (1)1,2,3,4,5,6,7,8?(2)互不相同的自然数?54（2）8条线段的长度可以是互不相同的自然数，见图。55例例8.一袋花生共一袋花生共1988颗颗,一只猴子第一天拿走一颗花一只猴子第一天拿走一颗花生生,从其次天起从其次天起,每天拿走的都
45、是以前各天的总和每天拿走的都是以前各天的总和.假假如到某天袋里的花生少于已拿走的总数时如到某天袋里的花生少于已拿走的总数时,这一天它这一天它又从拿走一颗起先又从拿走一颗起先,按原定的规律进行新的一轮按原定的规律进行新的一轮.如此如此接着下去接着下去,那么这袋花生被猴子拿光时是第几天那么这袋花生被猴子拿光时是第几天?56练习题18个小圆片分别涂有4种颜色：红、蓝、白、黑各两个。甲乙两人轮番把圆片放到正方体的顶点上，在全部的圆片都放完之后，假如正方体上存在一条棱，其两个端点所放的圆片同色，则甲获胜，否则乙获胜。问在这个游戏中睡有必胜策略。2.在黑板上写有3个整数,然后擦去其中一个,并代之以剩下的两数之和与1的差.重复这个步骤若干次后,黑板上的数变成了17,1967,1983,问起先时黑板上所写的数能否是下列数组:(1)2,2,2 (2)3,3,357路要自己走路要自己走 关要自己闯关要自己闯祝同学们取得好成果祝同学们取得好成果58