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

1、数学奥林匹克专题讲座 第16讲 枚举、归纳与猜想一、枚举法枚举法起源于原始的计数方法，即数数。关于这方面的例子，我们在第11讲中已介绍过，现在我们从另一角度来利用枚举法解题。当我们面临的问题存在大量的可能的答案（或中间过程），而暂时又无法用逻辑方法排除这些可能答案中的大部分时，就不得不采用逐一检验这些答案的策略，也就是利用枚举法来解题。采用枚举法解题时，重要的是应做到既不重复又不遗漏，这就好比工厂里的质量检验员的责任是把不合格产品挑出来，不让它出厂，于是要对所有的产品逐一检验，不能有漏检产品。例1 一个小于400的三位数，它是平方数，它的前两个数字组成的两位数还是平方数，其个位数也是一个平方数

2、。求这个三位数。解：这道题共提出三个条件：（1）一个小于400的三位数是平方数；（2）这个三位数的前两位数字组成的两位数还是平方数；（3）这个三位数的个位数也是一个平方数。我们先找出满足第一个条件的三位数：100，121，144，169，196，225， 256， 289， 324， 361。再考虑第二个条件，从中选出符合条件者：169，256，361。最后考虑第三个条件，排除不合格的256，于是找到答案是169和361。说明：这里我们采用了枚举与筛选并用的策略，即依据题中限定的条件，面对枚举出的情况逐步排除不符合条件的三位数，确定满足条件的三位数，从而找到问题的答案。例2哥德巴赫猜想是说：每

3、个大于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多年的历史了，它是数论中最有名的问题，中外许多著名的数学家都研

4、究过，包括我国著名数学家华罗庚教授。例 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分

5、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，

6、即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

7、，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枚硬币。如果天平平衡，那么所剩

8、一枚为伪币，于是取一枚伪币和一枚真币分放在天平两端，即可判明真币与伪币谁轻谁重。如果天平不平衡，那么取下重端的50枚硬币，并将轻端的50枚硬币分放两端各25枚，若此时天平平衡，则说明伪币在取下的50枚硬币中，即伪币比真币重；若此时天平仍不平衡，则说明伪币在较轻的50枚硬币中，即伪币比真币轻。在上述解答过程中，我们面临着“平衡”或“不平衡”两种可能的状态，对这两种状态，逐一检验，即得到问题的结论。由上述例题可以看出运用枚举法的关键在于：（1）如何将整体分解成各个特殊情况，也就是要注意分类的方法，分类必须适合于一一列举和研究，同时分类必须不重也不漏。（2）善于对列举的结果进行综合考察（包括筛选），

9、并导出结论。二、归纳与猜想“猜想”是一种重要的思维方法，对于确定证明方向，发现新定理，都有重大意义。最著名的例子就是哥德巴赫猜想，1742年曾任中学教师的哥德巴赫和大数学家欧拉通过观察实例：6=33，8=35，10=37，12=57，14=311，16=313，18=711，提出如下猜想：“任何大于或等于6的偶数，都可以表示成两个奇素数之和。”这就是闻名于世的哥德巴赫猜想，至今还没有给以逻辑证明，所以仍是一个猜想。二百多年以来，她像一颗璀璨夺目的明珠，吸引了无数数学家和数学爱好者为之奋斗。通过观察若干具体实例，发现存在于它们之中的某种似乎带规律性的东西，我们相信它具有普遍意义，对更多更一般的实

10、例同样适用，从而把它当做一般规律或结论，这种发现规律或结论的方法就是归纳法。当然，归纳出来的规律或结论一般来说还只是一种猜想，它是否正确，还有待于进一步证明。例如，我们可能碰巧看到182764=100，改变一下形式：13233343=102=（1234）2。这个形式很规则，这是偶然的，还是确有这样的规律？不妨再试验一下：1323=9=32=（12）2，132333=36=62=（123）2。再多一些数试验一下：1323334353=225=152=（12345）2。于是猜想：又如，求凸n边形内角和。观察分析：三角形内角和为180°；四边形可分为2个三角形，故内角和为2×18

11、0°；五边形可分为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，所以应填入括号里的数是174=21。（2）像（1

12、）那样考虑难以发现规律，改变一下角度，把各数改写为可以发现：（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。说明：从上面例子可以看到，观察时不可把眼光停留在某一点上固定不变，而要注意根据问题特点不断调整自己观察的角度，以利于观察出有一定隐蔽性的内在规律。例

13、8下面是七个分数：先约分，请你再划去一个与众不同的数，然后按照一定的规律将余下的六个数排列起来，并按你的规律接下去写出第七个数。分析：约分是容易的，除其中一个数外，另外六个数必有联系。解：已给分数经约分后是说明：这个题目里给出了解题的操作指示，即化简、按规律分类、排序、添加新数，做起来感觉很顺利、轻松。做完题后体会一下命题者的用意，他是想让学生了解和学会怎样归纳和猜测。在许多问题中，各元素从表面上看没什么联系，也看不出什么规律，这就需要我们像做约分那样透过表面看本质，扒掉“披在元素身上花花绿绿的外衣”，从而发现彼此间的共性和联系。这个题的命题者给出了一个做归纳和猜测的示范，应引起读者重视。例9

14、将正方形纸片如下图所示由下往上对折，再由左向右对折，称为完成一次操作。按上述规则完成五次操作以后，剪去所得小正方形的左下角。问：当展开这张正方形纸片后，一共有多少个小洞孔？解：一次操作后，层数由1变为4，若剪去所得小正方形左下角，展开后只有1个小洞孔，恰是大正方形的中心。连续两次操作后，折纸层数为42，剪去所得小正方形左下角，展开后大正方形留有42-1=41=4（个）小洞孔。连续三次操作后，折纸层数为43，剪去所得小正方形左下角，展开后大正方形上留有43-1=42=16（个）小洞孔。按上述规律不难断定：连续五次操作后，折纸层数为45，剪去所得小正方形左下角，展开后大正方形纸片上共留有小洞孔45

