35构造与论证一汇总

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

2、;现在将第3卷调至此时第I卷的位置最少需2次,得到的顺序为54312；最后将第I卷和第2卷对调即可.所以，共需调换 4+3+2+1=10 次.阳胆年第十A居全俄數芋皇匹立九年级第1理或是将其中的某1989块石子，第二堆2.有3堆小石子，每次允许进行如下操作：从每堆中取走同样数目的小石子, 一石子数是偶数的堆中的一半石子移入另外的一堆开始时，第一堆有 有989块石子，第三堆有 89块石子.问能否做到： (1某2堆石子全部取光？ (23堆中的所有石子都被取走【分析与解】(1 可以，如(1989 , 989, 89 T (1900 , 900,(950 , 900, 950-* (50 , 0, 5

3、0 (25 , 25, 50(0, 0, 25.（2因为操作就两种，每堆取走同样数目的小石子，将有偶数堆石子堆中一半移至另一堆，所 以每次操作石子总数要么减少3的倍数，要么不变.现在共有1989+989+89=3067,不是3的倍数，所以不能将3堆中所有石子都取走. «主昼主*金杯”少牛釁？电请專埜决住兰弟¥3.在1997X 1997的正方形棋盘上的每格都装有一盏灯和一个按钮.按钮每按一次，与它同一 行和同一列方格中的灯泡都改变一次状态，即由亮变为不亮，或由不亮变为亮.如果原来每盏 灯都是不亮的，请说明最少需要按多少次按钮才可以使灯全部变亮？【分析与解】 最少要1997次，

4、将第一列中的每一格都按一次，则除第一列外，每格的 灯都只改变一次状态，由不亮变成亮而第一列每格的灯都改变1997次状态，由不亮变亮.如果少于1997次，则至少有一列和至少有一行没有被按过，位于这一列和这一行相交处 的灯保持原状，即不亮的状态.»六崩”隼菱纽如炷鼠直豪® X鼻第10雜4.在某市举行的一次乒乓球邀请赛上，有方式进行，就是说每两名选手都要比赛一场.为公平起见，用以下方法记分：开赛前每位选手 各有10分作为底分，每赛一场，胜者加分，负者扣分，每胜专业选手一场加 选手一场加1分；专业选手每负一场扣 2分，业余选手每负一场扣 1分.少要胜几场，才能确保他的得分比某位专业

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

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

7、 12,不满足.即n=4不可能.(2)我们知道5个队共进行 J场比赛，而每场比赛有2分产生，所以4个队的得分总和为 5 X 2=20.因为每一队至少胜一场, 同，所以5个队得分最少为 实例.所以得分最低的队至少得2分，又要求每个队的得分都不相如下所示，A得2分,C得3分，D得4分，B得5分，E得6分.2+3+4+5+6=20,满足.即n=5有可能.但是我们必须验证是否存在其中“ AT B”表示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个圆圈内,

8、 使任意连续相邻的5个圆圈内的各数之和均不大于某个整数M.求M的最小值并完成你的填图M最小，就要尽量平均的填写，因为如果有的连续M就只能大于等于特别大的数，不能达到尽量小的目【分析与解】要使 圆圈内的数特别小，有的特别大，那么 的.因为每个圆圈内的数都用了5次，所以10 次的和为 5 X (1+2+3+10=275.每次和都小于等于朋，所以IOM大于等于275，整数M大于28.下面来验证 M=28时是否成立，注意到圆圈内全部数的总和是55，所以肯定是一边五个的和是28, 一边是27.因为数字都不一样，所以和 28肯定是相间排列，和 27也是相问排列， 也就是说数组每隔 4个差值为I，这样从1填

9、起，容易排出适当的填图.WSSxXzZ7. (1将1, 2, 3, 4, 5, 6, 7, 8, 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

10、这十一个数，1、2,3、9、10、11这六个数中任意两数不能相邻，余下4、5、6、7、8这五个数要填在前六个数的六个空隙中，显然是不可能的.(3对于1至12这十二个数，1、2、3、10、11、12这六个数中任意两数不能相邻，余下4、11、 10、 3、 2、5、6、7、& 9这六个数要填在前六个数的六个空隙中，恰好一个空隙填一个数又注意 到9不与1、2、3、10、11相邻，所以9只能一侧与12相邻，可另一侧必与 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的自然数现在要从中选出若干名运动员参加仪仗队，使得剩下的运动员中没有一个人的号码等于另外两人的号码的乘积.那么，选为仪仗队 的运动员最少有多少人 ？【分析与解】 我们很自然的想到把用得比较多的乘数去掉，因为它们参与的乘式比较 多，把它们去掉有助于使剩下的构不成乘式，比较小的数肯定是用得最多的，因为它们的倍 数最多，所以考虑先把它们去

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

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

14、在中间省略的数中不能只有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+10=14+11=13+12.看这些谁能出现和最小的I , 2, 3, 4,，25中，检验发现没有可以满足的:再看 I , 2, 3, 5，25,发现 1, 2, 3, 5, 10, 15, 25 满足，所以：1+2+

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

16、个数字不 19,下面给出一种排出方法.0fl-00(J0Ci00000000a00000000000000na000000II11在8X8的国际象棋盘上最多能够放置多少枚棋子，使得棋盘上每行、每列及每条斜线上 都有偶数枚棋子？【分析与解】因为8X8的国际象棋盘上的每行、每列都正好有偶数格，若某行（某列有空格，必空偶数格.而斜线上的格子数有奇也有偶，不妨从左上角的斜线看起：第一条斜线只有 1格，必空；第三条有 3格，必至少空1格；第五、七条分别有 5、7格，每条线上至少空 1 格.由对称性易知共有 16条斜线上有奇数格，且这 16条斜线没有共用的格子，故至少必空出 16格其实，空出两条主对角线上

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

18、点在一 列，那么就会出现红色三角形；如果是等于1000而没有这样的2个红点在一列，说明有999行只含有1个红点，而剩下的一行全是红点，那也肯定已经出现直角三角形了，所以n的最小值为1999.比窜市亂七雷Ft杠"tt节克武港乘就二腔陥an斟13.若干箱货物总重19.5吨，每箱重量不超过353千克那么最少需要多少辆载重量为1.5吨的汽车，才能保证把这些箱货物一次全部运走？【分析与解】至少需要16辆车.15辆车不一定能一次运完.例如这批货物共有 65只箱子，64只箱子都是301千克，1只箱的重量是236千克，那么 总重量为 301 X 64+236=19500（千克，恰好符合19.5吨的要

19、求.由于 301 X 5=1505（千克.超过1.5吨因此，每辆汽车最多只能装4只重量为301千克的箱子，15辆汽车最多只能装4X 15=60（只重量为301千克的箱子这样，必然有4只重量为301千克的箱子无法再装运了.16辆汽车一定能一次运完全部箱子:首先让12辆汽车装到刚刚超过 1.5吨，即若取下最后装的一只箱子就不超过1.5吨再从这12辆汽车上把每辆车最后装的那只箱子卸下来，并把这12只箱子分别装上另外 3辆空车，每车4箱，由于每车4箱总重量不超过 4X 353=1412（千克因此也不超过1.5吨这时,1.5 X 12=18（吨.而且每辆车载重不超过12+3=15辆车就装完原来前12辆车上的全部货物，总重量超过1.5吨.于是，剩下未装车箱子总重量不足19.5-18=1.5（吨可以把它们全部装在第16辆车上运走.14.在图35-2中有16个黑点，它们排成了一个4X4的方阵.用线段连接其中 4点，就可以画出各种不同的正方形现在要去掉某些点，使得其中任意4点都不能连成正方形，那么最少要去掉多少个