小学奥数构造与论证教师版

《小学奥数构造与论证教师版》由会员分享，可在线阅读，更多相关《小学奥数构造与论证教师版（14页珍藏版）》请在金锄头文库上搜索。

1、教学目标1. 掌握最佳安排和选择方案的组合问题.2. 利用基本染色去解决相关图论问题知识点拨各种探讨给定要求能否实现，在论证中，有时需进行分类讨论，有时则要着眼于极端情形，或从整体把握设计最佳安排和选择方案的组合问题，这里的最佳通常指某个量达到最大或最小解题时，既要构造出取得最值的具体实例，又要对此方案的最优性进行论证论证中的常用手段包括抽屉原则、整除性分析和不等式估计组合证明题，在论证中，有时需进行分类讨论，有时则需要着眼于极端情况，或从整体把握。若干点及连接它们的一些线段组成图，与此相关的题目称为图论问题。若干点及连接它们的一些线段组成图，与此相关的题目称为图论问题，这里宜从特殊的点或线着

2、手进行分析各种以染色为内容，或通过染色求解的组合问题，基本的染色方式有相间染色与条形染色例题精讲模块一 最佳安排和选择方案【例 1】 一个盒子里有 400 枚棋子，其中黑色和白色的棋子各 200 枚下面我们对这些棋子做如下操作：每次拿出 2 枚棋子，如果颜色相同，就补 1 枚黑色棋子回去；如果颜色不同，就补 1 枚白色的棋子回去这样的操作，实际上就是每次都少了 1 枚棋子，那么，经过 399 次操作后，最后剩下的棋子是 颜色(填“黑”或者“白”)【 在每一次操作中，若拿出的两枚棋子同色， 则补黑子 1 枚，所以拿出的白子可能为 0 枚或 2 枚；若拿出的两枚棋子异色，则补白子 1 枚， “两枚

3、棋子异色”说明其中一黑一白，那么此时拿出的白子数为 0 枚可见每次操作中拿出的白子都是偶数枚，而由于起初白子有 200 枚，是偶数枚，所以每次操作后剩下的白子都是偶数枚，因此最后 1 枚不可能是白子，只能是黑子【例 2】 5 卷本百科全书按从第 1 卷到第 5 卷的递增序号排列，今要将它们变为反序排列，即从第 5 卷到第 1 卷如果每次只能调换相邻的两卷，那么最少要调换多少次?第十三讲：构造与论证【 因为必须是调换相邻的两卷，将第 5 卷调至原来第 1 卷的位置最少需 4 次，得到的顺序为 51234；现在将第 4 卷调至此时第 l 卷的位置最少需 3 次，得到的顺序为 54123；现在将第

4、3 卷调至此时第 l 卷的位置最少需 2 次，得到的顺序为 54312；最后将第 l 卷和第 2 卷对调即可所以，共需调换 4+3+2+1=10 次【例 3】 有 3 堆小石子，每次允许进行如下操作：从每堆中取走同样数目的小石子，或是将其中的某一石子数是偶数的堆中的一半石子移入另外的一堆开始时，第一堆有 1989 块石子，第二堆有989 块石子，第三堆有 89 块石子问能否做到：、(1)某 2 堆石子全部取光? (2)3 堆中的所有石子都被取走?【 (1)可以，如(1989，989，89) (1900，900，0) (950，900，950) (50，0，50) (25，25，50)(O，0，

5、25)(2)因为操作就两种，每堆取走同样数目的小石子，将有偶数堆石子堆中一半移至另一堆，所以每次操作石子总数要么减少 3 的倍数，要么不变现在共有 1989+989+89=3067，不是 3 的倍数，所以不能将 3 堆中所有石子都取走【例 4】 n 支足球队进行比赛，比赛采用单循环制，即每对均与其他各队比赛一场.现规定胜一场得 2 分，平一场得 1 分，负一场得 0 分.如果每一队至少胜一场，并且所有各队的积分都不相同，问：（1）n=4 是否可能？（2）n=5 是否可能？【 （1）我们知道 4 个队共进行了 场比赛，而每场比赛有 2 分产24C生，所以 4 个队的得分总和为 2=12.因为每一

