35构造与论证汇总

《35构造与论证汇总》由会员分享，可在线阅读，更多相关《35构造与论证汇总（10页珍藏版）》请在装配图网上搜索。

1、各种探讨给定要求能否实现，设计最佳安排和选择方案的组合问题这里的最佳通常指某个量达到最大或最小解题时，既要构造出取得最值的具体实例，又要对此方案的最优性进行论证论证中的常用手段包括抽屉原则、整除性分析和不等式估计1. 5 卷本百科全书按从第 1 卷到第 5 卷的递增序号排列，今要将它们变为反序排列，即从第5卷到第 1 卷如果每次只能调换相邻的两卷，那么最少要调换多少次?【分析与解】 因为必须是调换相邻的两卷，将第5 卷调至原来第1 卷的位置最少需4次，得到的顺序为51234；现在将第 4卷调至此时第l 卷的位置最少需3次，得到的顺序为54123；现在将第 3卷调至此时第l 卷的位置最少需2次，

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

3、，将有偶数堆石子堆中一半移至另一堆，所以每次操作石子总数要么减少3 的倍数，要么不变现在共有1989+989+89=3067，不是 3 的倍数，所以不能将3 堆中所有石子都取走3. 在 19971997 的正方形棋盘上的每格都装有一盏灯和一个按钮按钮每按一次，与它同一行和同一列方格中的灯泡都改变一次状态，即由亮变为不亮，或由不亮变为亮如果原来每盏灯都是不亮的，请说明最少需要按多少次按钮才可以使灯全部变亮?【分析与解】最少要 1997 次，将第一列中的每一格都按一次，则除第一列外，每格的灯都只改变一次状态，由不亮变成亮而第一列每格的灯都改变1997 次状态，由不亮变亮如果少于 1997 次，则至

