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

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

2、少需 3 次，得到的順序為 54123;現(xiàn)在將第 3 卷調(diào)至此時第 I 卷的位置最少需 2 次，得到的順序為 54312;最后將第 I 卷和第 2 卷對調(diào)即可.所以，共需調(diào)換 4+3+2+仁 10 次.酸級數(shù)：車車車拿 E19曲牟罷十五屆全俄盤學(xué)龕舐匹丸丸年緘第1魏2.有 3 堆小石子，每次允許進(jìn)行如下操作：從每堆中取走同樣數(shù)目的小石子，或是將其中的某一石子數(shù)是偶數(shù)的堆中的一半石子移入另外的一堆開始時，第一堆有1989 塊石子，第二堆有989塊石子， 第三堆有 89塊石子.問能否做到： (1某2堆石子全部取光？(23堆中的所有石子都被取走？【分析與解】(1 可以，如(1989 , 989, 8

3、9(1900 , 900,0 -(950 , 900, 950 - (50 ,0, 50P(25 ,25, 50 (O,0, 25（2 因為操作就兩種，每堆取走同樣數(shù)目的小石子，將有偶數(shù)堆石子堆中一半移至另一堆，所 以每次操作石子總數(shù)要么減少3 的倍數(shù)，要么不變.現(xiàn)在共有 1989+989+89=3067,不是 3 的倍數(shù)，所以不能將 3 堆中所有石子都取走.矽蛾跌拿拿雀一3.在 1997X1997 的正方形棋盤上的每格都裝有一盞燈和一個按鈕.按鈕每按一次，與它同一 行和同一列方格中的燈泡都改變一次狀態(tài)，即由亮變?yōu)椴涣?，或由不亮變?yōu)榱寥绻瓉砻勘K 燈都是不亮的，請說明最少需要按多少次按鈕才可以

4、使燈全部變亮？【分析與解】 最少要 1997 次，將第一列中的每一格都按一次，則除第一列外，每格的燈都只改變一次狀態(tài)，由不亮變成亮而第一列每格的燈都改變1997 次狀態(tài)，由不亮變亮.如果少于 1997 次，則至少有一列和至少有一行沒有被按過，位于這一列和這一行相交處 的燈保持原狀，即不亮的狀態(tài).4.在某市舉行的一次乒乓球邀請賽上，有3 名專業(yè)選手與 3名業(yè)余選手參加.比賽采用單循環(huán)方式進(jìn)行，就是說每兩名選手都要比賽一場.為公平起見，用以下方法記分：開賽前每位選手各有 10 分作為底分，每賽一場，勝者加分，負(fù)者扣分，每勝專業(yè)選手一場加2 分，每勝業(yè)余選手一場加 1 分；專業(yè)選手每負(fù)一場扣 2 分

5、，業(yè)余選手每負(fù)一場扣 1 分問：一位業(yè)余選手最 少要勝幾場，才能確保他的得分比某位專業(yè)選手高？【分析與解】 當(dāng)一位業(yè)余選手勝 2 場時，如果只勝了另兩位業(yè)余選手，那么他得10+2-3=9（分此時，如果專業(yè)選手間的比賽均為一勝一負(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è)選手之間的三場比賽共得0I分，專業(yè)選手與業(yè)余選手的比賽最多共得4

6、 分.由三個人得 34 分，34 十 3=11，推知，必有人得分不超過 11 分.也就是說，一位業(yè)余選手勝3 場，能確保他的得分比某位專業(yè)選手高.5.n 支足球隊進(jìn)行比賽，比賽采用單循環(huán)制，即每對均與其他各隊比賽一場.現(xiàn)規(guī)定勝一場得 2 分，平一場得 1 分，負(fù)一場得0分.如果每一隊至少勝一場，并且所 有各隊的積分都不相同，問：(1) n=4 是否可能？(2) n=5 是否可能？【分析與解】(1)我們知道 4 個隊共進(jìn)行了場比賽，而每場比賽有2 分產(chǎn)生，所以4 個隊的得分總和為X2=12.因為每一隊至少勝一場，所以得分最低的隊至少得2 分，又要求每個隊的得分都不相同，所以 4 個隊得分最少 2

7、+3+4+5=14 12,不滿足.即 n=4 不可能.(2)我們知道 5 個隊共進(jìn)行場比賽，而每場比賽有 2 分產(chǎn)生，所以 4 個隊的得分總和為X2=20.因為每一隊至少勝一場，所以得分最低的隊至少得2 分，又要求每個隊的得分都不相同，所以 5 個隊得分最少為 2+3+4+5+6=20,滿足.即 n=5 有可能.但是我們必須驗證是否存在 實例.如下所示，A 得 2 分，C 得 3 分，D 得 4 分，B 得 5 分，E 得 6 分.其中“ B”表示AB 比賽時，A 勝 B;“ B-C ”表示 B、C 比賽時，B 平 C,余下類推c -c6.如圖 35-1，將 1 , 2, 3, 4, 5, 6

8、, 7,8, 9, 10 這 10 個數(shù)分別填入圖中的 10 個圓圈內(nèi), 使任意連續(xù)相鄰的 5 個圓圈內(nèi)的各數(shù)之和均不大于某個整數(shù)M.求 M 的最小值并完成你的填圖分析與解】要使 圓圈內(nèi)的數(shù)特別小，有的特別大，那么 的.下面來驗證 M=28 時是否成立，注意到圓圈內(nèi)全部數(shù)的總和是55，所以肯定是一邊五個的和是 28, 一邊是 27.因為數(shù)字都不一樣，所以和 28 肯定是相間排列，和 27 也是相問排列， 也就是說數(shù)組每隔 4 個差值為 I，這樣從 1 填起，容易排出適當(dāng)?shù)奶顖D7.(1 將 1, 2, 3, 4, 5, 6, 7, 8, 9 這 9 個數(shù)字排列在圓周上，使得任意相鄰兩數(shù)的差(大減

9、小不小于 3 且不大于 5.(2 對于 1 至 11 這 11 個數(shù)字，(3 對于 1 至 12 這 12 個數(shù)字，(4 對于 I 至 14 這 14 個數(shù)字，滿足上述要求的排列方法是否存在？【分析與解】(1 對于 I 至 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ù)不能相鄰

10、，余下4、5、6、7、8 這五個數(shù)要填在前六個數(shù)的六個空隙中，顯然是不可能的.(3 對于 1 至 12 這十二個數(shù)，1、2、3、10、11、12 這六個數(shù)中任意兩數(shù)不能相鄰，余下4、5、6、7、& 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、& 9、10、11 這八個數(shù)要填在前六個數(shù)的

11、六個空隙中，必有兩個空隙均填了兩 個數(shù)或有一個空隙中填了三個數(shù).再具體構(gòu)造一種填法即可，例如在圓周上依次放置1、5、2、6、3、7、12、9、13、10、14、11、8、4 即符合要求.級數(shù)：車車車車8. 1998 名運動員的號碼依次為 1 至 1998 的自然數(shù).現(xiàn)在要從中選出若干名運動員參加儀仗 隊，使得剩下的運動員中沒有一個人的號碼等于另外兩人的號碼的乘積那么，選為儀仗隊M 最小，就要盡量因為每個圓圈內(nèi)的數(shù)都用了5 次，所以10 次的和為 5X(1+2+3+10=275.每次和都小于等于朋，所以IOM 大于等于的運動員最少有多少人？【分析與解】 我們很自然的想到把用得比較多的乘數(shù)去掉，因

12、為它們參與的乘式比較多，把它們?nèi)サ粲兄谑故Ｏ碌臉?gòu)不成乘式，比較小的數(shù)肯定是用得最多的，因為它們的倍 數(shù)最多，所以考慮先把它們?nèi)サ?，但關(guān)鍵是除到何處？考慮到 44 的平方為 1936，所以去到 44 就夠了，因為如果剩下的構(gòu)成了乘式，那么乘式 中最小的數(shù)一定小于等于44,所以可以保證剩下的構(gòu)不成乘式因為對結(jié)果沒有影響，所以可以將 1 保留，于這 43 個數(shù).但是，是不是去掉 43 個數(shù)為最小的方法呢？構(gòu)造 2X97, 3X96, 4X95,，44X45,發(fā) 現(xiàn)這 43組數(shù)全不相同而且結(jié)果都比1998 小,所以要去掉這些乘式就至少要去掉43 個數(shù)，所以 43 位最小值，即為所求觀愆級數(shù)：車拿車車

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

14、，25 所有的和是 37;1, 2, 4, 5,，25 所有的和是 37;1, 2, 4, 6,，25 所有的和是 38;1, 2, 4, 8,，25 所有的和是 40.25 是奇數(shù)，只能是一個偶數(shù)加上一個奇數(shù)在中間省略的數(shù)中不能只有1 個數(shù)，所以至少還要添加兩個數(shù)，而且這兩個數(shù)的和不能小于25，否則就無法得到 25 這個數(shù).要求求出最小值，先看這兩個數(shù)的和是25 的情況，因為省略的兩個數(shù)不同于前面的數(shù)，所以從 20+5 開始.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、15+10=14+1 仁 13+12.看這些誰能出現(xiàn)和最小的 I , 2, 3, 4,，25 中，檢驗發(fā)現(xiàn)沒有可以滿足的:再看 I , 2, 3, 5，25,發(fā)現(xiàn) 1, 2, 3, 5, 10, 15, 25 滿足，所以：1+2+3+5+10+15+25=36+25=6110.在 10X19 方格表的每個方格內(nèi)，寫上0 或 1,然后算出每行及每列的各數(shù)之和問最多能得到多少個不同的和數(shù)？【分析與解】 首先每列的和最少為 0,最多是 10,每行的和最少是 0,最多是 19,所以 不同的和最多也就是 0, 1, 2, 3, 4,，18, 19 這 20 個.下面我們說明如果 0 出現(xiàn)，那么必然有另外

16、一個數(shù)字不能出現(xiàn).如果 0 出現(xiàn)在行的和中，說明有 1 行全是 0,意味著列的和中至多出現(xiàn) 0 到 9，加上行的 和至多出現(xiàn) 10 個數(shù)字，所以少了一種可能.如果 0 出現(xiàn)在列的和中，說明在行的和中19 不可能出現(xiàn)，所以 0 出現(xiàn)就意味著另一個數(shù)字不能出現(xiàn)，所以至多是 19,下面給出一種排出方法11在 8X8的國際象棋盤上最多能夠放置多少枚棋子，使得棋盤上每行、每列及每條斜線上 都有偶數(shù)枚棋子？【分析與解】 因為 8X8的國際象棋盤上的每行、每列都正好有偶數(shù)格，若某行（某列有空格，必空偶數(shù)格.而斜線上的格子數(shù)有奇也有偶，不妨從左上角的斜線看起：第一條斜線只有 1 格，必空；第三條有 3 格，必

17、至少空 1 格；第五、七條分別有 5、7 格，每條線上至少空 1 格.由對稱性易知共有 16級數(shù)：車車I條斜線上有奇數(shù)格，且這 16 條斜線沒有共用的格子，故至少必空出 16 格.其實，空出兩條主對角線上的16 個格子就合題意.此時，最多可放置 48 枚棋子，放在除這兩條主對角線外的其余格子中，如右圖所示.XXXXXXXXXXXXXXX，:X12 .在 1000X1000 的方格表中任意選取 n 個方格染為紅色，都存在 3 個紅色方格，它們的中 心構(gòu)成一個直角三角形的頂點.求n 的最小值.【分析與解】 首先確定 1998 不行.反例如下：其次 1999 可能是可以的，因為首先從行看，1999

18、個紅點分布在 1000 行中，肯定有一些行含有 2 個或者以上的紅點，因為含有0 或 1 個紅點的行最多 999 個，所以其他行含有紅點肯定大于等于 1999-999=1000 ,如果是大于 1000,那么根據(jù)抽屜原理，肯定有兩個這樣紅點在一 列，那么就會出現(xiàn)紅色三角形；如果是等于 1000 而沒有這樣的 2 個紅點在一列，說明有999 行只含有 1 個紅點，而剩下的一行全是紅點，那也肯定已經(jīng)出現(xiàn)直角三角形了，所以n 的最小值為 1999.級*1000北京市串七居円謖*杯“裁學(xué)北廉鼻蕎二翼齡“in13.若干箱貨物總重 19.5 噸，每箱重量不超過 353 千克那么最少需要多少輛載重量為 噸的汽

19、車，才能保證把這些箱貨物一次全部運走？【分析與解】 至少需要 16 輛車.15 輛車不一定能一次運完.例如這批貨物共有 65 只箱子，64 只箱子都是 301 千克，1 只箱的重量是 236 千克，那么 總重量為 301X64+236=19500 千克，恰好符合 19.5 噸的要求由于 301X5=1505（千克.超過 1.5 噸因此，每輛汽車最多只能裝4 只重量為 301 千克的箱子，15 輛汽車最多只能裝4X15=60（只重量為 301 千克的箱子.這樣，必然有4 只重量為 301 千克的箱子無法再裝運了.16 輛汽車一定能一次運完全部箱子：首先讓 12 輛汽車裝到剛剛超過 1.5 噸，即若取下最后裝的一只箱子就不超過1.5 噸再從這 12 輛汽車上把每輛車最后裝的那只箱子卸下來，并把這 12 只箱子分別裝上另外 3 輛空 車，每車 4箱，由于每車 4 箱總重量不超過 4X353=1412（千克因此也不超過 1.5 噸.這時，12+3=15 輛車就裝完原來前 12 輛車上的全部貨物，總重量超過 1.5X12=18（噸.而且每輛車載重不超過1.5 噸于是，剩下未裝車箱子總重量不足19.5-18