35構(gòu)造與論證匯總

1、各種探討給定要求能否實現(xiàn)，設(shè)計最佳安排和選擇方案的組合問題這里的最佳通常指某個量達(dá)到最大或最小解題時，既要構(gòu)造出取得最值的具體實例，又要對此方案的最優(yōu)性進行論證論證中的常用手段包括抽屜原則、整除性分析和不等式估計1. 5 卷本百科全書按從第 1 卷到第 5 卷的遞增序號排列，今要將它們變?yōu)榉葱蚺帕?，即從?卷到第 1 卷如果每次只能調(diào)換相鄰的兩卷，那么最少要調(diào)換多少次?【分析與解】 因為必須是調(diào)換相鄰的兩卷，將第5 卷調(diào)至原來第1 卷的位置最少需4次，得到的順序為51234；現(xiàn)在將第 4卷調(diào)至此時第l 卷的位置最少需3次，得到的順序為54123；現(xiàn)在將第 3卷調(diào)至此時第l 卷的位置最少需2次，

2、得到的順序為54312；最后將第l 卷和第 2 卷對調(diào)即可所以，共需調(diào)換4+3+2+1=10 次2. 有 3 堆小石子，每次允許進行如下操作：從每堆中取走同樣數(shù)目的小石子，或是將其中的某一石子數(shù)是偶數(shù)的堆中的一半石子移入另外的一堆開始時，第一堆有1989 塊石子，第二堆有 989 塊石子，第三堆有89 塊石子問能否做到：(1 某 2 堆石子全部取光?(23 堆中的所有石子都被取走?【分析與解】(1可以，如 (1989 ， 989，89(1900 ， 900， 0(950 ， 900，950(50 ， 0， 50(25 ， 25，50(O， 0，25(2 因為操作就兩種，每堆取走同樣數(shù)目的小石子

3、，將有偶數(shù)堆石子堆中一半移至另一堆，所以每次操作石子總數(shù)要么減少3 的倍數(shù)，要么不變現(xiàn)在共有1989+989+89=3067，不是 3 的倍數(shù)，所以不能將3 堆中所有石子都取走3. 在 19971997 的正方形棋盤上的每格都裝有一盞燈和一個按鈕按鈕每按一次，與它同一行和同一列方格中的燈泡都改變一次狀態(tài)，即由亮變?yōu)椴涣?，或由不亮變?yōu)榱寥绻瓉砻勘K燈都是不亮的，請說明最少需要按多少次按鈕才可以使燈全部變亮?【分析與解】最少要 1997 次，將第一列中的每一格都按一次，則除第一列外，每格的燈都只改變一次狀態(tài)，由不亮變成亮而第一列每格的燈都改變1997 次狀態(tài)，由不亮變亮如果少于 1997 次，則至

4、少有一列和至少有一行沒有被按過，位于這一列和這一行相交處的燈保持原狀，即不亮的狀態(tài)4. 在某市舉行的一次乒乓球邀請賽上，有 3 名專業(yè)選手與 3 名業(yè)余選手參加 . 比賽采用單循環(huán)方式進行，就是說每兩名選手都要比賽一場為公平起見，用以下方法記分：開賽前每位選手各有 10 分作為底分，每賽一場，勝者加分，負(fù)者扣分，每勝專業(yè)選手一場加2 分，每勝業(yè)余選手一場加1 分；專業(yè)選手每負(fù)一場扣2 分，業(yè)余選手每負(fù)一場扣1 分問：一位業(yè)余選手最少要勝幾場，才能確保他的得分比某位專業(yè)選手高?【分析與解】當(dāng)一位業(yè)余選手勝2 場時，如果只勝了另兩位業(yè)余選手，那么他得10+2-3=9( 分此時，如果專業(yè)選手間的比賽

5、均為一勝一負(fù)，而專業(yè)選手與業(yè)余選手比賽全勝，那么每位專業(yè)選手的得分都是10+2- 2+3=13( 分所以，一位業(yè)余選手勝2 場，不能確保他的得分比某位專業(yè)選手高當(dāng)一位業(yè)余選手勝3 場時，得分最少時是勝兩位業(yè)余選手，勝一位專業(yè)選手，得10+2+2-2=12( 分此時，三位專業(yè)選手最多共得30+0+4=34( 分，其中專業(yè)選手之間的三場比賽共得0分，專業(yè)選手與業(yè)余選手的比賽最多共得4 分 . 由三個人得34 分， 343=11，推知，必有人得分不超過11 分.也就是說，一位業(yè)余選手勝3 場，能確保他的得分比某位專業(yè)選手高.n 支足球隊進行比賽，比賽采用單循環(huán)制，即每對均與其他各隊比賽一場.現(xiàn)規(guī)5定

6、勝一場得 2 分，平一場得1 分，負(fù)一場得0 分 . 如果每一隊至少勝一場，并且所有各隊的積分都不相同，問：（ 1） n=4 是否可能？（ 2） n=5 是否可能？【分析與解】（ 1）我們知道4 個隊共進行了場比賽，而每場比賽有2 分產(chǎn)生，所以4 個隊的得分總和為 2=12.所以因為每一隊至少勝一場，所以得分最低的隊至少得 4 個隊得分最少 2+3+4+5=1412，不滿足 . 即2 分，又要求每個隊的得分都不相同， n=4 不可能 .（ 2）我們知道5 個隊共進行場比賽，而每場比賽有2 分產(chǎn)生，所以4 個隊的得分總和為 2=20.因為每一隊至少勝一場，所以得分最低的隊至少得2 分，又要求每個

7、隊的得分都不相同，所以5 個隊得分最少為2+3+4+5+6=20，滿足 . 即 n=5 有可能 . 但是我們必須驗證是否存在實例 .如下所示， A得 2分， C得 3 分，D得 4分，B得 5 分，E得 6分.其中“ AB”表示 A、 B 比賽時， A 勝 B；“ B-C ”表示 B、 C比賽時， B 平 C，余下類推 .6. 如圖 35-1 ，將 1， 2， 3， 4， 5， 6， 7， 8， 9，10 這 10 個數(shù)分別填入圖中的10 個圓圈內(nèi)，使任意連續(xù)相鄰的5 個圓圈內(nèi)的各數(shù)之和均不大于某個整數(shù)M.求 M的最小值并完成你的填圖.【分析與解】要使圓圈內(nèi)的數(shù)特別小，有的特別大，那么的M最小

8、，就要盡量平均的填寫，因為如果有的連續(xù)M就只能大于等于特別大的數(shù)，不能達(dá)到盡量小的目5 個因為每個圓圈內(nèi)的數(shù)都用了5 次，所以10 次的和為5 (1+2+3+10=275每次和都小于等于朋，所以IOM 大于等于275，整數(shù)M大于28下面來驗證和是 28，一邊是也就是說數(shù)組每隔M=28時是否成立，注意到圓圈內(nèi)全部數(shù)的總和是55，所以肯定是一邊五個的27因為數(shù)字都不一樣，所以和28 肯定是相間排列，和27 也是相問排列，4 個差值為l ，這樣從1 填起，容易排出適當(dāng)?shù)奶顖D.7(1 將 1， 2， 3， 4， 5， 6，7， 8， 9 這減小不小于3 且不大于59 個數(shù)字排列在圓周上，使得任意相鄰兩

9、數(shù)的差( 大(2對于1 至11 這11 個數(shù)字，(3對于1 至12 這12 個數(shù)字，(4對于l至 14這14 個數(shù)字，滿足上述要求的排列方法是否存在?【分析與解】(1 對于 l 至 9 這九個數(shù)，注意到可與1 相鄰的數(shù)是4、 5、 6，可與 9 相鄰的數(shù)也是4、 5、 6，而 1、 9 又不可相鄰，從而4、 5、 6 這三個數(shù)只可能分別在1、 9 之間及 1和 9 的另一側(cè)以此為突破口，構(gòu)造一種合題意的填法即可例如：可以在圓周上依次填入1、 6、 2、 7、3、 8、 4、 9、 5(2 對于 1 至 11 這十一個數(shù)， 1、 2,3 、 9、 10、 11 這六個數(shù)中任意兩數(shù)不能相鄰，余下4

10、、 5、 6、 7、8 這五個數(shù)要填在前六個數(shù)的六個空隙中，顯然是不可能的(3 對于 1 至 12 這十二個數(shù)， 1、 2、 3、 10、 11、 12 這六個數(shù)中任意兩數(shù)不能相鄰，余下4、 5、 6、 7、8、 9 這六個數(shù)要填在前六個數(shù)的六個空隙中，恰好一個空隙填一個數(shù)又注意到 9 不與 1、2、 3、 10、 11 相鄰，所以9 只能一側(cè)與12 相鄰，可另一側(cè)必與11、 10、 3、 2、1 中的某一個相鄰，這是不符合要求的.(4 對于 1 至 14 這十四個數(shù)， 1,2 、 3、 12、 13、 14 這六個數(shù)中任意兩個數(shù)不能相鄰，余下 4,5 、 6、 7、 8、 9、 10、 11

11、 這八個數(shù)要填在前六個數(shù)的六個空隙中，必有兩個空隙均填了兩個數(shù)或有一個空隙中填了三個數(shù)再具體構(gòu)造一種填法即可，例如在圓周上依次放置1、 5、2、 6、 3、 7、12、 9、 13、 10、 14、11、 8、 4 即符合要求8. 1998 名運動員的號碼依次為 1 至 1998 的自然數(shù)現(xiàn)在要從中選出若干名運動員參加儀仗隊，使得剩下的運動員中沒有一個人的號碼等于另外兩人的號碼的乘積那么，選為儀仗隊的運動員最少有多少人 ?【分析與解】 我們很自然的想到把用得比較多的乘數(shù)去掉，因為它們參與的乘式比較多，把它們?nèi)サ粲兄谑故Ｏ碌臉?gòu)不成乘式，比較小的數(shù)肯定是用得最多的，因為它們的倍數(shù)最多，所以考慮先

12、把它們?nèi)サ?，但關(guān)鍵是除到何處?考慮到 44 的平方為 1936，所以去到 44 就夠了，因為如果剩下的構(gòu)成了乘式，那么乘式中最小的數(shù)一定小于等于 44，所以可以保證剩下的構(gòu)不成乘式因為對結(jié)果沒有影響，所以可以將 1 保留，于是去掉 2， 3， 4， ， 44 這 43 個數(shù)但是，是不是去掉43 個數(shù)為最小的方法呢?構(gòu)造 2 97， 3 96， 4 95， ， 44 45，發(fā)現(xiàn)這 43 組數(shù)全不相同而且結(jié)果都比1998 小，所以要去掉這些乘式就至少要去掉以 43 位最小值，即為所求.43 個數(shù)，所9. 組互不相同的自然數(shù)，其中最小的數(shù)是l ，最大的數(shù)是 25，除 1 之外，這組數(shù)中的任一個數(shù)或者

13、等于這組數(shù)中某一個數(shù)的2 倍，或者等于這組數(shù)中某兩個數(shù)之和值是多少 ?當(dāng)取到最小值時，這組數(shù)是怎樣構(gòu)成的?. 問：這組數(shù)之和的最小【分析與解】首先把這組數(shù)從小到大排列起來，那么最小的肯定為2 倍即 2，2 后面可以是3 或 4， 3 的后面可以是4， 5， 6； 4 的后面可以是251， 1 后面只能是1 的5， 6， 8最大的為下面將所有的可能情況列出：l ， 2，3， 4， ， 25 所有的和是 35；l ， 2，3， 5， ， 25 所有的和是 36；1， 2，3， 6， ， 25所有的和是37；1， 2，4， 5， ， 25所有的和是37；1， 2，4， 6， ， 25所有的和是38；

14、1， 2，4， 8， ， 25所有的和是 40.25 是奇數(shù)，只能是一個偶數(shù)加上一個奇數(shù)在中間省略的數(shù)中不能只有少還要添加兩個數(shù)，而且這兩個數(shù)的和不能小于25，否則就無法得到1 個數(shù)，所以至25 這個數(shù)要求求出最小值，先看這兩個數(shù)的和是所以從 20+5 開始25 的情況，因為省略的兩個數(shù)不同于前面的數(shù)，25=20+5=19+6=18+7=17+8=16+9=15+10=14+11=13+12這些數(shù)中 20， 19， 18， 17 太大，無法產(chǎn)生，所以看：16+9=15+10=14+11=13+12看這些誰能出現(xiàn)和最小的l ， 2， 3， 4， ， 25 中，檢驗發(fā)現(xiàn)沒有可以滿足的：再看 l ，

15、 2， 3，5， ， 25，發(fā)現(xiàn) 1， 2， 3，5， 10， 15， 25 滿足，所以： 1+2+3+5+10+15+25=36+25=6110. 在 1019 方格表的每個方格內(nèi)，寫上 0 或 1，然后算出每行及每列的各數(shù)之和問最多能得到多少個不同的和數(shù) ?【分析與解】 首先每列的和最少為 0，最多是 10，每行的和最少是 0，最多是 19，所以不同的和最多也就是 0， 1， 2， 3， 4， ， 18，19 這 20 個下面我們說明如果0 出現(xiàn)，那么必然有另外一個數(shù)字不能出現(xiàn)如果 0 出現(xiàn)在行的和中，說明有 1 行全是和至多出現(xiàn) 10 個數(shù)字，所以少了一種可能0，意味著列的和中至多出現(xiàn)0

16、 到9，加上行的如果 0 出現(xiàn)在列的和中，說明在行的和中19 不可能出現(xiàn)，所以能出現(xiàn)，所以至多是19，下面給出一種排出方法.0 出現(xiàn)就意味著另一個數(shù)字不11在 88的國際象棋盤上最多能夠放置多少枚棋子，使得棋盤上每行、每列及每條斜線上都有偶數(shù)枚棋子?【分析與解】因為 88的國際象棋盤上的每行、每列都正好有偶數(shù)格，若某行( 某列有空格，必空偶數(shù)格而斜線上的格子數(shù)有奇也有偶，不妨從左上角的斜線看起：第一條斜線只有1 格，必空；第三條有3 格，必至少空1 格；第五、七條分別有5、 7 格，每條線上至少空格由對稱性易知共有16 條斜線上有奇數(shù)格，且這16 條斜線沒有共用的格子，故至少必空出16 格其實

17、，空出兩條主對角線上的16 個格子就合題意1此時，最多可放置48 枚棋子，放在除這兩條主對角線外的其余格子中，如右圖所示12在 1000 1000 的方格表中任意選取n 個方格染為紅色，都存在心構(gòu)成一個直角三角形的頂點求n 的最小值3 個紅色方格，它們的中【分析與解】首先確定1998 不行反例如下：其次 1999 可能是可以的，因為首先從行看，1999 個紅點分布在1000 行中，肯定有一些行含有 2 個或者以上的紅點，因為含有0 或 1 個紅點的行最多999 個，所以其他行含有紅點肯定大于等于 1999-999=1000 ，如果是大于 1000，那么根據(jù)抽屜原理，肯定有兩個這樣紅點在一列，那

18、么就會出現(xiàn)紅色三角形；如果是等于1000 而沒有這樣的2 個紅點在一列，說明有999 行只含有1 個紅點，而剩下的一行全是紅點，那也肯定已經(jīng)出現(xiàn)直角三角形了，所以n 的最小值為199913 若干箱貨物總重19.5 噸，每箱重量不超過353 千克那么最少需要多少輛載重量為1.5噸的汽車，才能保證把這些箱貨物一次全部運走?【分析與解】至少需要16 輛車 15 輛車不一定能一次運完例如這批貨物共有 65 只箱子， 64 只箱子都是 301 千克， 1 只箱的重量是 236 千克，那么總重量為 30164+236=19500(千克，恰好符合 19.5 噸的要求由于3015=1505(千克超過 1.5

19、噸因此，每輛汽車最多只能裝4 只重量為301 千克的箱子， 15 輛汽車最多只能裝415=60(只重量為 301 千克的箱子這樣，必然有 4 只重量為 30l 千克的箱子無法再裝運了16 輛汽車一定能一次運完全部箱子：首先讓 12 輛汽車裝到剛剛超過1.5 噸，即若取下最后裝的一只箱子就不超過1.5 噸再從這 12 輛汽車上把每輛車最后裝的那只箱子卸下來，并把這12 只箱子分別裝上另外3 輛空車，每車4 箱，由于每車4 箱總重量不超過4353=1412(千克因此也不超過1.5 噸這時， 12+3=15 輛車就裝完原來前12 輛車上的全部貨物，總重量超過1.5 12=18(噸而且每輛車載重不超過1.5 噸于是，剩下未裝車箱子總重量不足19.5-18=1.5(噸可以把它們?nèi)垦b在第16 輛車上運走14在圖 35