4、少有一列和至少有一行没有被按过，位于这一列和这一行相交处的灯保持原状，即不亮的状态4. 在某市举行的一次乒乓球邀请赛上，有 3 名专业选手与 3 名业余选手参加 . 比赛采用单循环方式进行，就是说每两名选手都要比赛一场为公平起见，用以下方法记分：开赛前每位选手各有 10 分作为底分，每赛一场，胜者加分，负者扣分，每胜专业选手一场加2 分，每胜业余选手一场加1 分；专业选手每负一场扣2 分，业余选手每负一场扣1 分问：一位业余选手最少要胜几场，才能确保他的得分比某位专业选手高?【分析与解】当一位业余选手胜2 场时，如果只胜了另两位业余选手，那么他得10+2-3=9( 分此时，如果专业选手间的比赛

5、均为一胜一负，而专业选手与业余选手比赛全胜，那么每位专业选手的得分都是10+2- 2+3=13( 分所以，一位业余选手胜2 场，不能确保他的得分比某位专业选手高当一位业余选手胜3 场时，得分最少时是胜两位业余选手，胜一位专业选手，得10+2+2-2=12( 分此时，三位专业选手最多共得30+0+4=34( 分，其中专业选手之间的三场比赛共得0分，专业选手与业余选手的比赛最多共得4 分 . 由三个人得34 分， 343=11，推知，必有人得分不超过11 分.也就是说，一位业余选手胜3 场，能确保他的得分比某位专业选手高.n 支足球队进行比赛，比赛采用单循环制，即每对均与其他各队比赛一场.现规5定

6、胜一场得 2 分，平一场得1 分，负一场得0 分 . 如果每一队至少胜一场，并且所有各队的积分都不相同，问：（ 1） n=4 是否可能？（ 2） n=5 是否可能？【分析与解】（ 1）我们知道4 个队共进行了场比赛，而每场比赛有2 分产生，所以4 个队的得分总和为 2=12.所以因为每一队至少胜一场，所以得分最低的队至少得 4 个队得分最少 2+3+4+5=1412，不满足 . 即2 分，又要求每个队的得分都不相同， n=4 不可能 .（ 2）我们知道5 个队共进行场比赛，而每场比赛有2 分产生，所以4 个队的得分总和为 2=20.因为每一队至少胜一场，所以得分最低的队至少得2 分，又要求每个

7、队的得分都不相同，所以5 个队得分最少为2+3+4+5+6=20，满足 . 即 n=5 有可能 . 但是我们必须验证是否存在实例 .如下所示， A得 2分， C得 3 分，D得 4分，B得 5 分，E得 6分.其中“ AB”表示 A、 B 比赛时， A 胜 B；“ B-C ”表示 B、 C比赛时， B 平 C，余下类推 .6. 如图 35-1 ，将 1， 2， 3， 4， 5， 6， 7， 8， 9，10 这 10 个数分别填入图中的10 个圆圈内，使任意连续相邻的5 个圆圈内的各数之和均不大于某个整数M.求 M的最小值并完成你的填图.【分析与解】要使圆圈内的数特别小，有的特别大，那么的M最小

8、，就要尽量平均的填写，因为如果有的连续M就只能大于等于特别大的数，不能达到尽量小的目5 个因为每个圆圈内的数都用了5 次，所以10 次的和为5 (1+2+3+10=275每次和都小于等于朋，所以IOM 大于等于275，整数M大于28下面来验证和是 28，一边是也就是说数组每隔M=28时是否成立，注意到圆圈内全部数的总和是55，所以肯定是一边五个的27因为数字都不一样，所以和28 肯定是相间排列，和27 也是相问排列，4 个差值为l ，这样从1 填起，容易排出适当的填图.7(1 将 1， 2， 3， 4， 5， 6，7， 8， 9 这减小不小于3 且不大于59 个数字排列在圆周上，使得任意相邻两

9、数的差( 大(2对于1 至11 这11 个数字，(3对于1 至12 这12 个数字，(4对于l至 14这14 个数字，满足上述要求的排列方法是否存在?【分析与解】(1 对于 l 至 9 这九个数，注意到可与1 相邻的数是4、 5、 6，可与 9 相邻的数也是4、 5、 6，而 1、 9 又不可相邻，从而4、 5、 6 这三个数只可能分别在1、 9 之间及 1和 9 的另一侧以此为突破口，构造一种合题意的填法即可例如：可以在圆周上依次填入1、 6、 2、 7、3、 8、 4、 9、 5(2 对于 1 至 11 这十一个数， 1、 2,3 、 9、 10、 11 这六个数中任意两数不能相邻，余下4

10、、 5、 6、 7、8 这五个数要填在前六个数的六个空隙中，显然是不可能的(3 对于 1 至 12 这十二个数， 1、 2、 3、 10、 11、 12 这六个数中任意两数不能相邻，余下4、 5、 6、 7、8、 9 这六个数要填在前六个数的六个空隙中，恰好一个空隙填一个数又注意到 9 不与 1、2、 3、 10、 11 相邻，所以9 只能一侧与12 相邻，可另一侧必与11、 10、 3、 2、1 中的某一个相邻，这是不符合要求的.(4 对于 1 至 14 这十四个数， 1,2 、 3、 12、 13、 14 这六个数中任意两个数不能相邻，余下 4,5 、 6、 7、 8、 9、 10、 11

11、 这八个数要填在前六个数的六个空隙中，必有两个空隙均填了两个数或有一个空隙中填了三个数再具体构造一种填法即可，例如在圆周上依次放置1、 5、2、 6、 3、 7、12、 9、 13、 10、 14、11、 8、 4 即符合要求8. 1998 名运动员的号码依次为 1 至 1998 的自然数现在要从中选出若干名运动员参加仪仗队，使得剩下的运动员中没有一个人的号码等于另外两人的号码的乘积那么，选为仪仗队的运动员最少有多少人 ?【分析与解】 我们很自然的想到把用得比较多的乘数去掉，因为它们参与的乘式比较多，把它们去掉有助于使剩下的构不成乘式，比较小的数肯定是用得最多的，因为它们的倍数最多，所以考虑先

12、把它们去掉，但关键是除到何处?考虑到 44 的平方为 1936，所以去到 44 就够了，因为如果剩下的构成了乘式，那么乘式中最小的数一定小于等于 44，所以可以保证剩下的构不成乘式因为对结果没有影响，所以可以将 1 保留，于是去掉 2， 3， 4， ， 44 这 43 个数但是，是不是去掉43 个数为最小的方法呢?构造 2 97， 3 96， 4 95， ， 44 45，发现这 43 组数全不相同而且结果都比1998 小，所以要去掉这些乘式就至少要去掉以 43 位最小值，即为所求.43 个数，所9. 组互不相同的自然数，其中最小的数是l ，最大的数是 25，除 1 之外，这组数中的任一个数或者

13、等于这组数中某一个数的2 倍，或者等于这组数中某两个数之和值是多少 ?当取到最小值时，这组数是怎样构成的?. 问：这组数之和的最小【分析与解】首先把这组数从小到大排列起来，那么最小的肯定为2 倍即 2，2 后面可以是3 或 4， 3 的后面可以是4， 5， 6； 4 的后面可以是251， 1 后面只能是1 的5， 6， 8最大的为下面将所有的可能情况列出：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；

14、1， 2，4， 8， ， 25所有的和是 40.25 是奇数，只能是一个偶数加上一个奇数在中间省略的数中不能只有少还要添加两个数，而且这两个数的和不能小于25，否则就无法得到1 个数，所以至25 这个数要求求出最小值，先看这两个数的和是所以从 20+5 开始25 的情况，因为省略的两个数不同于前面的数，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 ，

15、 2， 3，5， ， 25，发现 1， 2， 3，5， 10， 15， 25 满足，所以： 1+2+3+5+10+15+25=36+25=6110. 在 1019 方格表的每个方格内，写上 0 或 1，然后算出每行及每列的各数之和问最多能得到多少个不同的和数 ?【分析与解】 首先每列的和最少为 0，最多是 10，每行的和最少是 0，最多是 19，所以不同的和最多也就是 0， 1， 2， 3， 4， ， 18，19 这 20 个下面我们说明如果0 出现，那么必然有另外一个数字不能出现如果 0 出现在行的和中，说明有 1 行全是和至多出现 10 个数字，所以少了一种可能0，意味着列的和中至多出现0

16、 到9，加上行的如果 0 出现在列的和中，说明在行的和中19 不可能出现，所以能出现，所以至多是19，下面给出一种排出方法.0 出现就意味着另一个数字不11在 88的国际象棋盘上最多能够放置多少枚棋子，使得棋盘上每行、每列及每条斜线上都有偶数枚棋子?【分析与解】因为 88的国际象棋盘上的每行、每列都正好有偶数格，若某行( 某列有空格，必空偶数格而斜线上的格子数有奇也有偶，不妨从左上角的斜线看起：第一条斜线只有1 格，必空；第三条有3 格，必至少空1 格；第五、七条分别有5、 7 格，每条线上至少空格由对称性易知共有16 条斜线上有奇数格，且这16 条斜线没有共用的格子，故至少必空出16 格其实

17、，空出两条主对角线上的16 个格子就合题意1此时，最多可放置48 枚棋子，放在除这两条主对角线外的其余格子中，如右图所示12在 1000 1000 的方格表中任意选取n 个方格染为红色，都存在心构成一个直角三角形的顶点求n 的最小值3 个红色方格，它们的中【分析与解】首先确定1998 不行反例如下：其次 1999 可能是可以的，因为首先从行看，1999 个红点分布在1000 行中，肯定有一些行含有 2 个或者以上的红点，因为含有0 或 1 个红点的行最多999 个，所以其他行含有红点肯定大于等于 1999-999=1000 ，如果是大于 1000，那么根据抽屉原理，肯定有两个这样红点在一列，那

18、么就会出现红色三角形；如果是等于1000 而没有这样的2 个红点在一列，说明有999 行只含有1 个红点，而剩下的一行全是红点，那也肯定已经出现直角三角形了，所以n 的最小值为199913 若干箱货物总重19.5 吨，每箱重量不超过353 千克那么最少需要多少辆载重量为1.5吨的汽车，才能保证把这些箱货物一次全部运走?【分析与解】至少需要16 辆车 15 辆车不一定能一次运完例如这批货物共有 65 只箱子， 64 只箱子都是 301 千克， 1 只箱的重量是 236 千克，那么总重量为 30164+236=19500(千克，恰好符合 19.5 吨的要求由于3015=1505(千克超过 1.5

19、吨因此，每辆汽车最多只能装4 只重量为301 千克的箱子， 15 辆汽车最多只能装415=60(只重量为 301 千克的箱子这样，必然有 4 只重量为 30l 千克的箱子无法再装运了16 辆汽车一定能一次运完全部箱子：首先让 12 辆汽车装到刚刚超过1.5 吨，即若取下最后装的一只箱子就不超过1.5 吨再从这 12 辆汽车上把每辆车最后装的那只箱子卸下来，并把这12 只箱子分别装上另外3 辆空车，每车4 箱，由于每车4 箱总重量不超过4353=1412(千克因此也不超过1.5 吨这时， 12+3=15 辆车就装完原来前12 辆车上的全部货物，总重量超过1.5 12=18(吨而且每辆车载重不超过

20、1.5 吨于是，剩下未装车箱子总重量不足19.5-18=1.5(吨可以把它们全部装在第16 辆车上运走14在图 35-2 中有 16 个黑点，它们排成了一个44的方阵用线段连接其中4 点，就可以画出各种不同的正方形现在要去掉某些点，使得其中任意4 点都不能连成正方形，那么最少要去掉多少个点?【分析与解】至少要除去6 个点，如下所示为几种方法：15 在正方体的 8 个顶点处分别标上 1，2， 3， 4，5， 6， 7，8，然后再把每条棱两端所标的两个数之和写在这条棱的中点问：(1各条棱中点处所写的数是否可能恰有5 种不同的数值 ?(2各条棱中点处所写的数是否可能恰有4 种不同的数值 ?【分析与解

21、】如下图所示各棱中点处所写的数恰有五种不同数值是可能的，如在 4、 B、 、 H 依次填7、 8、 4、 6、 2，则中点处恰有五个不同数值 6、8、 9、 10、 121、 5、3、不可能少于五种不同数值，这是因为：足a以 1 所在顶点为端点的棱有三条，不妨设这三条棱的另一端点所填写的数是，则这三条棱的中点处的数为1+ a， 1+b， 1+c，满足 1+a1+ba、 b、c，满足以 8 所在顶点为端点的棱也有三条，不妨设这三条棱的另一端点所填写的数为x、 y、 zx z，则这三条棱的中点处的数为8+ x， 8+y， 8+z，满足 8+ x8+y 9，所以1+a1+b1+c8+x8+y8+z从而这六条棱中点的六个数不可能少于五种不同的值，因此在各条棱中点处所写的数能恰有5种不同的数值，不能使各条棱中点处所写的数恰有同的取值为6， 8， 9， 10， 124 种不同的如：，对应5 种不