6、 队至少胜一场，所以得分最低的队至少得 2 分，又要求每个队的得分都不相同，所以 4 个队得分最少 2+3+4+5=1412，不满足.即 n=4不可能。（2）我们知道 5 个队共进行 场比赛，而每场比赛有 2 分产生，25所以 4 个队的得分 总和为 2=20.因为每一队至少胜一 场，C所以得分最低的队至少得 2 分，又要求每个队的得分都不相同，所以 5 个队得分最少为 2+3+4+5+6=20，满足.即 n=5 有可能.但是我们必 须验证是否存在 实例.如下所示，A 得 2 分， C得 3 分，D 得 4 分，B 得 5 分， E 得 6 分.其中“A B”表示A、B 比 赛时，A 胜 B；

7、“B-C”表示 B、C 比赛时，B 平 C，余下类推.【例 5】 如图 35-1，将 1，2，3，4，5，6，7，8，9，10 这 10 个数分别填入图中的 10 个圆圈内，使任意连续相邻的 5 个圆圈内的各数之和均不大于某个整数 M.求 M 的最小值并完成你的填图.【 要使 M 最小，就要尽量平均的填写，因 为如果有的连续 5 个圆圈内的数特别小，有的特别大，那么 M 就只能大于等于特 别大的数，不能达到尽量小的目的因为每个圆圈内的数都用了 5 次，所以 10 次的和 为 5(1+2+3+10)=275每次和都小于等于朋，所以 IOM 大于等于 275，整数 M 大于 28下面来验证 M=2

8、8 时是否成立，注意到圆圈内全部数的总 和是 55，所以肯定是一边五个的和是 28，一边是 27因为数字都不一样 ，所以和 28 肯定是相间排列，和 27 也是相问排列，也就是说数组每隔 4 个差值为 l，这样从 1 填起，容易排出适当的填图.【例 6】 （2009 年清华附中入学测试题）如图，在时钟的表盘上任意作 个 的扇形，使得每一个扇9120形都恰好覆盖 个数，且每两个扇形覆盖的数不全相同，求证：一定可以找到 个扇形，恰好4 3覆盖整个表盘上的数并举一个反例说明，作 个扇形将不能保证上述结论成立8 1110987 6 5 432112【 要在表盘上共可作出 12 个不同的扇形，且 112

9、 中的每个数恰好被 4 个扇形覆盖将这 12 个扇形分为 4 组，使得每一 组的 3 个扇形恰好盖住整个表盘那么，根据抽 屉原理，从中选择 9 个扇形，必有 个扇形属于同一组，那么这一组的 3 个扇形可以覆盖整个表 盘913另一方面，作 8 个扇形相当于从全部的 12 个扇形中去掉 4 个， 则可以去掉盖住同一个数的 4 个扇形，这样这个数就没有被剩下的 8 个扇形盖住，那么 这 8 个扇形不能盖住整个表 盘【例 7】 一组互不相同的自然数，其中最小的数是 l，最大的数是 25，除 1 之外，这组数中的任一个数或者等于这组数中某一个数的 2 倍，或者等于这组数中某两个数之和.问：这组数之和的最

10、小值是多少?当取到最小值时，这组数是怎样构成的?【 首先把这组数从小到大排列起来，那么最小的肯定为 1，1 后面只能是 1 的 2 倍即 2，2 后面可以是 3 或 4，3 的后面可以是 4，5，6；4 的后面可以是 5，6，8最大的 为 25下面将所有的可能情况列出：l，2，3，4，25 所有的和是 35；l，2，3，5，25 所有的和是 36；1，2，3，6，25 所有的和是 37；1，2，4，5，25 所有的和是 37；1，2，4，6，25 所有的和是 38；1，2，4，8，25 所有的和是 40.25 是奇数，只能是一个偶数加上一个奇数在中间省略的数中不能只有 1 个数，所以至少还要添

11、加两个数，而且这两个数的和不能小于 25，否 则就无法得到 25 这个数要求求出最小值，先看这两个数的和是 25 的情况，因为 省略的两个数不同于前面的数，所以从 20+5 开始25=20+5=19+6=18+7=17+8=16+9=15+10=14+11=13+12这些数中 20，19，18，17 太大，无法产生，所以看： 16+9=15+10=14+11=13+12看这些谁能出现和最小的 l，2，3，4，25 中，检验发现没有可以满足的：再看 l，2，3，5，25，发现 1，2，3，5，10，15，25 满足，所以：1+2+3+5+10+15+25=36+25=61【例 8】 2004 枚

