《数学奥林匹克专题讲座》第16讲枚举

第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。说明：解此题要求同学们记住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。（1）当a-b=0，即a=b时，在两位数11，22，33，44，55，66，77，88，99中逐一检验，只有22，99符合被7除余1的条件。（2）当a-b=7，即a=b＋7时，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的大小，可分两种情况讨论。当b＜d时，有b=2，c=3或4或5，可得下列3种填法：当b＞d时，有b=3，d=2，c=4或5，可得下列2种填法：综上所述，一共有5种填法。例6今有101枚硬币，其中有100枚同样的真币和1枚伪币，伪币与真币的重量不同，现需弄清楚伪币比真币轻，还是比真币重，但只有一架没有砝码的天平。试问，怎样利用这架天平称两次，来达到目的？解：在天平两端各放50枚硬币。如果天平平衡，那么所剩一枚为伪币，于是取一枚伪币和一枚真币分放在天平两端，即可判明真币与伪币谁轻谁重。如果天平不平衡，那么取下重端的50枚硬币，并将轻端的50枚硬币分放两端各25枚，若此时天平平衡，则说明伪币在取下的50枚硬币中，即伪币比真币重；若此时天平仍不平衡，则说明伪币在较轻的50枚硬币中，即伪币比真币轻。在上述解答过程中，我们面临着“平衡”或“不平衡”两种可能的状态，对这两种状态，逐一检验，即得到问题的结论。由上述例题可以看出运用枚举法的关键在于：（1）如何将整体分解成各个特殊情况，也就是要注意分类的方法，分类必须适合于一一列举和研究，同时分类必须不重也不漏。（2）善于对列举的结果进行综合考察（包括筛选），并导出结论。二、归纳与猜想“猜想”是一种重要的思维方法，对于确定证明方向，发现新定理，都有重大意义。最著名的例子就是哥德巴赫猜想，1742年曾任中学教师的哥德巴赫和大数学家欧拉通过观察实例：6=3＋3，8=3＋5，10=3＋7，12=5＋7，14=3＋11，16=3＋13，18=7＋11，…提出如下猜想：“任何大于或等于6的偶数，都可以表示成两个奇素数之和。”这就是闻名于世的哥德巴赫猜想，至今还没有给以逻辑证明，所以仍是一个猜想。二百多年以来，她像一颗璀璨夺目的明珠，吸引了无数数学家和数学爱好者为之奋斗。通过观察若干具体实例，发现存在于它们之中的某种似乎带规律性的东西，我们相信它具有普遍意义，对更多更一般的实例同样适用，从而把它当做一般规律或结论，这种发现规律或结论的方法就是归纳法。当然，归纳出来的规律或结论一般来说还只是一种猜想，它是否正确，还有待于进一步证明。例如，我们可能碰巧看到1＋8＋27＋64=100，改变一下形式：13＋23＋33＋43=102=（1＋2＋3＋4）2。这个形式很规则，这是偶然的，还是确有这样的规律？不妨再试验一下：13＋23=9=32=（1＋2）2，13＋23＋33=36=62=（1＋2＋3）2。再多一些数试验一下：13＋23＋33＋43＋53=225=152=（1＋2＋3＋4＋5）2。于是猜想：又如，求凸n边形内角和。观察分析：三角形内角和为180°；四边形可分为2个三角形，故内角和为2×180°；五边形可分为3个三角形，故内角和为3×180°；归纳猜想：凸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，所以应填入括号里的数是17＋4=21。（2）像（1）那样考虑难以发现规律，改变一下角度，把各数改写为可以发现：（3）为探究规律，作适当变形：这样一来，分子部分呈现规律：自3起，依次递增2，故括号内的数的分子为13。再看分母部分：4，8，14，22，32。相邻两数之差得4，6，8，10。可见括号内的数的分母应为32＋12=44。（4）分成两列数：奇数位的数为32，16，（），4，2。可见前面括号中应填入8；偶数位的数为31，26，（），16，11。括号中的数应填入21。所以，两括号内依次填入8，21。说明：从上面例子可以看到，观察时不可把眼光停留在某一点上固定不变，而要注意根据问题特点不断调整自己观察的角度，以利于观察出有一定隐蔽性的内在规律。例8下面是七个分数：先约分，请你再划去一个与众不同的数，然后按照一定的规律将余下的六个数排列起来，并按你的规律接下去写出第七个数。分析：约分是容易的，除其中一个数外，另外六个数必有联系。解：已给分数经约分后是说明：这个题目里给出了解题的操作指示，即化简、按规律分类、排序、添加新数，做起来感觉很顺利、轻松。做完题后体会一下命题者的用意，他是想让学生了解和学会怎样归纳和猜测。在许多问题中，各元素从表面上看没什么联系，也看不出什么规律，这就需要我们像做约分那样透过表面看本质，扒掉“披在元素身上花花绿绿的外衣”，从而发现彼此间的共性和联系。这个题的命题者给出了一个做归纳和猜测的示范，应引起读者重视。例9将正方形纸片如下图所示由下往上对折，再由左向右对折，称为完成一次操作。按上述规则完成五次操作以后，剪去所得小正方形的左下角。问：当展开这张正方形纸片后，一共有多少个小洞孔？解：一次操作后，层数由1变为4，若剪去所得小正方形左下角，展开后只有1个小洞孔，恰是大正方形的中心。连续两次操作后，折纸层数为42，剪去所得小正方形左下角，展开后大正方形留有42-1=41=4（个）小洞孔。连续三次操作后，折纸层数为43，剪去所得小正方形左下角，展开后大正方形上留有43-1=42=16（个）小洞孔。……按上述规律不难断定：连续五次操作后，折纸层数为45，剪去所得小正方形左下角，展开后大正方形纸片上共留有小洞孔45-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项an就等于上面数列的前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个拐弯处的数是：a20=1+（1+1+2+2+3+3+4+4+…+10+10）=1＋2×（1＋2＋…＋10）=111。第25个拐弯处的数是：a25=1+（1+1+2+2+…+12+12+13）=111＋2×（11＋12）＋13=170。说明：（1）这个数列的一般项可以写成第2n（偶数）项为a2n=1＋2×（1＋2＋…＋n）=1＋n＋n2；第（2n+1）（奇数）项为a2n＋1=1＋2×（1＋2＋…＋n）＋（n＋1）=2＋2n＋n2。（2）寻找数列排列的规律，常用两种方法：一是考察数列的“项”与它所在的位置即“项数”之间的关系，一般的数列写作a1，a2，a3，…，an，…这里an是数列的“项”，n是“项数”。若能找到“项”与“项数”的关系，则知道了项数n，也就知道了项an。另一方法是研究相邻两项或几项的关系，这样，知道了最初的几项后，后面的项就可利用关系顺次写出来。例11给出一个“三角形”的数表如下：此表构成的规则是：第一行是0，1，2，…，999，以后下一行的数是上一行相邻两数的和。问：第四行的数中能被999整除的数是