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

《《数学奥林匹克专题讲座》第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。　　说明：这里我们采用了枚举与筛选并用的策略，即依据

3、题中限定的条件，面对枚举出的情况逐步排除不符合条件的三位数，确定满足条件的三位数，从而找到问题的答案。　　例2哥德巴赫猜想是说：每个大于2的偶数都可以表示为两个质数之和。问：168是哪两个两位数的质数之和，并且其中一个的个位数是1？　　解：168表示成两个两位质数之和，两个质数都大于68。个位是1且大于68的两位数有71，81，91，其中只有71是质数，所以一个质数是71，另一个质数是168-71=97。　　说明：解此题要求同学们记住100以内的质数。如果去掉题目中“其中一个的个位数是1”的条件，那么上述答案不变，仍是唯一的解答。　　如果

4、取消位数的限制，那么还有　　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）。　　每一对币值中有一个

5、可用若干枚贰分和伍分硬币构成，则另一个也可以，显然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分。　　综合以上分

6、析，不能用若干枚贰分和伍分硬币构成的1分到1元之间的币值只有四种，即1分、3分、97分、99分。　　例4一个两位数被7除余1，如果交换它的十位数字与个位数字的位置，所得到的两位数被7除也余1，那么这样的两位数有多少个？都是几？　　　　两式相减，得9（a-b）=7（n-m）。于是7

7、9（a-b）。因为（7，9）=1，所以7

8、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时

9、，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分别填入左下图所示的表格内，使得每行相邻的两个数左边

10、的小于右边的，每列的两数上面的小于下面的。问：有几种填法？　　　　解：如右上图，由已知可得a最小，f最大，即a=1，f=6。根据b与d的大小，可分两种情况讨论。　　当b＜d时，有b=2，c=3