奧數(shù)：第9講組合問題第4講

《奧數(shù)：第9講組合問題第4講》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第19講組合問題第04講構(gòu)造與論證之二例15卷本百科全書按從第1卷到第5卷的遞增序號排列，今要將它們變?yōu)榉葱蚺帕?，即從?卷到第1卷．如果每次只能調(diào)換相鄰的兩卷，那么最少要調(diào)換多少次?答案10次．分析注意到由原排列要變?yōu)榉葱蚺帕校恳痪頃贾辽僖c其余各卷書調(diào)換一次，即至少要調(diào)換=10次；再具體構(gòu)造一種調(diào)換方案，恰好只需調(diào)換10次．詳解考慮這5卷書的序號排列，原排列為1、2、3、4、5．現(xiàn)要將其調(diào)換為反序排列，即變?yōu)?、4、3、2、1．對于原排列中的每一個(gè)數(shù)，比如2、1至少要與2調(diào)換一次才能達(dá)成反序排列的狀態(tài)，3、4、

2、5這三個(gè)數(shù)分別也都要與2至少調(diào)換一次才能達(dá)成反序排列的狀態(tài)．從而每兩個(gè)數(shù)都至少要調(diào)換一次，共至少需調(diào)換=10次．而且調(diào)換10次是可以將其變?yōu)榉葱蚺帕械模纾谝徊桨?調(diào)至最后成2、3、4、5、1，需調(diào)換4次；第二步再把2調(diào)至5、1間成3、4、5、3、2、1，需3次；第三步再把3調(diào)至5、2間成4、5、3、2、1，需2次；最后一步把4調(diào)至5、3間成5、4、3、2、1，需1次．共需調(diào)換4+3+2+1=10次．評注解決這類最少、最多次等問題，可從整體上估算出解決方案所需的最少、最多次數(shù)，再具體構(gòu)造出一種符合題意的解題方案．例

3、2在1997×1997的正方形棋盤上的每格都裝有盞燈和一個(gè)按鈕，按鈕每按一次，與它同一行和同一列的方格中燈泡都改變一次狀態(tài)，即由亮變?yōu)椴涣?，由不亮變?yōu)榱粒绻瓉砻勘K燈都是不亮的，請說明最少需要按多少次按鈕?再具體構(gòu)造一種操作即可.答案1997次．分析注意到1997×1997的正方形棋盤的一條對角線上有1997個(gè)燈泡，它們每兩個(gè)既不同行也不同列，要使這1997個(gè)燈泡全都改變狀態(tài)，至少需按1997次按鈕．再具體構(gòu)造一種操作即可．詳解因?yàn)槊堪匆淮伟粹o，只改變與它同一行或同一列方格中燈泡的狀態(tài)，而不改變與它不同行且不同列的方

4、格中燈泡的狀態(tài)·現(xiàn)在1997×1997的正方形棋盤中，一條對角線有既不同行且不同列的1997個(gè)燈泡，要使這1997個(gè)燈泡全都改變狀態(tài)，至少需按1997次按鈕．現(xiàn)在構(gòu)造一種按1997次按鈕的方法，使得原來都不亮的燈泡全部變亮．比如，可以將第一列的每個(gè)按鈕按一次，則第一列方格中的燈泡全部改變1997次狀態(tài)，由不亮變?yōu)榱?；而其余方格中的燈泡都恰好改?次狀態(tài)，也由不亮變?yōu)榱粒u注此解法中，通過考慮“同行或同列，，的反面情形．即“既不同行也不同列”的燈泡數(shù)為1997個(gè)，．從而得到至少1977次按鈕.這種換個(gè)角度來思考問題的方法

5、也是我們論讓最大或最小值問題的一種常用方法．例3n支足球隊(duì)進(jìn)行比賽，比賽采用單循環(huán)制，即每隊(duì)均與其他各隊(duì)比賽一場．現(xiàn)規(guī)定勝一場得2分，平一場得1分，負(fù)一場得0分．如果每一隊(duì)至少勝一場，并且所有各隊(duì)的積分都不相同，問：①n=4是否可能?②n=5是否可能?答案①不可能；②可能．分析注意比賽總場數(shù)N與球隊(duì)數(shù)n之間的關(guān)系為N=，且每賽一場兩隊(duì)總得分為2分，從而比賽結(jié)束后各隊(duì)得分之和應(yīng)為n(n一1)分．故可以從最后各隊(duì)得分之和入手來考慮．詳解①4支球隊(duì)比賽總場數(shù)為=6場，每賽一次兩隊(duì)總得分為2分，所以最后4隊(duì)總得分為6×2=12

6、分．若每一隊(duì)至少勝一場，則得分至少為2分；又所有各隊(duì)的積分都不相同，所以這4支球隊(duì)最后總得分至少為2+3+4+5=14分，比這4隊(duì)實(shí)際的最后總得分12分還多，顯然這是不可能的．②5支球隊(duì)的比賽總場數(shù)為=10場，每賽一場兩隊(duì)總得分為2分，所以最后5隊(duì)總得分為10X2=20分．若每一隊(duì)至少勝一場，且所有各隊(duì)的積分都不相同，則最后5隊(duì)總得分至少為2+3+4+5+6=20分．恰好等干最后5隊(duì)的實(shí)際總得分．又可以構(gòu)造出一種比賽結(jié)果，使得各隊(duì)得分恰好分別為2分、3分、4分、5分和6分．例如，1隊(duì)勝5隊(duì)．其余均?。?隊(duì)勝1隊(duì)平4隊(duì)，

7、其余均??；3隊(duì)勝1、2隊(duì)，其余均??；4隊(duì)勝1、3隊(duì)平2隊(duì)，敗給5隊(duì)，則這種比賽結(jié)果恰好符合要求．用·一·表示一勝一負(fù)，用．一·表示平一場，則上述結(jié)果可簡單地用圖19—1加以表示．例4①將1、2、3、4、5、6、7、8、9這九個(gè)數(shù)字排列在圓周上，使得任意相鄰兩數(shù)的差(大減小)不小于3且不大于籮．②對于1至11這十一個(gè)數(shù)字，③對于1至12這十二個(gè)數(shù)字，④對于1至14這十四個(gè)數(shù)字，滿足上述要求的排列方法是否存在?答案①一種可能的排列方法是在圓周上依次放置1、672、7、3、8、4、9、5．②不存在．③不存在．④存在．例如在圓

8、周上依次放置1，5、2、6、3、7、12、9、13、10、14、11、8、4．分析圓周上的數(shù)字排列問題，一般可從特殊數(shù)入手，如最大的數(shù)或最小的數(shù)，找到可能與之相鄰的數(shù)，逐步構(gòu)造出一種填法；或者考慮其中兩兩互不相鄰的幾個(gè)數(shù)，考慮它們的空隙可能的填法．詳解①對于1至9這九個(gè)數(shù)，注意到可與1相鄰的數(shù)是4、5、6，可與9相鄰的數(shù)也是4、5