35构造与论证(一)汇总

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

2、少需 3 次，得到的顺序为 54123;现在将第 3 卷调至此时第 I 卷的位置最少需 2 次，得到的顺序为 54312;最后将第 I 卷和第 2 卷对调即可.所以，共需调换 4+3+2+仁 10 次.酸级数：車車車拿 E19曲牟罷十五届全俄盘学龛舐匹丸丸年缄第1魏2.有 3 堆小石子，每次允许进行如下操作：从每堆中取走同样数目的小石子，或是将其中的某一石子数是偶数的堆中的一半石子移入另外的一堆开始时，第一堆有1989 块石子，第二堆有989块石子， 第三堆有 89块石子.问能否做到： (1某2堆石子全部取光？(23堆中的所有石子都被取走？【分析与解】(1 可以，如(1989 , 989, 8

3、9(1900 , 900,0 -(950 , 900, 950 - (50 ,0, 50P(25 ,25, 50 (O,0, 25（2 因为操作就两种，每堆取走同样数目的小石子，将有偶数堆石子堆中一半移至另一堆，所 以每次操作石子总数要么减少3 的倍数，要么不变.现在共有 1989+989+89=3067,不是 3 的倍数，所以不能将 3 堆中所有石子都取走.矽蛾跌拿拿雀一3.在 1997X1997 的正方形棋盘上的每格都装有一盏灯和一个按钮.按钮每按一次，与它同一 行和同一列方格中的灯泡都改变一次状态，即由亮变为不亮，或由不亮变为亮如果原来每盏 灯都是不亮的，请说明最少需要按多少次按钮才可以

4、使灯全部变亮？【分析与解】 最少要 1997 次，将第一列中的每一格都按一次，则除第一列外，每格的灯都只改变一次状态，由不亮变成亮而第一列每格的灯都改变1997 次状态，由不亮变亮.如果少于 1997 次，则至少有一列和至少有一行没有被按过，位于这一列和这一行相交处 的灯保持原状，即不亮的状态.4.在某市举行的一次乒乓球邀请赛上，有3 名专业选手与 3名业余选手参加.比赛采用单循环方式进行，就是说每两名选手都要比赛一场.为公平起见，用以下方法记分：开赛前每位选手各有 10 分作为底分，每赛一场，胜者加分，负者扣分，每胜专业选手一场加2 分，每胜业余选手一场加 1 分；专业选手每负一场扣 2 分

5、，业余选手每负一场扣 1 分问：一位业余选手最 少要胜几场，才能确保他的得分比某位专业选手高？【分析与解】 当一位业余选手胜 2 场时，如果只胜了另两位业余选手，那么他得10+2-3=9（分此时，如果专业选手间的比赛均为一胜一负，而专业选手与业余选手比赛全胜，那么 每位专业选手的得分都是10+2-2+3=13（分所以，一位业余选手胜2 场，不能确保他的得分比某位专业选手高.当一位业余选手胜 3 场时，得分最少时是胜两位业余选手，胜一位专业选手，得10+2+2-2=12（分.此时，三位专业选手最多共得30+0+4=34（分，其中专业选手之间的三场比赛共得0I分，专业选手与业余选手的比赛最多共得4

6、 分.由三个人得 34 分，34 十 3=11，推知，必有人得分不超过 11 分.也就是说，一位业余选手胜3 场，能确保他的得分比某位专业选手高.5.n 支足球队进行比赛，比赛采用单循环制，即每对均与其他各队比赛一场.现规定胜一场得 2 分，平一场得 1 分，负一场得0分.如果每一队至少胜一场，并且所 有各队的积分都不相同，问：(1) n=4 是否可能？(2) n=5 是否可能？【分析与解】(1)我们知道 4 个队共进行了场比赛，而每场比赛有2 分产生，所以4 个队的得分总和为X2=12.因为每一队至少胜一场，所以得分最低的队至少得2 分，又要求每个队的得分都不相同，所以 4 个队得分最少 2

7、+3+4+5=14 12,不满足.即 n=4 不可能.(2)我们知道 5 个队共进行场比赛，而每场比赛有 2 分产生，所以 4 个队的得分总和为X2=20.因为每一队至少胜一场，所以得分最低的队至少得2 分，又要求每个队的得分都不相同，所以 5 个队得分最少为 2+3+4+5+6=20,满足.即 n=5 有可能.但是我们必须验证是否存在 实例.如下所示，A 得 2 分，C 得 3 分，D 得 4 分，B 得 5 分，E 得 6 分.其中“ B”表示AB 比赛时，A 胜 B;“ B-C ”表示 B、C 比赛时，B 平 C,余下类推c -c6.如图 35-1，将 1 , 2, 3, 4, 5, 6

8、, 7,8, 9, 10 这 10 个数分别填入图中的 10 个圆圈内, 使任意连续相邻的 5 个圆圈内的各数之和均不大于某个整数M.求 M 的最小值并完成你的填图分析与解】要使 圆圈内的数特别小，有的特别大，那么 的.下面来验证 M=28 时是否成立，注意到圆圈内全部数的总和是55，所以肯定是一边五个的和是 28, 一边是 27.因为数字都不一样，所以和 28 肯定是相间排列，和 27 也是相问排列， 也就是说数组每隔 4 个差值为 I，这样从 1 填起，容易排出适当的填图7.(1 将 1, 2, 3, 4, 5, 6, 7, 8, 9 这 9 个数字排列在圆周上，使得任意相邻两数的差(大减

9、小不小于 3 且不大于 5.(2 对于 1 至 11 这 11 个数字，(3 对于 1 至 12 这 12 个数字，(4 对于 I 至 14 这 14 个数字，满足上述要求的排列方法是否存在？【分析与解】(1 对于 I 至 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 这六个数中任意两数不能相邻

10、，余下4、5、6、7、8 这五个数要填在前六个数的六个空隙中，显然是不可能的.(3 对于 1 至 12 这十二个数，1、2、3、10、11、12 这六个数中任意两数不能相邻，余下4、5、6、7、& 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、& 9、10、11 这八个数要填在前六个数的

11、六个空隙中，必有两个空隙均填了两 个数或有一个空隙中填了三个数.再具体构造一种填法即可，例如在圆周上依次放置1、5、2、6、3、7、12、9、13、10、14、11、8、4 即符合要求.级数：車車車車8. 1998 名运动员的号码依次为 1 至 1998 的自然数.现在要从中选出若干名运动员参加仪仗 队，使得剩下的运动员中没有一个人的号码等于另外两人的号码的乘积那么，选为仪仗队M 最小，就要尽量因为每个圆圈内的数都用了5 次，所以10 次的和为 5X(1+2+3+10=275.每次和都小于等于朋，所以IOM 大于等于的运动员最少有多少人？【分析与解】 我们很自然的想到把用得比较多的乘数去掉，因

12、为它们参与的乘式比较多，把它们去掉有助于使剩下的构不成乘式，比较小的数肯定是用得最多的，因为它们的倍 数最多，所以考虑先把它们去掉，但关键是除到何处？考虑到 44 的平方为 1936，所以去到 44 就够了，因为如果剩下的构成了乘式，那么乘式 中最小的数一定小于等于44,所以可以保证剩下的构不成乘式因为对结果没有影响，所以可以将 1 保留，于这 43 个数.但是，是不是去掉 43 个数为最小的方法呢？构造 2X97, 3X96, 4X95,，44X45,发 现这 43组数全不相同而且结果都比1998 小,所以要去掉这些乘式就至少要去掉43 个数，所以 43 位最小值，即为所求觀愆级数：車拿車車

13、9. 组互不相同的自然数，其中最小的数是 I，最大的数是 25,除 1 之外，这组数中的任一个数 或者等于这组数中某一个数的 2 倍，或者等于这组数中某两个数之和 问：这组数之和的最小 值是多少？当取到最小值时，这组数是怎样构成的？【分析与解】 首先把这组数从小到大排列起来，那么最小的肯定为1, 1 后面只能是 1 的2 倍即 2, 2 后面可以是 3 或 4, 3 的后面可以是 4, 5, 6; 4 的后面可以是 5, 6, 8.最大的为 25.下面将所有的可能情况列出：I , 2, 3, 4,，25 所有的和是 35;I , 2, 3, 5,，25 所有的和是 36;1, 2, 3, 6,

14、，25 所有的和是 37;1, 2, 4, 5,，25 所有的和是 37;1, 2, 4, 6,，25 所有的和是 38;1, 2, 4, 8,，25 所有的和是 40.25 是奇数，只能是一个偶数加上一个奇数在中间省略的数中不能只有1 个数，所以至少还要添加两个数，而且这两个数的和不能小于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、15+10=14+1 仁 13+12.看这些谁能出现和最小的 I , 2, 3, 4,，25 中，检验发现没有可以满足的:再看 I , 2, 3, 5，25,发现 1, 2, 3, 5, 10, 15, 25 满足，所以：1+2+3+5+10+15+25=36+25=6110.在 10X19 方格表的每个方格内，写上0 或 1,然后算出每行及每列的各数之和问最多能得到多少个不同的和数？【分析与解】 首先每列的和最少为 0,最多是 10,每行的和最少是 0,最多是 19,所以 不同的和最多也就是 0, 1, 2, 3, 4,，18, 19 这 20 个.下面我们说明如果 0 出现，那么必然有另外

16、一个数字不能出现.如果 0 出现在行的和中，说明有 1 行全是 0,意味着列的和中至多出现 0 到 9，加上行的 和至多出现 10 个数字，所以少了一种可能.如果 0 出现在列的和中，说明在行的和中19 不可能出现，所以 0 出现就意味着另一个数字不能出现，所以至多是 19,下面给出一种排出方法11在 8X8的国际象棋盘上最多能够放置多少枚棋子，使得棋盘上每行、每列及每条斜线上 都有偶数枚棋子？【分析与解】 因为 8X8的国际象棋盘上的每行、每列都正好有偶数格，若某行（某列有空格，必空偶数格.而斜线上的格子数有奇也有偶，不妨从左上角的斜线看起：第一条斜线只有 1 格，必空；第三条有 3 格，必

17、至少空 1 格；第五、七条分别有 5、7 格，每条线上至少空 1 格.由对称性易知共有 16级数：車車I条斜线上有奇数格，且这 16 条斜线没有共用的格子，故至少必空出 16 格.其实，空出两条主对角线上的16 个格子就合题意.此时，最多可放置 48 枚棋子，放在除这两条主对角线外的其余格子中，如右图所示.XXXXXXXXXXXXXXX，:X12 .在 1000X1000 的方格表中任意选取 n 个方格染为红色，都存在 3 个红色方格，它们的中 心构成一个直角三角形的顶点.求n 的最小值.【分析与解】 首先确定 1998 不行.反例如下：其次 1999 可能是可以的，因为首先从行看，1999

18、个红点分布在 1000 行中，肯定有一些行含有 2 个或者以上的红点，因为含有0 或 1 个红点的行最多 999 个，所以其他行含有红点肯定大于等于 1999-999=1000 ,如果是大于 1000,那么根据抽屉原理，肯定有两个这样红点在一 列，那么就会出现红色三角形；如果是等于 1000 而没有这样的 2 个红点在一列，说明有999 行只含有 1 个红点，而剩下的一行全是红点，那也肯定已经出现直角三角形了，所以n 的最小值为 1999.级*1000北京市串七居円谡*杯“裁学北廉鼻蕎二翼齡“in13.若干箱货物总重 19.5 吨，每箱重量不超过 353 千克那么最少需要多少辆载重量为 吨的汽

19、车，才能保证把这些箱货物一次全部运走？【分析与解】 至少需要 16 辆车.15 辆车不一定能一次运完.例如这批货物共有 65 只箱子，64 只箱子都是 301 千克，1 只箱的重量是 236 千克，那么 总重量为 301X64+236=19500 千克，恰好符合 19.5 吨的要求由于 301X5=1505（千克.超过 1.5 吨因此，每辆汽车最多只能装4 只重量为 301 千克的箱子，15 辆汽车最多只能装4X15=60（只重量为 301 千克的箱子.这样，必然有4 只重量为 301 千克的箱子无法再装运了.16 辆汽车一定能一次运完全部箱子：首先让 12 辆汽车装到刚刚超过 1.5 吨，即若取下最后装的一只箱子就不超过1.5 吨再从这 12 辆汽车上把每辆车最后装的那只箱子卸下来，并把这 12 只箱子分别装上另外 3 辆空 车，每车 4箱，由于每车 4 箱总重量不超过 4X353=1412（千克因此也不超过 1.5 吨.这时，12+3=15 辆车就装完原来前 12 辆车上的全部货物，总重量超过 1.5X12=18（吨.而且每辆车载重不超过1.5 吨于是，剩下未装车箱子总重量不足19.5-18