数学竞赛之组合数学选讲课件

数学竞赛之组合数学选讲11、获得的成功越大，就越令人高兴。野心是使人勤奋的原因，节制使人枯萎。12、不问收获，只问耕耘。如同种树，先有根茎，再有枝叶，尔后花实，好好劳动，不要想太多，那样只会使人胆孝懒惰，因为不实践，甚至不接触社会，难道你是野人。(名言网)13、不怕，不悔(虽然只有四个字，但常看常新。14、我在心里默默地为每一个人祝福。我爱自己，我用清洁与节制来珍惜我的身体，我用智慧和知识充实我的头脑。15、这世上的一切都借希望而完成。农夫不会播下一粒玉米，如果他不曾希望它长成种籽；单身汉不会娶妻，如果他不曾希望有小孩；商人或手艺人不会工作，如果他不曾希望因此而有收益。-马钉路德。抽屉原理抽屉原理p一般地：m个物品放入n个抽屉中，则至少有一个抽屉不少于a个，其中6抽屉原理的变式抽屉原理的变式抽屉原理的变式抽屉原理的变式7例例例例1 1单位圆内任意投放六点，求证至少有两点距离单位圆内任意投放六点，求证至少有两点距离单位圆内任意投放六点，求证至少有两点距离单位圆内任意投放六点，求证至少有两点距离不大于不大于不大于不大于1 1。pp解答：取六点中一点解答：取六点中一点解答：取六点中一点解答：取六点中一点A A A A，若若若若A A A A为单位圆的圆心，为单位圆的圆心，为单位圆的圆心，为单位圆的圆心，结论显然成立。结论显然成立。结论显然成立。结论显然成立。若若若若A A不是圆心不是圆心不是圆心不是圆心OO，则如图将，则如图将，则如图将，则如图将单位圆划分为六个中心角为单位圆划分为六个中心角为单位圆划分为六个中心角为单位圆划分为六个中心角为6060度的扇形度的扇形度的扇形度的扇形,若阴影部若阴影部若阴影部若阴影部分内尚有六点中另一点分内尚有六点中另一点分内尚有六点中另一点分内尚有六点中另一点,则结论成立则结论成立则结论成立则结论成立.若阴影部分若阴影部分若阴影部分若阴影部分内没有六点中除内没有六点中除内没有六点中除内没有六点中除A A点外的点点外的点点外的点点外的点,则另五点则另五点则另五点则另五点(物品物品物品物品)在其余在其余在其余在其余四个扇形四个扇形四个扇形四个扇形(抽屉抽屉抽屉抽屉)中中中中,由抽屉原理由抽屉原理由抽屉原理由抽屉原理,必有某个扇形必有某个扇形必有某个扇形必有某个扇形(抽屉抽屉抽屉抽屉)含有至少两个含有至少两个含有至少两个含有至少两个(物品物品物品物品),),故结论成立故结论成立故结论成立故结论成立.8例例例例2 2平面上任给平面上任给平面上任给平面上任给20052005个点，其中任两点距离均大于个点，其中任两点距离均大于个点，其中任两点距离均大于个点，其中任两点距离均大于，求证：必有，求证：必有，求证：必有，求证：必有223223个点彼此之间距离都不小于个点彼此之间距离都不小于个点彼此之间距离都不小于个点彼此之间距离都不小于2 2。pp解答解答解答解答:将平面按图分成九个将平面按图分成九个将平面按图分成九个将平面按图分成九个抽屉抽屉抽屉抽屉,i,i,i,i号小方格全体为第号小方格全体为第号小方格全体为第号小方格全体为第i i i i个抽屉个抽屉个抽屉个抽屉.2005.2005.2005.2005个点分放在九个点分放在九个点分放在九个点分放在九个抽屉中个抽屉中个抽屉中个抽屉中,至少有一个抽屉至少有一个抽屉至少有一个抽屉至少有一个抽屉含有含有含有含有223223223223个点个点个点个点,由于由于由于由于2005200520052005个个个个点中任两点距离均大于点中任两点距离均大于点中任两点距离均大于点中任两点距离均大于 ,所以此所以此所以此所以此223223223223个点距离均大个点距离均大个点距离均大个点距离均大于于于于,它们中没有两点属于同它们中没有两点属于同它们中没有两点属于同它们中没有两点属于同一小方格一小方格一小方格一小方格,而同号方格又不而同号方格又不而同号方格又不而同号方格又不在同一方格中的任两点距在同一方格中的任两点距在同一方格中的任两点距在同一方格中的任两点距离都不小于离都不小于离都不小于离都不小于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 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 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 99pp本题牵扯到本题牵扯到本题牵扯到本题牵扯到A A A A的子集以及子集中各数之和两个讨论的子集以及子集中各数之和两个讨论的子集以及子集中各数之和两个讨论的子集以及子集中各数之和两个讨论对象，分别讨论它们有多少种。对象，分别讨论它们有多少种。对象，分别讨论它们有多少种。对象，分别讨论它们有多少种。15151515元子集元子集元子集元子集A A A A的子集的子集的子集的子集共个共个共个共个 ，不空真子集共，不空真子集共，不空真子集共，不空真子集共 个，真子个，真子个，真子个，真子集中各数之和集中各数之和集中各数之和集中各数之和S S S S满足满足满足满足 =27979=27979=27979=27979，pp子集中各数和的种数不超过子集中各数和的种数不超过子集中各数和的种数不超过子集中各数和的种数不超过27979279792797927979，将，将，将，将32766327663276632766个子个子个子个子集放入集放入集放入集放入27979279792797927979类和（抽屉）中，至少有一类和中含类和（抽屉）中，至少有一类和中含类和（抽屉）中，至少有一类和中含类和（抽屉）中，至少有一类和中含有两个子集，即有有两个子集，即有有两个子集，即有有两个子集，即有 B B B B与与与与C C C C中各数和相中各数和相中各数和相中各数和相等。若等。若等。若等。若 ，则结论成立；若，则结论成立；若，则结论成立；若，则结论成立；若 ，则以，则以，则以，则以pp 代替代替代替代替B B B B，C C C C，结论亦成立。，结论亦成立。，结论亦成立。，结论亦成立。10111 1 1 12 2 2 2 极端原理极端原理极端原理极端原理 利用讨论“极端”对象来实现问题解决的解题方法称为用极端原理解题，常用的极端原理基于下述简单的事实：1）由实数组成的有限集合，必有一个最大数，也有一个最小数。2）由自然数组成的任何非空集合中，必有一个最小的自然数。为了肯定或否定组合数学问题的存在性，极端原理有着重大的作用。考察极端情况，讨论极端对象，无形中给问题的讨论增加了一个条件，所以更有利于问题的解决；用反证法时，讨论极端情况，使矛盾更容易暴露。12例例例例5 5 对平面上不全共线的对平面上不全共线的对平面上不全共线的对平面上不全共线的n n个点，求证：必存在一个点，求证：必存在一个点，求证：必存在一个点，求证：必存在一条恰好通过两点的直线。条恰好通过两点的直线。条恰好通过两点的直线。条恰好通过两点的直线。解答：对解答：对解答：对解答：对n n个点中的任两点作连线个点中的任两点作连线个点中的任两点作连线个点中的任两点作连线mm，并取连线外的点并取连线外的点并取连线外的点并取连线外的点P P（必存在），（必存在），（必存在），（必存在），考察考察考察考察P P到到到到mm的距离的距离的距离的距离d d（P P，mm），），），），由于点为有限个，连线由于点为有限个，连线由于点为有限个，连线由于点为有限个，连线mm为有限条，为有限条，为有限条，为有限条，组合（组合（组合（组合（P P，mm）也只能有有限个，用极端原理设）也只能有有限个，用极端原理设）也只能有有限个，用极端原理设）也只能有有限个，用极端原理设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,AB3n3）名乒乓球选手单打比赛若干场后）名乒乓球选手单打比赛若干场后）名乒乓球选手单打比赛若干场后）名乒乓球选手单打比赛若干场后,任意两任意两任意两任意两名选手已赛过的对手恰好都不完全相同名选手已赛过的对手恰好都不完全相同名选手已赛过的对手恰好都不完全相同名选手已赛过的对手恰好都不完全相同,求证求证求证求证:总可以从中去掉一名选手总可以从中去掉一名选手总可以从中去掉一名选手总可以从中去掉一名选手,使得余下的选手中使得余下的选手中使得余下的选手中使得余下的选手中,任意任意任意任意两个选手已赛过的对手仍然都不完全相同两个选手已赛过的对手仍然都不完全相同两个选手已赛过的对手仍然都不完全相同两个选手已赛过的对手仍然都不完全相同.pp证明证明证明证明:若不存在可去选手若不存在可去选手若不存在可去选手若不存在可去选手,则则则则A A不是可去选手不是可去选手不是可去选手不是可去选手,去掉去掉去掉去掉A A后后后后.至至至至少存在选手少存在选手少存在选手少存在选手B B和和和和C,C,他们赛过的对手完全相同他们赛过的对手完全相同他们赛过的对手完全相同他们赛过的对手完全相同,故故故故B B和和和和C C一定一定一定一定没有赛过没有赛过没有赛过没有赛过;B;B和和和和C C中恰有一人中恰有一人中恰有一人中恰有一人(不妨设为不妨设为不妨设为不妨设为B)B)与与与与A A赛过赛过赛过赛过(否则否则否则否则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 D D不会是不会是不会是不会是A,B(A,B(A,B(A,B(因因因因A,BA,BA,BA,B与与与与C C C C未赛过未赛过未赛过未赛过),D),D),D),D与与与与B B B B赛过赛过赛过赛过(因因因因D D D D和和和和C C C C赛过赛过赛过赛过,去掉去掉去掉去掉A A A A后后后后,B,C,B,C,B,C,B,C对手相同对手相同对手相同对手相同).).).).去掉去掉去掉去掉C C C C后后后后,D,D,D,D和和和和E E E E赛过的对手相同赛过的对手相同赛过的对手相同赛过的对手相同.所以所以所以所以E E E E与与与与B B B B也赛过也赛过也赛过也赛过.151.3 构造法和不变性原理构造法和不变性原理pp通过直接构作出解答来实现问题的解决称为用构通过直接构作出解答来实现问题的解决称为用构通过直接构作出解答来实现问题的解决称为用构通过直接构作出解答来实现问题的解决称为用构造法解题造法解题造法解题造法解题;对讨论问题分析其变化对讨论问题分析其变化对讨论问题分析其变化对讨论问题分析其变化,找出其中不变找出其中不变找出其中不变找出其中不变的量、不变的关系或不变的性质，抓住变中的的量、不变的关系或不变的性质，抓住变中的的量、不变的关系或不变的性质，抓住变中的的量、不变的关系或不变的性质，抓住变中的“不变不变不变不变”以促使问题的解决称为用不变性原理解题。以促使问题的解决称为用不变性原理解题。以促使问题的解决称为用不变性原理解题。以促使问题的解决称为用不变性原理解题。pp对于组合数学的存在性问题，常用构造法给出肯对于组合数学的存在性问题，常用构造法给出肯对于组合数学的存在性问题，常用构造法给出肯对于组合数学的存在性问题，常用构造法给出肯定的答案，而不变性原理常可给出否定的结论。定的答案，而不变性原理常可给出否定的结论。定的答案，而不变性原理常可给出否定的结论。定的答案，而不变性原理常可给出否定的结论。不变性原理中最简单、最实用的是奇偶性分析。不变性原理中最简单、最实用的是奇偶性分析。不变性原理中最简单、最实用的是奇偶性分析。不变性原理中最简单、最实用的是奇偶性分析。16例例例例8 8 8 8 有一个凸有一个凸有一个凸有一个凸n n n n边形（边形（边形（边形（n4n4n4n4）所有顶点用红绿蓝三色）所有顶点用红绿蓝三色）所有顶点用红绿蓝三色）所有顶点用红绿蓝三色染色，三种颜色都出现，且任意两相邻顶点不同色，染色，三种颜色都出现，且任意两相邻顶点不同色，染色，三种颜色都出现，且任意两相邻顶点不同色，染色，三种颜色都出现，且任意两相邻顶点不同色，求证：可用在求证：可用在求证：可用在求证：可用在n n n n边形内不交的对角线将多边形分成边形内不交的对角线将多边形分成边形内不交的对角线将多边形分成边形内不交的对角线将多边形分成n-2n-2n-2n-2个三角形，使每个三角形的三顶点都不同色。个三角形，使每个三角形的三顶点都不同色。个三角形，使每个三角形的三顶点都不同色。个三角形，使每个三角形的三顶点都不同色。pp解答解答解答解答:若某种颜色的点只有一个若某种颜色的点只有一个若某种颜色的点只有一个若某种颜色的点只有一个,则易知结论成立则易知结论成立则易知结论成立则易知结论成立.若每若每若每若每种颜色的顶点至少有二个种颜色的顶点至少有二个种颜色的顶点至少有二个种颜色的顶点至少有二个,且相邻顶点颜色不同且相邻顶点颜色不同且相邻顶点颜色不同且相邻顶点颜色不同,则必则必则必则必有连续三个顶点有连续三个顶点有连续三个顶点有连续三个顶点k,k+1,k+2k,k+1,k+2恰为三色恰为三色恰为三色恰为三色,将此三角形从凸将此三角形从凸将此三角形从凸将此三角形从凸n n边形中割下边形中割下边形中割下边形中割下,那么余下的是规模更小的凸多边形那么余下的是规模更小的凸多边形那么余下的是规模更小的凸多边形那么余下的是规模更小的凸多边形,若仍然每种颜色的顶点至少有二个若仍然每种颜色的顶点至少有二个若仍然每种颜色的顶点至少有二个若仍然每种颜色的顶点至少有二个,可继续割去一个三色三角形可继续割去一个三色三角形可继续割去一个三色三角形可继续割去一个三色三角形,最后可得某种颜色只有一个最后可得某种颜色只有一个最后可得某种颜色只有一个最后可得某种颜色只有一个,可以如图给出分划可以如图给出分划可以如图给出分划可以如图给出分划.17例例例例9 9 能否把能否把能否把能否把1 1，1 1，2 2，2 2，3 3，3 3，20052005，20052005这这这这40104010个数排成一列，使得两个个数排成一列，使得两个个数排成一列，使得两个个数排成一列，使得两个1 1之间有一个数，两个之间有一个数，两个之间有一个数，两个之间有一个数，两个2 2之间有二个数，之间有二个数，之间有二个数，之间有二个数，两个，两个，两个，两个20052005之间有之间有之间有之间有20052005个数个数个数个数 .18p证明：充分性：可用构造法作出，如图，正方形可剖分成6个钝角三角形，又任一钝角三角形总可分成两个钝角三角形。必要性：先找出任意钝角三角形剖分中不变的关系。对剖分法的剖分点进行分类：在正方形边界上的剖分点或在某一剖分三角形边上但不是该三角形顶点的内剖分点称为第一类剖分点；不在三角形边上的内剖分点称为第二类剖分点。如图中F，G，H为第一类剖分点，E为第二类剖分点。1920（2）任意凸四边形（各种情形）可剖分成钝角三角形（锐角三角形）的充要条件又各是什么？212组合数学中的计数问题组合数学中的计数问题p21 加法原理和乘法原理加法原理和乘法原理p加法原理：设事件加法原理：设事件A有有m种选取方式，事件种选取方式，事件B有有n种选取种选取方式，事件方式，事件A和事件和事件B没有共同选取方式，则选没有共同选取方式，则选A或选或选B有有m+n种方式。种方式。p乘法原理：设事件乘法原理：设事件A有有m种选取方式，事件种选取方式，事件B有有n种选取种选取方式，则选取方式，则选取A以后再选以后再选B共有共有mn种方式。种方式。p 2223例例例例12.12.三个数三个数三个数三个数14471447、10051005、12311231有许多相同之处：它有许多相同之处：它有许多相同之处：它有许多相同之处：它们都有四位数，最高位都是们都有四位数，最高位都是们都有四位数，最高位都是们都有四位数，最高位都是1 1，都恰有两个相同的数，都恰有两个相同的数，都恰有两个相同的数，都恰有两个相同的数字，一共有多少个这样的数。字，一共有多少个这样的数。字，一共有多少个这样的数。字，一共有多少个这样的数。242.2 映射与计数映射与计数25例例例例13.13.在数列在数列在数列在数列1 1，9 9，8181，9200592005中删去最高位是中删去最高位是中删去最高位是中删去最高位是9 9的项，问余下的数列有多少项？的项，问余下的数列有多少项？的项，问余下的数列有多少项？的项，问余下的数列有多少项？26例例14.14.圆周上有圆周上有n n个点每两个点连一线段，假设任三个点每两个点连一线段，假设任三条线段在圆内不共点，于是三条两两相交的线段构条线段在圆内不共点，于是三条两两相交的线段构成一个三角形，试求这些三角形的个数？成一个三角形，试求这些三角形的个数？27例例例例15.15.设凸设凸设凸设凸n n边形的任意边形的任意边形的任意边形的任意3 3条对角线不相交于行内一点，条对角线不相交于行内一点，条对角线不相交于行内一点，条对角线不相交于行内一点，求它的对角线在行内的交点总数。求它的对角线在行内的交点总数。求它的对角线在行内的交点总数。求它的对角线在行内的交点总数。28例例例例16.16.今有编号为今有编号为今有编号为今有编号为1 1，2 2，1010的钥匙与编号为的钥匙与编号为的钥匙与编号为的钥匙与编号为1 1，2 2，1010的箱的箱的箱的箱子，每把钥匙只能打开与之号数相同的箱子，现将所有钥匙都放子，每把钥匙只能打开与之号数相同的箱子，现将所有钥匙都放子，每把钥匙只能打开与之号数相同的箱子，现将所有钥匙都放子，每把钥匙只能打开与之号数相同的箱子，现将所有钥匙都放进这些箱子中，每只箱子放一把，然后锁上，那么至少有多少种进这些箱子中，每只箱子放一把，然后锁上，那么至少有多少种进这些箱子中，每只箱子放一把，然后锁上，那么至少有多少种进这些箱子中，每只箱子放一把，然后锁上，那么至少有多少种不同的放法，使得至少要撬开两只箱子才能将箱子全部打开？若不同的放法，使得至少要撬开两只箱子才能将箱子全部打开？若不同的放法，使得至少要撬开两只箱子才能将箱子全部打开？若不同的放法，使得至少要撬开两只箱子才能将箱子全部打开？若恰撬开两只箱子才能将箱子全部打开，又有多少放法？恰撬开两只箱子才能将箱子全部打开，又有多少放法？恰撬开两只箱子才能将箱子全部打开，又有多少放法？恰撬开两只箱子才能将箱子全部打开，又有多少放法？29 证明：我们将不定方程证明：我们将不定方程证明：我们将不定方程证明：我们将不定方程 的任意一组非的任意一组非的任意一组非的任意一组非负整数解负整数解负整数解负整数解 对应于一个由对应于一个由对应于一个由对应于一个由n n个圆圈个圆圈个圆圈个圆圈“”，k-1k-1个竖线个竖线个竖线个竖线“|”|”组成的如下排列：组成的如下排列：组成的如下排列：组成的如下排列：|，其，其，其，其中第一根竖线中第一根竖线中第一根竖线中第一根竖线“|”|”的左侧恰有的左侧恰有的左侧恰有的左侧恰有x1x1个圆圈个圆圈个圆圈个圆圈“”；第；第；第；第i-1i-1根根根根竖线竖线竖线竖线“|”|”与第与第与第与第i i根竖线根竖线根竖线根竖线“|”|”之间恰有之间恰有之间恰有之间恰有xixi个圆圈个圆圈个圆圈个圆圈“”；第第第第i-1i-1根竖线根竖线根竖线根竖线“|”|”的右侧恰有的右侧恰有的右侧恰有的右侧恰有xkxk个圆圈个圆圈个圆圈个圆圈“”。显然，不。显然，不。显然，不。显然，不定方程的不同的解对应于不同的排列，且每一个这样的对定方程的不同的解对应于不同的排列，且每一个这样的对定方程的不同的解对应于不同的排列，且每一个这样的对定方程的不同的解对应于不同的排列，且每一个这样的对应于不定方程的一组非负整数解，因此，我们建立的对应应于不定方程的一组非负整数解，因此，我们建立的对应应于不定方程的一组非负整数解，因此，我们建立的对应应于不定方程的一组非负整数解，因此，我们建立的对应是一个双射。是一个双射。是一个双射。是一个双射。又因为由又因为由又因为由又因为由n n个圆圈个圆圈个圆圈个圆圈“”及及及及k-1k-1根竖线根竖线根竖线根竖线“|”|”组成的组成的组成的组成的n+k-1n+k-1个个个个元素的全排列数为元素的全排列数为元素的全排列数为元素的全排列数为 ，所以，不定方程，所以，不定方程，所以，不定方程，所以，不定方程 的一组非负整数解组的组数为的一组非负整数解组的组数为的一组非负整数解组的组数为的一组非负整数解组的组数为 。3023容斥原理容斥原理31例例18.18.一个学校只有3门课程：数学、物理、化学，已知修这3门课程的学生分别有170、130、120人；同时修数学、物理两门课的学生有45人；同时修数学、化学两门课的学生有20人；同时修物理、化学两门课的学生有22人；同时修三门课的学生有3人。问这个学校共有多少学生？32例例19.求a，b，c，d，e，f这六个字母的全排列中不允许出现ace和df图像的排列数。3334例例例例21.21.求由求由求由求由a a，b b，c c，d d这这这这4 4个字符构成的个字符构成的个字符构成的个字符构成的n n位数字串中，位数字串中，位数字串中，位数字串中，a a，b b，c c至少出现一次的符号串的数目。至少出现一次的符号串的数目。至少出现一次的符号串的数目。至少出现一次的符号串的数目。3536同理3738练习题1给定2003个集合，每个集合都恰含有44个元素，并且每两个集合都恰有一个公共元素，试求这2003个集合的并集中有多少个元素？2平面内给定200个不同的点，证明：其中距离为单位长的点对数小于2050。3以正n边形的顶点为顶点的梯形共有多少个？39杂杂 题题40 例例1 1 运动会开了n天（n1）,共发出m个奖牌,第一天发出1个加余下奖牌的,第二天发出2个加余下奖牌的,如此继续下去,最后,第n天发出n个奖牌恰无剩余.问运动会共开了几天?共发出多少个奖牌?414243例例2.几个人在一起几个人在一起几个人在一起几个人在一起,使得其中存在有相同生日的概率使得其中存在有相同生日的概率使得其中存在有相同生日的概率使得其中存在有相同生日的概率至少为二分之一至少为二分之一至少为二分之一至少为二分之一.即即即即23232323人中人中人中人中,至少有一至少有一至少有一至少有一对对生日相同的概率超生日相同的概率超生日相同的概率超生日相同的概率超过过二分之一二分之一二分之一二分之一 44例例例例3.3.甲乙二人玩，在黑板上写数的游戏，规则是二人轮流甲乙二人玩，在黑板上写数的游戏，规则是二人轮流甲乙二人玩，在黑板上写数的游戏，规则是二人轮流甲乙二人玩，在黑板上写数的游戏，规则是二人轮流在黑板上写一个不超过在黑板上写一个不超过在黑板上写一个不超过在黑板上写一个不超过p p的自然数，但禁止再写出黑板上已的自然数，但禁止再写出黑板上已的自然数，但禁止再写出黑板上已的自然数，但禁止再写出黑板上已有的因数。甲先开始写，轮到谁写而无法写出时就告负。有的因数。甲先开始写，轮到谁写而无法写出时就告负。有的因数。甲先开始写，轮到谁写而无法写出时就告负。有的因数。甲先开始写，轮到谁写而无法写出时就告负。（1 1）当）当）当）当p=10p=10时，游戏者中谁有获胜策略？时，游戏者中谁有获胜策略？时，游戏者中谁有获胜策略？时，游戏者中谁有获胜策略？（2 2）当）当）当）当p=1000p=1000时，游戏者中谁有获胜策略？时，游戏者中谁有获胜策略？时，游戏者中谁有获胜策略？时，游戏者中谁有获胜策略？解答：（解答：（解答：（解答：（1 1）甲有获胜策略，他可以先写）甲有获胜策略，他可以先写）甲有获胜策略，他可以先写）甲有获胜策略，他可以先写6 6，于是按规则不，于是按规则不，于是按规则不，于是按规则不能再写能再写能再写能再写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的这个游戏。如果这个游戏先写者有必胜策略，的这个游戏。如果这个游戏先写者有必胜策略，的这个游戏。如果这个游戏先写者有必胜策略，的这个游戏。如果这个游戏先写者有必胜策略，那么甲对原来的游戏只要照搬就行了。因为甲写下一个自那么甲对原来的游戏只要照搬就行了。因为甲写下一个自那么甲对原来的游戏只要照搬就行了。因为甲写下一个自那么甲对原来的游戏只要照搬就行了。因为甲写下一个自然数后，乙是不能写然数后，乙是不能写然数后，乙是不能写然数后，乙是不能写1 1的。如果新游戏先写数的人没有获的。如果新游戏先写数的人没有获的。如果新游戏先写数的人没有获的。如果新游戏先写数的人没有获胜策略，即他只能告负，那么甲在原游戏中可以先写胜策略，即他只能告负，那么甲在原游戏中可以先写胜策略，即他只能告负，那么甲在原游戏中可以先写胜策略，即他只能告负，那么甲在原游戏中可以先写1 1，从而将失败留给了乙。可见，甲总有获胜策略。从而将失败留给了乙。可见，甲总有获胜策略。从而将失败留给了乙。可见，甲总有获胜策略。从而将失败留给了乙。可见，甲总有获胜策略。45p例例4.甲乙两人在画有个方格的正方形场地上做游戏:甲先在场地中央画一个星号,乙则在放有星号的格子周围的8个格子中任选1个方格画一个圆圈.然后甲再在某个与已画有标记的格子挨着的空格中画一个星号,并一直继续下去.如果甲成功地将星号画入场地四角的任何一个角上的方格中,就算他获胜.求证:不论乙怎么做,甲总可以获胜.46例例5.5.在33的正方形表格中填上如图所示的9个数字,将该表进行如下操作:每次操作是对表中相邻两数同时加上一个数(相邻是指有公共边的两小格),问能否经过若干次操作使得（1）表格中各数均为0；（2）表格中四个角的数为1,其余均为0.03267049547解答:(1)能够得到.事实上经过5次操作即可.03267049501067049501067005501067000001001000000000000048(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因此不能实现满足题目要求的操作.abcdefghk49例例6.凸n边形的任意3条对角线不相交于形内一点，求这些对角线将凸n边形分成的区域的个数.5051525354例例7.已知平面上有4条直线,其中任何两条都相交,任何三条都不交于一点,于是在每条直线上都交得3个交点,它们从直线上截出两条线段,共得到8条线段.问这8条线段的长度能否分别为 (1)1,2,3,4,5,6,7,8?(2)互不相同的自然数?55（2）8条线段的长度可以是互不相同的自然数，见图。56例例8.一袋花生共1988颗,一只猴子第一天拿走一颗花生,从第二天起,每天拿走的都是以前各天的总和.如果到某天袋里的花生少于已拿走的总数时,这一天它又从拿走一颗开始,按原定的规律进行新的一轮.如此继续下去,那么这袋花生被猴子拿光时是第几天?57练习题18个小圆片分别涂有4种颜色：红、蓝、白、黑各两个。甲乙两人轮流把圆片放到正方体的顶点上，在所有的圆片都放完之后，如果正方体上存在一条棱，其两个端点所放的圆片同色，则甲获胜，否则乙获胜。问在这个游戏中睡有必胜策略。2.在黑板上写有3个整数,然后擦去其中一个,并代之以剩下的两数之和与1的差.重复这个步骤若干次后,黑板上的数变成了17,1967,1983,问开始时黑板上所写的数能否是下列数组:(1)2,2,2 (2)3,3,358路要自己走路要自己走 关要自己闯关要自己闯祝同学们取得好成绩祝同学们取得好成绩59精品课件资料分享 SL出品精品课件资料分享 SL出品精品课件资料分享 SL出品谢谢你的阅读v知识就是财富v丰富你的人生71、既然我已经踏上这条道路，那么，任何东西都不应妨碍我沿着这条路走下去。康德72、家庭成为快乐的种子在外也不致成为障碍物但在旅行之际却是夜间的伴侣。西塞罗73、坚持意志伟大的事业需要始终不渝的精神。伏尔泰74、路漫漫其修道远，吾将上下而求索。屈原75、内外相应，言行相称。韩非