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

《奥数：第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