15、-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+

16、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）=12×（1210）=111。第25个拐弯处的数是：a25=1+（1+1+2+2+12+12+13）=1112×（1112）13=170。说明：（1）这个数列的一般项可以写成第2n（偶数）项为a2n=12×（12n）=1nn2；第（2n+1）（奇数）项为a2n1=12×（12n）（n1）=22nn2。（2）寻找数列排列的规律，常用两种方法：一是考察数列的“项”与它所在的位置即“项数”之间的关系，一般的数列写作

17、a1，a2，a3，an，这里an是数列的“项”，n是“项数”。若能找到“项”与“项数”的关系，则知道了项数n，也就知道了项an。另一方法是研究相邻两项或几项的关系，这样，知道了最初的几项后，后面的项就可利用关系顺次写出来。例11给出一个“三角形”的数表如下：此表构成的规则是：第一行是0，1，2，999，以后下一行的数是上一行相邻两数的和。问：第四行的数中能被999整除的数是什么？解：首先找出第四行数的构成规律。通过观察、分析，可以看出：第四行的任一个数都和第一行中相应的四个相邻的数有关，具体关系可以从下表看出：如果用an表示第四行的第n个数，那么an=8n+4。现在要找出an=8n+4=999

18、k的an，显然k应是4的倍数。注意到第四行中最大的数是7980999×8，所以k=4。由此求出第四行中能被999整除的数是999×4=3996，它是第四行的第（3996-4）÷8=499（项），即a499=3996。说明：本题通过观察、归纳找出第四行的构成规律，即第n个数的通项公式。当然通项公式也可以直接通过观察第四行各数的排列规律来发现，即把第四行的前后几个数算出来：12，20，28，36，7980。观察分析发现：后一个数都比前一个数多8，从而归纳出通项公式为：an=8n+4。例12在平面上有n条直线，任何两条都不平行，并且任何三条都不交于同一点，这些直线能把平

19、面分成几部分？解：设n条直线分平面为Sn部分，先实验观察特例有如下结果： n与Sn之间的关系不太明显，但Sn-Sn-1有如下关系： 观察上表发现，当n2时，有Sn-Sn-1=n。因为在（n-1）条直线后添加第n条直线被原（n-1）条直线截得的n段中的任何一段都将它所在的原平面一分为二，相应地增加n部分，所以Sn=Sn-1+n，即Sn-Sn-1=n。从而S2-S1=2，S3-S2=3，S4-S3=4，Sn-Sn-1=n。将上面各式相加，得到Sn-S1=2+3+n，Sn=S1+2+3+n=2+2+3+n=1+（1+2+n）说明：Sn也可由如下观察发现。由上表知：S1=1+1，S2=1+1+2，S3

20、=1+1+2+3，S4=1+1+2+3+4，依此类推，便可猜想到  练习16 1.用数字1，3，4，5，7，8，9组成没有重复数字的四位数，得到的数从小到大排成一列。问：第119个数是几？2.同时满足下列条件的分数共有多少个？（2）分子和分母都是质数；（3）分母是两位数。请列举出所有满足条件的分数。3.用一个三位数乘945，使所得的乘积为平方数，这样的数共有几个？最大的与最小的各是多少？4.A，B，C三人中，一部分是总说真话的老实人，另一部分是总说假话的骗子。A说：“若C是老实人，则B是骗子。”C说：“A和我不都是老实人，也不全是骗子。”问：A，B，C三人中，谁是老实人？谁是骗子？5

21、.现有如下一系列图形：当时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）现已知某个平

22、面图有999个顶点，且围成了999个区域，试根据以上关系确定这个图有多少条边。7.有一列数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这样每隔一个数擦去一个数，转圈擦下去。问：最后剩下一个数时，剩下的是哪个数？练习16 1.1985。解：按从小到大无重复数字的四位数顺序，前

23、两位数是13的有20个；前两位数是14的有20个；前两位数是19的有20个。即为1987，那么第119个数就是1985。提示：由（1）知分子是大于1，且小于20（因为分母是两位数）的质数。然后就分子为2，3，5，7，11，13，17，19逐一枚举，推出共有13个分数满足要求。3.945，105。解：因为945=33×5×7，要使它乘上一个数后成为平方数，必须使乘积中各质因数的个数成为偶数，所以，所乘的数必须是 3×5×7=105与另一平方数的乘积。因为105×12=105，105×22=620，105×32=945，所以，与

24、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时，直角三角形有2×12个，边数=2×1×（1+1）+12=5；n=2时，直角三角形有2×22个，边数=2×2×（2+1）22=16；n=3时，直角三角形有2×32个，边数=2&#

25、215;3×（3+1）+32=33。对一般的n，共分为2×n2个直角三角形，边数=2n（n+1）+n2。所以n=100时，共分为2×1002=20000（个）直角三角形，共有2×100×（100+1）+1002=30200（条）边。6.（1）填表如下：（2）由该表可以看出，所给四个平面图的顶点数、边数及区域数之间有下述关系：4+3-6=1，8+5-12=1，6+4-9=1，10+6-15=1。所以，我们可以推断：任何平面图的顶点数、边数及区域数之间，都有下述关系：顶点数+区域数-边数=1。（3）由上面所给的关系，可知所求平面图的边数。边数=顶点数+区域数-1=99