12、棋子，每次可以取 1、3、4、7 枚，最后取的获胜。甲、乙轮流取，如果甲先取，如何才能保证赢？【 先从简单的情况看起，看看棋子数量 较少时，在什么情况下先取者胜，什么情况下后取者胜可以列表如下：棋子数量 先取者胜 后取者胜1 枚 2 枚 3 枚 4 枚 5 枚 (1)6 枚 7 枚 8 枚 9 枚 (1)10 枚 11 枚 312 枚 (48)13 枚 1014 枚 15 枚 (7)16 枚 17 枚 1618 枚 19 枚 (3)20 枚 4棋子数是 18 时比较容易看得出来是先取者胜还是后取者胜，可以看出只有棋子数是 2 枚和 8枚时是后取者胜，其他情况下都是先取者 胜当棋子数大于 8 时

13、，可以先取若干枚棋子，使得剩下的棋子数变成前面已有的棋子数先取者为了取胜，第一次取后，应该使剩下的棋子数是后取者胜的情况，比如变成剩下 2 枚或 8 枚这样推下去，可以发现只有当棋子数是 8 的倍数或者除以 8 余 2 时，是后取者 胜，其他情况下是先取者胜题目中有 2004 枚棋子，除以 8 余 4，所以先取者肯定可以取胜不过取胜的策略比较灵活，不能明确地说每次后取者取多少枚先取者就相应地取多少枚，应该从除以 8 的余数来考虑：先取者第一次可以先取 4 枚， 这样还剩下 2000 枚， 2000 除以 8 的余数是 0；先取者为了保证获胜，在每一次后取者取了之后，先取者再取的时候，应该使得自

14、己取后剩下的棋子数是 8 的倍数或者除以 8 余 2；后取者每次可以取 1，3，4，7 枚，每次先取者取后剩下的棋子数除以 8 的余数是 0 或 2，所以每次后取者取后剩下的棋子数除以 8 的余数是 7，5，4，1 或 1，7，6，3.所以接下来先取者可以对应地取 7，3，4，1 或 1，7，4，3 枚棋子，这样剩下的剩下的棋子数除以 8的余数为 0，2，0，0 或 0，0，2，0.这样就保证了第点每次先取者取后剩下的棋子数除以 8 的余数是 0 或 2，那么最后一枚棋子肯定是先取者取得，所以先取者获胜【例 9】 在 1019 方格表的每个方格内，写上 0 或 1，然后算出每行及每列的各数之和

15、问最多能得到多少个不同的和数?【 首先每列的和最少为 0，最多是 10，每行的和最少是 0，最多是 19，所以不同的和最多也就是0，1，2，3，4，18，19 这 20 个下面我们说明如果 0 出现，那么必然有另外一个数字不能出 现如果 0 出现在行的和中，说明有 1 行全是 0，意味着列的和中至多出现 0 到 9，加上行的和至多出现 10 个数字，所以少了一种可能如果 0 出现在列的和中， 说明在行的和中 19 不可能出 现，所以 0 出现就意味着另一个数字不能出现，所以至多是 19，下面 给出一种排出方法.【例 10】 在 88 的国际象棋盘上最多能够放置多少枚棋子，使得棋盘上每行、每列及

16、每条斜线上都有偶数枚棋子?【 因为 88 的国际象棋盘上的每行、每列都正好有偶数格，若某行(某列)有空格，必空偶数格而斜线上的格子数有奇也有偶，不妨从左上角的斜线看起：第一条斜 线只有 1 格，必空；第三条有 3 格，必至少空 1 格；第五、七条分 别 有 5、7 格，每条 线上至少空 1 格由对称性易知共有 16 条斜线上有奇数格，且这 16 条斜线没有共用的格子，故至少必空出 16 格其实，空出两条主对角线上的16 个格子就合题意此 时，最多可放置 48 枚棋子，放在除这两条主对角线外的其余格子中，如下图所示【例 11】 在下图中有 16 个黑点，它们排成了一个 44 的方阵用线段连接其中 4 点，