数学奥林匹克专题讲座 第16讲 枚举、归纳与猜想

数学奥林匹克专题讲座 第16讲 枚举、归纳与猜想 数学奥林匹克专题讲座1第16讲枚举、归纳与猜想 一、枚举法枚举法起源于原始的计数方法，即数数。 关于这方面的例子，我们在第11讲中已介绍过，现在我们从另一角度来利用枚举法解题。 当我们面临的问题存在大量的可能的答案（或中间过程），而暂时又无法用逻辑方法排除这些可能答案中的大部分时，就不得不采用逐一检验这些答案的策略，也就是利用枚举法来解题。 采用枚举法解题时，重要的是应做到既不重复又不遗漏，这就好比工厂里的质量检验员的责任是把不合格产品挑出来，不让它出厂，于是要对所有的产品逐一检验，不能有漏检产品。 例1一个小于400的三位数，它是平方数，它的前两个数字组成的两位数还是平方数，其个位数也是一个平方数。 求这个三位数。 解这道题共提出三个条件 （1）一个小于400的三位数是平方数； （2）这个三位数的前两位数字组成的两位数还是平方数； （3）这个三位数的个位数也是一个平方数。 我们先找出满足第一个条件的三位数100，121，144，169，196，225，256，289，324，361。 再考虑第二个条件，从中选出符合条件者169，256，361。 最后考虑第三个条件，排除不合格的256，于是找到答案是169和361。 说明这里我们采用了枚举与筛选并用的策略，即依据题中限定的条件，面对枚举出的情况逐步排除不符合条件的三位数，确定满足条件的三位数，从而找到问题的答案。 例2哥德巴赫猜想是说每个大于2的偶数都可以表示为两个质数之和。 问168是哪两个两位数的质数之和，并且其中一个的个位数是1？解168表示成两个两位质数之和，两个质数都大于68。 个位是1且大于68的两位数有71，81，91，其中只有71是质数，所以一个质数是71，另一个质数是168-71=97。 2说明解此题要求同学们记住100以内的质数。 如果去掉题目中“其中一个的个位数是1”的条件，那么上述答案不变，仍是唯一的解答。 如果取消位数的限制，那么还有168=5+163，168=11+157，168=17+151，?哥德巴赫猜想是1742年提出来的，至今已有250多年的历史了，它是数论中最有名的问题，中外许多著名的数学家都研究过，包括我国著名数学家华罗庚教授。 例3有30枚贰分硬币和8枚伍分硬币，用这些硬币不能构成的1分到1元之间的币值有多少种？解注意到所有的38枚硬币的总币值恰好是100分（即1元），于是除了50分与100分外，其他98种币值可以两两配对，即（1，99），（2，98），（3，97），?，（49，51）。 每一对币值中有一个可用若干枚贰分和伍分硬币构成，则另一个也可以，显然50分和100分的币值是可以构成的，因此只需要讨论币值为1分、2分、3分?49分这49种情况。 1分和3分的币值显然不能构成。 2分、4分、6分?48分这24种偶数币值都可以用若干枚贰分硬币构成，因为贰分硬币的总数为30个。 5分、7分、9分?49分这23种奇数币值，只需分别在4分、6分、8分?48分币值的构成方法上，用1枚伍分硬币换去两枚贰分硬币即可，比如37分币值，由于36分币值可用18枚贰分硬币构成，用1枚伍分硬币换下2枚贰分硬币，所得的硬币值即为37分。 综合以上分析，不能用若干枚贰分和伍分硬币构成的1分到1元之间的币值只有四种，即1分、3分、97分、99分。 例4一个两位数被7除余1，如果交换它的十位数字与个位数字的位置，所得到的两位数被7除也余1，那么这样的两位数有多少个？都是几？两式相减，得9（a-b）=7（n-m）。 于是7|9（a-b）。 因为（7，9）=1，所以7|a-b，得到a-b=0，或a-b=7。 3 （1）当a-b=0，即a=b时，在两位数11，22，33，44，55，66，77，88，99中逐一检验，只有22，99符合被7除余1的条件。 （2）当a-b=7，即a=b7时，b=1，或b=2。 在81，92这二个数中，只有92符合被7除余1的条件。 因为a，b交换位置也是解，所以符合条件的两位数共有四个，它们是22，29，92及99。 说明这里我们把题中限定的条件放宽，分成两类，枚举出每一类的两位数，逐一检验排除不符合条件的两位数，确定符合条件的两位数，从而找到问题的答案。 此题也可以枚举出被7除余1的所有两位数15，22，29，36，43，50，57，64，71，78，85，92，99，再根据题意逐一筛选。 例5把1，2，3，4，5，6分别填入左下图所示的表格内，使得每行相邻的两个数左边的小于右边的，每列的两数上面的小于下面的。 问有几种填法？解如右上图，由已知可得a最小，f最大，即a=1，f=6。 根据b与d的大小，可分两种情况讨论。 当bd时，有b=2，c=3或4或5，可得下列3种填法当bd时，有b=3，d=2，c=4或5，可得下列2种填法综上所述，一共有5种填法。 例6今有101枚硬币，其中有100枚同样的真币和1枚伪币，伪币与真币的重量不同，现需弄清楚伪币比真币轻，还是比真币重，但只有一架没有砝码的天平。 试问，怎样利用这架天平称两次，来达到目的？解在天平两端各放50枚硬币。 如果天平平衡，那么所剩一枚为伪币，于是取一枚伪币和一枚真币分放在天平两端，即可判明真币与伪币谁轻谁重。 4如果天平不平衡，那么取下重端的50枚硬币，并将轻端的50枚硬币分放两端各25枚，若此时天平平衡，则说明伪币在取下的50枚硬币中，即伪币比真币重；若此时天平仍不平衡，则说明伪币在较轻的50枚硬币中，即伪币比真币轻。 在上述解答过程中，我们面临着“平衡”或“不平衡”两种可能的状态，对这两种状态，逐一检验，即得到问题的结论。 由上述例题可以看出运用枚举法的关键在于 （1）如何将整体分解成各个特殊情况，也就是要注意分类的方法，分类必须适合于一一列举和研究，同时分类必须不重也不漏。 （2）善于对列举的结果进行综合考察（包括筛选），并导出结论。 二、归纳与猜想“猜想”是一种重要的思维方法，对于确定证明方向，发现新定理，都有重大意义。 最著名的例子就是哥德巴赫猜想，1742年曾任中学教师的哥德巴赫和大数学家欧拉通过观察实例6=33，8=35，10=37，12=57，14=311，16=313，18=711，?提出如下猜想“任何大于或等于6的偶数，都可以表示成两个奇素数之和。 这就是闻名于世的哥德巴赫猜想，至今还没有给以逻辑证明，所以仍是一个猜想。 二百多年以来，她像一颗璀璨夺目的明珠，吸引了无数数学家和数学爱好者为之奋斗。 通过观察若干具体实例，发现存在于它们之中的某种似乎带规律性的东西，我们相信它具有普遍意义，对更多更一般的实例同样适用，从而把它当做一般规律或结论，这种发现规律或结论的方法就是归纳法。 当然，归纳出来的规律或结论一般来说还只是一种猜想，它是否正确，还有待于进一步证明。 例如，我们可能碰巧看到182764=100，改变一下形式13233343=102=（1234）2。 这个形式很规则，这是偶然的，还是确有这样的规律？不妨再试验一下1323=9=32=（12）2，132333=36=62=（123）2。 再多一些数试验一下51323334353=225=152=（12345）2。 于是猜想又如，求凸n边形内角和。 观察分析三角形内角和为180；四边形可分为2个三角形，故内角和为2180；五边形可分为3个三角形，故内角和为3180；归纳猜想凸n边形的内角和为（n-2）180。 例7下面各列数都依照一定规律排列，在括号里填上适当的数 （1）1，5，9，13，17，（）； （4）32，31，16，26，（），（），4，16，2，11。 分析与解要在括号里填上适当的数，必须正确地判断出每列数所依照的规律，为此必须进行仔细的观察和揣摩。 （1）考察相邻两数的差5-1=4，9-5=4，13-9=4，17-13=4。 可见，相邻两数之差都是4。 按此规律，括号里的数减去17等于4，所以应填入括号里的数是174=21。 （2）像 （1）那样考虑难以发现规律，改变一下角度，把各数改写为可以发现6 （3）为探究规律，作适当变形这样一来，分子部分呈现规律自3起，依次递增2，故括号内的数的分子为13。 再看分母部分4，8，14，22，32。 相邻两数之差得4，6，8，10。 可见括号内的数的分母应为3212=44。 （4）分成两列数奇数位的数为32，16，（），4，2。 可见前面括号中应填入8；偶数位的数为31，26，（），16，11。 括号中的数应填入21。 所以，两括号内依次填入8，21。 说明从上面例子可以看到，观察时不可把眼光停留在某一点上固定不变，而要注意根据问题特点不断调整自己观察的角度，以利于观察出有一定隐蔽性的内在规律。 例8下面是七个分数先约分，请你再划去一个与众不同的数，然后按照一定的规律将余下的六个数排列起来，并按你的规律接下去写出第七个数。 分析约分是容易的，除其中一个数外，另外六个数必有联系。 解已给分数经约分后是7说明这个题目里给出了解题的操作指示，即化简、按规律分类、排序、添加新数，做起来感觉很顺利、轻松。 做完题后体会一下命题者的用意，他是想让学生了解和学会怎样归纳和猜测。 在许多问题中，各元素从表面上看没什么联系，也看不出什么规律，这就需要我们像做约分那样透过表面看本质，扒掉“披在元素身上花花绿绿的外衣”，从而发现彼此间的共性和联系。 这个题的命题者给出了一个做归纳和猜测的示范，应引起读者重视。 例9将正方形纸片如下图所示由下往上对折，再由左向右对折，称为完成一次操作。 按上述规则完成五次操作以后，剪去所得小正方形的左下角。 问当展开这张正方形纸片后，一共有多少个小洞孔？解一次操作后，层数由1变为4，若剪去所得小正方形左下角，展开后只有1个小洞孔，恰是大正方形的中心。 连续两次操作后，折纸层数为42，剪去所得小正方形左下角，展开后大正方形留有42-1=41=4（个）小洞孔。 连续三次操作后，折纸层数为43，剪去所得小正方形左下角，展开后大正方形上留有43-1=42=16（个）小洞孔。 ?按上述规律不难断定连续五次操作后，折纸层数为45，剪去所得小正方形左下角，展开后大正方形纸片上共留有小洞孔845-1=44=256（个）。 例10将自然数排成如下的螺旋状第一个拐弯处的数是2，第二个拐弯处的数是3，第20个及第25个拐弯处的数各是多少？解由图可知，前几个拐弯处的数依次是2，3，5，7，10，13，17，21，26，?这是一个数列，题目要求找出它的第20项和第25项各是多少，因此要找出这个数列的规律。 把数列的后一项减去前一项，得一新数列1，2，2，3，3，4，4，5，5，?把原数列的第一项2添在新数列的前面，得到2，1，2，2，3，3，4，4，5，5，?于是，原数列的第n项a n就等于上面数列的前n项和，即a1=2=1+1=2，a2=2+1=1+（1+1）=3，a3=2+1+2=1+（1+1+2）=5，a4=2+1+2+2=1+（1+1+2+2）=7，?所以，第20个拐弯处的数是9a20=1+（1+1+2+2+3+3+4+4+?+10+10）=12（12?10）=111。 第25个拐弯处的数是a25=1+（1+1+2+2+?+12+12+13）=1112（1112）13=170。 说明 （1）这个数列的一般项可以写成第2n（偶数）项为a2n=12（12?n）=1nn2；第（2n+1）（奇数）项为a2n1=12（12?n）（n1）=22nn2。 （2）寻找数列排列的规律，常用两种方法一是考察数列的“项”与它所在的位置即“项数”之间的关系，一般的数列写作a1，a2，a3，?，a n，?这里a n是数列的“项”，n是“项数”。 若能找到“项”与“项数”的关系，则知道了项数n，也就知道了项a n。 另一方法是研究相邻两项或几项的关系，这样，知道了最初的几项后，后面的项就可利用关系顺次写出来。 例11给出一个“三角形”的数表如下此表构成的规则是第一行是0，1，2，?，999，以后下一行的数是上一行相邻两数的和。 问第四行的数中能被999整除的数是什么？解首先找出第四行数的构成规律。 通过观察、分析，可以看出第四行的任一个数都和第一行中相应的四个相邻的数有关，具体关系可以从下表看出10如果用a n表示第四行的第n个数，那么a n=8n+4。 现在要找出a n=8n+4=999k的a n，显然k应是4的倍数。 注意到第四行中最大的数是79809998，所以k=4。 由此求出第四行中能被999整除的数是9994=3996，它是第四行的第（3996-4）8=499（项），即a499=3996。 说明本题通过观察、归纳找出第四行的构成规律，即第n个数的通项公式。 当然通项公式也可以直接通过观察第四行各数的排列规律来发现，即把第四行的前后几个数算出来12，20，28，36，?，7980。 观察分析发现后一个数都比前一个数多8，从而归纳出通项公式为a n=8n+4。 例12在平面上有n条直线，任何两条都不平行，并且任何三条都不交于同一点，这些直线能把平面分成几部分？解设n条直线分平面为S n部分，先实验观察特例有如下结果n与S n之间的关系不太明显，但S n-S n-1有如下关系观察上表发现，当n2时，有S n-S n-1=n。 因为在（n-1）条直线后添加第n条直线被原（n-1）条直线截得的n段中的任何一段都将它所在的原平面一分为二，相应地增加n部分，所以S n=S n-1+n，即S n-S n-1=n。 从而11S2-S1=2，S3-S2=3，S4-S3=4，?，S n-S n-1=n。 将上面各式相加，得到S n-S1=2+3+?+n，S n=S1+2+3+?+n=2+2+3+?+n=1+（1+2+?+n）说明S n也可由如下观察发现。 由上表知S1=1+1，S2=1+1+2，S3=1+1+2+3，S4=1+1+2+3+4，依此类推，便可猜想到练习161.用数字1，3，4，5，7，8，9组成没有重复数字的四位数，得到的数从小到大排成一列。 问第119个数是几？2.同时满足下列条件的分数共有多少个？ （2）分子和分母都是质数； （3）分母是两位数。 请列举出所有满足条件的分数。 3.用一个三位数乘945，使所得的乘积为平方数，这样的数共有几个？最大的与最小的各是多少？4.A，B，C三人中，一部分是总说真话的老实人，另一部分是总说假话的骗子。 A说“若C是老实人，则B是骗子。 12C说“A和我不都是老实人，也不全是骗子。 问A，B，C三人中，谁是老实人？谁是骗子？5.现有如下一系列图形当时n=1时，长方形ABCD分为2个直角三角形，这些三角形共有5条边（重复的只算一条，下同）。 当n=2时，长方形ABCD分为8个直角三角形，这些三角形共有16条边。 当n=3时，长方形ABCD分为18个直角三角形，这些三角形共有33条边。 ?按如上规律请你回答当n=100时，长方形ABCD应分为多少个直角三角形？这些三角形共有多少条边？6. （1）下面的（a）（b）（c）（d）为四个平面图。 数一数，每个平面图各有多少顶点？多少条边？它们分别围成了多少个区域？请将结果填入下表（按填好的样子做）。 （2）观察上表，推断一个平面图的顶点数、边数、区域数之间有什么关系。 （3）现已知某个平面图有999个顶点，且围成了999个区域，试根据以上关系确定这个图有多少条边。 137.有一列数1，3，4，7，11，18，?（从第三个数开始，每个数恰好是它前面相邻两个数的和）。 （1）第999个数被6除余几？ （2）把以上数列按下述方法分组 （1），（3，4），（7，11，18），?（第n组含有n个数）第999组的各数之和被6除余数是几？8.把1999这999个自然数按顺时针的方向依次排列在一个圆圈上（如下图）。 从1开始按顺时针的方向，保留1，擦去2；保留3，擦去4?这样每隔一个数擦去一个数，转圈擦下去。 问最后剩下一个数时，剩下的是哪个数？练习161.1985。 解按从小到大无重复数字的四位数顺序，前两位数是13的有20个；前两位数是14的有20个；?前两位数是19的有20个。 即为1987，那么第119个数就是1985。 14提示由 （1）知分子是大于1，且小于20（因为分母是两位数）的质数。 然后就分子为2，3，5，7，11，13，17，19逐一枚举，推出共有13个分数满足要求。 3.945，105。 解因为945=3357，要使它乘上一个数后成为平方数，必须使乘积中各质因数的个数成为偶数，所以，所乘的数必须是357=105与另一平方数的乘积。 因为10512=105，10522=620，10532=945，所以，与945相乘得到平方数的三位数共有3个，最大的是945，最小的是105。 4.B，C是老实人，A是骗子。 解假设C是骗子，那么，从C的说法断定A与C一样是骗子。 这样，不管B是不是骗子，A的说法没错，应是老实人，产生矛盾。 因此C是老实人。 由C的说法断定A与C不一样，是骗子。 再由A的说法，断定B不是骗子，是老实人。 5.20000个，30200条。 解n=1时，直角三角形有212个，边数=21（1+1）+12=5；n=2时，直角三角形有222个，边数=22（2+1）22=16；n=3时，直角三角形有232个，边数=23（3+1）+32=33。 对一般的n，共分为2n2个直角三角形，边数=2n（n+1）+n2。 所以n=100时，共分为21002=20000（个）直角三角形，共有2100（100+1）+1002=30200（条）边。 6. （1）填表如下15 （2）由该表可以看出，所给四个平面图的顶点数、边数及区域数之间有下述关系4+3-6=1，8+5-12=1，6+4-9=1，10+6-15=1。 所以，我们可以推断任何平面图的顶点数、边数及区域数之间，都有下述关系顶点数+区域数-边数=1。 （3）由上面所给的关系，可知所求平面图的边数。 边数=顶点数+区域数-1=999+999-1=1997。 注任