第十四讲 构造与论证

1、第十四讲构造与论证构造与论证是一类创造性的思维活动要求我们积极展开联想灵活运用所学的知识。而构造法是一种重要的数学方法,一类数论问题可以通过构造出某些特殊结构,特殊形式的数列或数组来解决,另外在解决一些图形问题上,逻辑推理问题上也可以通过构造我们所熟悉的特殊情景然后在解题,问题就变得容易多 定能从中选出3支笔,使得任意2支笔在颜色和规格上各不相同?分析:显然不能.例如盒子里只有规格和颜色分别为短红、短黄、短绿、中红、长红的5支铅笔.例3、(一个立方体的12条棱分别被染成白色和红色, 每个面上至少要有一条边是白色的,那么最少有多少条边是白色的?分析:注意到有如下带有“”的三条边满足(注意三条线没

2、有任何两条在同一个平面内,并且显然有只染2条边无法满足,所以至少需要3条白色的边.例4、(国际象棋的皇后可以沿横线、竖线、斜线走,为了控制一个4×4的棋盘至少要放几个皇后?分析:显然在2×2的棋盘中,只需要一个皇后即可控制,3×3的棋盘中,只需在中心格内放入一个皇后即可控制;而4×4的棋盘中,我们只需将其分成一个3×3的棋盘,即一个“L”形如 123被123吃掉(任何数都可以被与它相同的数吃掉,但240和223互相都不能被吃掉.现请你设计6个三位数,它们当中任何一个都不能被其他5个数吃掉,并且它们的百位数字只允许取l,2;十位数字只允许取1,2

3、,3;个位数字只允许取1,2,3,4.问这6个三位数分别是多少?分析:我们注意先书写高位数字较小的数字,再往下书写,有:114,123, 132,213,222,231为所求的6个三位数.例6、(在如图所示表格第二行的每个空格内,填入一个整数,使它恰好表示它上面的那个数字在第二行中出现的次数, 那么第二行中的5个数字各是几?分析:每一空格填一个数,共有5个空格,各个数出现的次数总和应该等于5,即第二行所填的五数之和是5.如果4的下面一格所填数超过1,其他空格中至少有两个4,五个数的和就会超过5;如果4的下面填1,表示4在第二行出现一次.这时,其余数的和为0.所以,4只能填在0的下面,但第二行仅

4、剩三个空格(五个空格中已填了一个1和一个4,矛盾,所以4的下面一格只能填0.再看3的下面一格,若填大于1的数,则第二行至少有两个3,超过了5,不满足;若填1,则表示3在第二行出现一次.如果把3填在0的下面,1的下面至少填1,还剩两格,无法填上三个0;如果3填在其他数字下面,定会出现第二行五数之和大于5.所以,3的下面也只能填0.现在,第二行所剩三个空格中,只能填0,1,2三个数字,且要它们的和为5,只有一个1和两个2满足要求.所以,1在第二行出现一次,1的下面一格应填1;2在第二行出现两次,2的下面一格应填2;0在第二行中出现两次,在0的下面一格填上2.便得到结果:21200.例7、(有一张8

5、×8的方格纸,每个方格都涂上红、蓝两色之一.能个红格 次翻分析:因为共翻动了1993+1992+1991+3+2+1=1994×1993÷2=997×1993,也就是每枚硬币平均翻动997次,恰好使得原来朝上的一面变为朝下.又有1993=1+1992=2+1991=996+997.所以,第k次与第(1995-k次恰好翻动这1993枚硬币各一次,则最终每枚硬币均被翻动997次,原先朝下的一面都朝上.例9、(在象棋比赛中,胜者得1分;败者扣1分;若为平局,则双方各得0分.今有若干名学生进行比赛,每两人之间都赛一局.现知,其中有一个学生共得7分,另一个学生共得

6、20分.试说明,在比赛过程中至少有过一次平局.分析:假设总人数为n+1,如果没有平局,设得7分得那个学生胜过x个人,输给了n-x个人,所以得到x-(n-x=2x-n分,由此得2x-n=7,这说明n 为奇数.设得20分得学生胜过y个人,输给了n-y个人,所以得到y-(n-y=2y -n分,由此得2y-n=20,这说明n为偶数.两者矛盾,所以开始得假设不成立,即至少有过依次平局成立.例10、(今有长度为l,2,3,198,199的金属杆各一根,能否用上全部的金属杆,不弯曲其中的任何一根,把它们焊接成(1一个正方体框架?(2一个长方体框架?分析与解 (1 正方体不可能,因为正方体的12条棱长度相同,

7、所以所有数的和应该是12的倍数.但1+2+3+198+199=19900,不是12的倍数.(2 长方体可能,因为长方体的棱长和只要求是4的倍数即可,19900显然是4的倍数.下面给出一种构造方法:有199=1+198=2+197=3+196=4+195=99+100.这样我们将199个金属杆变成100个长度为199的杆,这样让长、宽、高分别为199×12,199×12,199即可,需(12+12+1×4=100根,正好满足.例11、(5卷本百科全书按从第1卷到第5卷的递增序号排列,今要将它们变为反序排列,即从第5卷到第l卷.如果每次只能调换相邻的两卷,那么最少要调

8、换多少次?分析:因为必须是调换相邻的两卷,将第5卷调至原来第1卷的位置最少需4次,得到的顺序为51234;现在将第4卷调至此时第1卷的位置最少需3次,得到的顺序为54123;现在将第3卷调至此时第1卷的位置最少需2次,得到的顺序为54312;最后将第1卷和第2卷对调即可.所以,共需调换4+3+2+1=10次.例12、(有3堆小石子,每次允许进行如下操作:从每堆中取走同样数目的小石子,或是将其中的某一石子数是偶数的堆中的一半石子移入另外的一堆.开始时,第一堆有1989块石子,第二堆有989块石子,第三堆有89块石子.问能否做到:(1某2堆石子全部取光?(23堆中的所有石子都被取走?分析:(1 可

9、以,如(1989,989,89(1900,900,0(950,900,950(50,0,50(25,25,50(0,0,25 .(2 因为操作就两种,每堆取走同样数目的小石子,将有偶数堆石子堆中一半移至另一堆,所以每次操作石子总数要么减少3的倍数,要么不变.现在共有1989+989+89=3067,不是3的倍数,所以不能将3堆中所有石子都取走.例13、( (15条直线最多有几个交点?(25个三角形最多能将平面分成几部分?(35个长方形最多能将平面分成几部分?分析:(12条直线最多有1个交点,第三条直线和前面的两条直线各有1个交点,共1+2=3个交点;第四条直线和前面的三条直线各有1个交点,共3

10、+3=6个交点;第五条直线和前面的四条直线各有1个交点,共6+4=10个交点。拓展到n条直线的情况:有1+2+3+4+(n-1=(12n n个交点。(21个三角形将平面分成2部分,第2个三角形的每条边都和第一个三角形有2个交点,则每条边多出2条线段,每条线段对应1个面,因此多出3×2=6个面,共2+6=8个面;第三个三角形的每条边都和前面的2个三角形有4个交点,多出4个面,因此多出3×4=12个面,共8+12=20个面;第四个三角形每边都和前面的3个三角形有6个交点,多出6个面,共多出3×6=18个面,共20+18=38个面;第五个三角形每边和前面的4个三角形有8

11、个交点,多出3×8=24个面,共38+24=62个面。拓展到n 个三角形的情况:最多有2+3×2+3×4+3×6+3×2(n -1=2+3×n(n -1个面;(3同第二问,1个长方形将平面分成2部分,第2个长方形的每条边和第1个长方形有2个交点,多出4×2个面,共2+8=10个面;拓展到n 个长方形的情况:最多有2+4×2+4×4+4×6+4×2(n -1=2+4×n(n -1个面。例14、(班主任老师外出采购前将255元班费分装在几个袋子里,只要买255元以内的东西,他都可

12、以从事先准备好的袋子里凑出所要付的钱,而不必再数钱数,你知道班主任分装在几个袋子里吗?每个袋子里放了多少元?分析:102(256(11111111 ,因此用22222222(1(10(100(1000(10000(100000(1000000(10000000、8个袋子,每个袋子装1、2、4、8、16、32、64、128元。例15、(要用天平称出1克、2克、3克40克这些不同的整数克重量,至少要用多少个砝码?这些砝码的重量分别是多少?分析:一般天平两边都可放砝码,我们从最简单的情形开始研究。(1称重1克,只能用一个1克的砝码,故1克的一个砝码是必须的。(2称重2克,有3种方案:增加一个1克的砝

13、码;用一个2克的砝码; 用一个3克的砝码,称重时,把一个1克的砝码放在称重盘内,把3克的砝码放在砝码盘内。从数学角度看,就是利用3-1=2。(3称重3克,用上面的两个方案,不用再增加砝码,因此方案淘汰。(4称重4克,用上面的方案,不用再增加砝码,因此方案也被淘汰。总之,用1克、3克两个砝码就可以称出(3+1克以内的任意整数克重。(5接着思索可以进行一次飞跃,称重5克时可以利用9-(3+1=5,即用一个9克重的砝码放在砝码盘内,1克、3克两个砝码放在称重盘内。这样,可以依次称到1+3+9=13(克以内的任意整数克重。而要称14克时,按上述规律增加一个砝码,其重为14+13=27(克,可以称到1+

14、3+9+27=40(克以内的任意整数克重。总之,砝码的重量为1,3,23,33克时,所用砝码最少,称重最大,这也是本题的答案。这个结论显然可以推广,当天平一端端都可放砝码时,使用1,2,212,2n - 克砝码可以称出1,2,3,21n -克重的重量。这是使用砝码最少、称重最大的砝码重量设计方案。当天平两端都可放砝码时,使用1,3,213,3n - 克砝码可以称出1,2,3,1312n -(克重的重量。这是使用砝码最少、称重最大的砝码重量设计方案。例16、(将九个正方形其边长分别为1、4、7、8、9、10、14、15和18拼成一个正方形,那么在这个长方形的四个直角上的四个正方形面积总和是多少?

15、分析:因1+4+7+8+9+10+14+15+18=86,拼成的大长方形的半周长<86,又九个正方形面积之和为1056=52×3×11,则只需考察1056=16×66=22×48=24×44=32×33(其它情形,如1056=1×1056=2×528=12×88均使两因数之和大于86但只有1056=32×33时,才能拼成一个长方形,如图,所以拼成的大长方形四个直角上的四个正方形面积的总和是22229141815+=826。例17、(在1997×1997的正方形棋盘上的每格都装有一

16、盏灯和一个按钮.按钮每按一次,与它同一行和同一列方格中的灯泡都改变一次状态,即由亮变为不亮,或由不亮变为亮.如果原来每盏灯都是不亮的,请说明最少需要按多少次按钮才可以使灯全部变亮?分析:最少要1997次,将第一列中的每一格都按一次,则除第一列外,每格的灯都只改变一次状态,由不亮变成亮.而第一列每格的灯都改变1997次状态,由不亮变亮.如果少于1997次,则至少有一列和至少有一行没有被按过,位于这一列和这一行相交处的灯保持原状,即不亮的状态.例18、(n 支足球队进行比赛,比赛采用单循环制,即每队均与其他各队比赛一场.现规定胜一场得2分,平一场得1分,负一场得0分.如果每一队至少胜一场,并且所有

17、各队的积分都不相同,问:(1n =4是否可能?(2n =5是否可能?分析:(1 我们知道4个队共进行了24C场比赛,而每场比赛有2分产生,所以4个队的得分总和为24C×2=12.因为每一队至少胜一场,所以得分最低的队至少得2分,有要求每个队的得分要求都不相同,所以4个队得分最少为2+3+4+5=14>12,不满足.即n=4不可能.(2 我们知道5个队共进行了25C场比赛,而每场比赛有2分产生,所以4个队的得分总和为25C×2=20.因为每一队至少胜一场,所以得分最低的队至少得2分,有要求每个队的得分要求都不相同,所以5个队得分最少为2+3+4+5+6=20,满足.即n

18、=5有可能.但是我们必须验证是否存在实例.如下所示,A得2分,C得3分,D得4分,B得5分,E得6分. C”表示B、C比赛时,B 6,7,8,9,10这10个数5个圆圈内的各数之和均不大分析:要使M最小,就要尽量平均的填写,因为如果有的连续5个圆圈内的数特别小,有的特别大,那么M就只能大于等于特别大的数,不能达到尽量小的目的.因为每个圆圈内的数都用了5次,所以10次的和为5×(1+2+3+10= 275.每次和都小于等于M,所以10M大于等于275,整数M大于28.下面来验证M=28时是否成立,注意到全部的圆圈内数总和时55,所以肯 28肯定是相个差值为1,这样从1填起,7,8,9这

19、9个数字排列在5.(3对于l至12这12 个数字,(4对于1至14这14个数字,满足上述要求的排列方法是否存在?分析:(1 对于1至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、5、6、7、8这五个数要填在前六个数的六个空隙中,显然是不可能的.(3 对于1至12这十二个数,1、2、3、10、1

20、1、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这八个数要填在前六个数的六个空隙中,必有两个空隙均填了两个数或有一个空隙中填了三个数.再具体构造一种填法即可,例如在圆周上依次放置1、5、2、6、3、7、12、9、13、10、14、11、8、4即符合要求.例21、(在

21、8×8的国际象棋盘上最多能够放置多少枚棋子,使得棋盘上每行、每列及每条斜线上都有偶数枚棋子?分析:因为8×8的国际象棋盘上的每行、每列都正好有偶数格,若某行(某列有空格,必空偶数格.而斜线上的格子数有奇也有偶,不妨从左上角的斜线看起:第一条斜线只有1格,必空;第三条有3格,必至少空1格;第五、七条分别有5、7格,每条线上至少空1格.由对称性易知共有16条斜线上有奇数格,且这16条斜线没有共用的格子,故至少必空出16格.其实,空出两条主对角线上的16个格子就合题意.此时,最多可放置48枚棋子,放在除这两条主对角线外的其余格子中,如 例22、(若干箱货物总重19.5吨,每箱重量

22、不超过353千克.那么最少需要多少辆载重量为 1.5吨的汽车,才能保证把这些箱货物一次全部运走?分析:至少需要16辆车.15辆车不一定能一次运完.例如这批货物共有65只箱子,64只箱子都是301千克,1只箱的重量时236千克,那么总重量为301×64+236=19500(千克,例23、(有9位数学家,每人至多能讲3种语言,每3个人中至少有2个人有共通的语言.求证:在这些数学家中至少有3人能用同一种语言交谈.分析:假设任意三位科学家都没有共同会的语言,这表明每种语言至多有两人会说.记这九位科学家为A、B、C、D、E、F、G、H、I.由于一位科学家最多会三种语言,而每种语言至多有两人会说

23、,所以一位科学家至多能和另外三人通话,即至少与五人语言不通.不妨设A不能与B,C,D,E,F通话.同理,B也至多能和三人通话,因此在C,D,E,F中至少有一人与B语言不通,设为C.则A、B、C三人中任意两人都没有共同语言,与题意矛盾.这表明假设不成立.例24、(在平面上有7个点,其中任意3个点都不在同一条直线上.如果在这7个点之间连结18条线段,那么这些线段最多能构成多少个三角形?分析:平面上这7个点,任意3点都不在同一条直线上,若任意2点连结,共可连结出76212=条线段.现在只连结18条线段,有3条没有连出,要使得这18条线段所构成的三角形最多,需使得没连出的这3条线段共同参与的三角形总数

24、最多,故这3条线段共点.对于这3条线段中的任何一条,还与其他5个点本应构成5个三角形,故这3条线段没连出,至少少构成5×3-3=12个三角形.而平面内任何三点不共线的7个点,若任何2点连线,共可构成37C=35个三角形.故现在最多可构成三角形35-12=23个.课后作业1、能否在5×5方格表的各个小方格内分别填入数1,2,24,25,使得从每行中都可以选择若干个数,这些数的和等于该行中其余各数之和?2、把图10-2中的圆圈任意涂上红色或蓝色.问:能否使得在同一条直线上的红圈数都是奇数? 3、在99枚外观相同的硬币中,要找出其中的某些伪币.已知每枚伪币与真币的重量均相差奇数克

25、,而所给硬币的总重量恰等于99枚真币的重量.今有能标明两盘重量之差的天平,证明:只要称一次即可辨别出预先选择的一枚硬币是否为伪币. 5、但现在的表格中9个数的和为100,100除以3的余数为1,而操作后9个数都相同即为9的倍数,除以3的余数为0.显然不满足操作前后9个数的和除以3的余数不变.6、用110十个数字随意拍成一排,如果相邻的两个数中前面的大于后面的就将其颠倒位置,如此操作直到前面的数都小于后的数位为止,已知10位于这列数中的第6位,最少要实行多少次交换,最多要实行多少次交换?7、有三堆棋子的个数分别为19,8,9,现在进行如下操作,每次从任意的两堆中各取出1个放入第三堆中,试问能否经

26、过若干次操作后,使得:三堆石子的数分别是22,2,12?能否三堆都是12?如果能请用最快的操作完成,如果不能,说明理由;8、在11×11的棋盘上每个方格内都有一个数字0,现在变换一次都会使与这个数的同行和同列的数字由0变为1,由1变为0,试问最少经过多少次操作才能使这个11×11的棋盘上的全部有0变为1?9、ABCDE五支足球队进行循环比赛,每两队都要赛一场,规定每场比赛的胜者得2分,负者得0分,平者各得1分,已知各队的总比分各不相同,并且: (1获得冠军的没有平过一场;(2获得亚军的没有负过一场;(3获得第四名的没有胜过一场,试确定所有的各场比赛的结果,并填入表中。 10

27、、把112排在下图中12个圆圈中,然后将任意的相邻的两个数相加,得到一些和,要使这些和都不超过N,N至少是多少?为什么?请你设计一种排法满足你的结论; 11、把数1,2,3,4,1993置于圆周上,请你设计一种方法使其相邻的两数之间的差不超过2? 12、把在6×6的棋盘上的若干格涂上红色,其他格不涂色,棋盘上的每个3×3的正方形的四个角上的4个方格中都恰好有一个红格,那么整个方格纸上最多要涂上多少个红格? 13、采石场采出200块花冈石料,其中有120块各重7吨,其余每块各重9吨,每节火车皮至多能载重40吨,为了能一次运出这些石料至少要用多少节车皮?14、4个人聚会,每人各带了2件礼品,分赠给其余3个人中的2人.试证明:至少有2对人,每对人是互赠过礼品的.15、平面上有10个点,其中任意三点都不在一条直线上,如果在这10个点之间连上42条线段,那么这些线段至少能构成多少个三角形?16、给你一架天平和两个砝码,这两个砝码分别重50克和100克,如果再添上3个砝码,则这5个砝码能称出的重量种类最多是种?(天平的左右两盘均可放砝码17、有10个整数克的砝码(允许砝码重量相同,将其中一个或几个放在天平的右边,待称的物品放在天平的左边,能称出1,2,3,200的所有整数克的物品来;那么,这10个砝码中第二重的砝码最少是克。分析:首先