奥数:第19讲 组合问题第04讲

奥数:第19讲 组合问题第04讲

ID:28767583

大小:138.00 KB

页数:5页

时间:2018-12-14

奥数:第19讲  组合问题第04讲_第1页
奥数:第19讲  组合问题第04讲_第2页
奥数:第19讲  组合问题第04讲_第3页
奥数:第19讲  组合问题第04讲_第4页
奥数:第19讲  组合问题第04讲_第5页
资源描述:

《奥数:第19讲 组合问题第04讲》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第19讲组合问题第04讲构造与论证之二例15卷本百科全书按从第1卷到第5卷的递增序号排列,今要将它们变为反序排列,即从第5卷到第1卷.如果每次只能调换相邻的两卷,那么最少要调换多少次?答案10次.分析注意到由原排列要变为反序排列,每一卷书都至少要与其余各卷书调换一次,即至少要调换=10次;再具体构造一种调换方案,恰好只需调换10次.详解考虑这5卷书的序号排列,原排列为1、2、3、4、5.现要将其调换为反序排列,即变为5、4、3、2、1.对于原排列中的每一个数,比如2、1至少要与2调换一次才能达成反序排列的状态,3、4、5这

2、三个数分别也都要与2至少调换一次才能达成反序排列的状态.从而每两个数都至少要调换一次,共至少需调换=10次.而且调换10次是可以将其变为反序排列的.例如,第一步把1调至最后成2、3、4、5、1,需调换4次;第二步再把2调至5、1间成3、4、5、3、2、1,需3次;第三步再把3调至5、2间成4、5、3、2、1,需2次;最后一步把4调至5、3间成5、4、3、2、1,需1次.共需调换4+3+2+1=10次.评注解决这类最少、最多次等问题,可从整体上估算出解决方案所需的最少、最多次数,再具体构造出一种符合题意的解题方案.例2在19

3、97×1997的正方形棋盘上的每格都装有盏灯和一个按钮,按钮每按一次,与它同一行和同一列的方格中灯泡都改变一次状态,即由亮变为不亮,由不亮变为亮.如果原来每盏灯都是不亮的,请说明最少需要按多少次按钮?再具体构造一种操作即可.答案1997次.分析注意到1997×1997的正方形棋盘的一条对角线上有1997个灯泡,它们每两个既不同行也不同列,要使这1997个灯泡全都改变状态,至少需按1997次按钮.再具体构造一种操作即可.详解因为每按一次按钮,只改变与它同一行或同一列方格中灯泡的状态,而不改变与它不同行且不同列的方格中灯泡的状

4、态·现在1997×1997的正方形棋盘中,一条对角线有既不同行且不同列的1997个灯泡,要使这1997个灯泡全都改变状态,至少需按1997次按钮.现在构造一种按1997次按钮的方法,使得原来都不亮的灯泡全部变亮.比如,可以将第一列的每个按钮按一次,则第一列方格中的灯泡全部改变1997次状态,由不亮变为亮;而其余方格中的灯泡都恰好改变1次状态,也由不亮变为亮.评注此解法中,通过考虑“同行或同列,,的反面情形.即“既不同行也不同列”的灯泡数为1997个,.从而得到至少1977次按钮.这种换个角度来思考问题的方法也是我们论让最大

5、或最小值问题的一种常用方法.例3n支足球队进行比赛,比赛采用单循环制,即每队均与其他各队比赛一场.现规定胜一场得2分,平一场得1分,负一场得0分.如果每一队至少胜一场,并且所有各队的积分都不相同,问:①n=4是否可能?②n=5是否可能?答案①不可能;②可能.分析注意比赛总场数N与球队数n之间的关系为N=,且每赛一场两队总得分为2分,从而比赛结束后各队得分之和应为n(n一1)分.故可以从最后各队得分之和入手来考虑.详解①4支球队比赛总场数为=6场,每赛一次两队总得分为2分,所以最后4队总得分为6×2=12分.若每一队至少胜一

6、场,则得分至少为2分;又所有各队的积分都不相同,所以这4支球队最后总得分至少为2+3+4+5=14分,比这4队实际的最后总得分12分还多,显然这是不可能的.②5支球队的比赛总场数为=10场,每赛一场两队总得分为2分,所以最后5队总得分为10X2=20分.若每一队至少胜一场,且所有各队的积分都不相同,则最后5队总得分至少为2+3+4+5+6=20分.恰好等干最后5队的实际总得分.又可以构造出一种比赛结果,使得各队得分恰好分别为2分、3分、4分、5分和6分.例如,1队胜5队.其余均败;2队胜1队平4队,其余均败;3队胜1、2队

7、,其余均败;4队胜1、3队平2队,败给5队,则这种比赛结果恰好符合要求.用·一·表示一胜一负,用.一·表示平一场,则上述结果可简单地用图19—1加以表示.例4①将1、2、3、4、5、6、7、8、9这九个数字排列在圆周上,使得任意相邻两数的差(大减小)不小于3且不大于箩.②对于1至11这十一个数字,③对于1至12这十二个数字,④对于1至14这十四个数字,满足上述要求的排列方法是否存在?答案①一种可能的排列方法是在圆周上依次放置1、672、7、3、8、4、9、5.②不存在.③不存在.④存在.例如在圆周上依次放置1,5、2、6、

8、3、7、12、9、13、10、14、11、8、4.分析圆周上的数字排列问题,一般可从特殊数入手,如最大的数或最小的数,找到可能与之相邻的数,逐步构造出一种填法;或者考虑其中两两互不相邻的几个数,考虑它们的空隙可能的填法.详解①对于1至9这九个数,注意到可与1相邻的数是4、5、6,可与9相邻的数也是4、5

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。