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

2、少需 3 次，得到的順序為 54123;現在將第 3 卷調至此時第 I 卷的位置最少需 2 次，得到的順序為 54312;最后將第 I 卷和第 2 卷對調即可.所以，共需調換 4+3+2+仁 10 次.酸級數：車車車拿 E19曲牟罷十五屆全俄盤學龕舐匹丸丸年緘第1魏2.有 3 堆小石子，每次允許進行如下操作：從每堆中取走同樣數目的小石子，或是將其中的某一石子數是偶數的堆中的一半石子移入另外的一堆開始時，第一堆有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 因為操作就兩種，每堆取走同樣數目的小石子，將有偶數堆石子堆中一半移至另一堆，所 以每次操作石子總數要么減少3 的倍數，要么不變.現在共有 1989+989+89=3067,不是 3 的倍數，所以不能將 3 堆中所有石子都取走.矽蛾跌拿拿雀一3.在 1997X1997 的正方形棋盤上的每格都裝有一盞燈和一個按鈕.按鈕每按一次，與它同一 行和同一列方格中的燈泡都改變一次狀態，即由亮變為不亮，或由不亮變為亮如果原來每盞 燈都是不亮的，請說明最少需要按多少次按鈕才可以

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

5、，業余選手每負一場扣 1 分問：一位業余選手最 少要勝幾場，才能確保他的得分比某位專業選手高？【分析與解】 當一位業余選手勝 2 場時，如果只勝了另兩位業余選手，那么他得10+2-3=9（分此時，如果專業選手間的比賽均為一勝一負，而專業選手與業余選手比賽全勝，那么 每位專業選手的得分都是10+2-2+3=13（分所以，一位業余選手勝2 場，不能確保他的得分比某位專業選手高.當一位業余選手勝 3 場時，得分最少時是勝兩位業余選手，勝一位專業選手，得10+2+2-2=12（分.此時，三位專業選手最多共得30+0+4=34（分，其中專業選手之間的三場比賽共得0I分，專業選手與業余選手的比賽最多共得4

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

7、+3+4+5=14 12,不滿足.即 n=4 不可能.(2)我們知道 5 個隊共進行場比賽，而每場比賽有 2 分產生，所以 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 個數分別填入圖中的 10 個圓圈內, 使任意連續相鄰的 5 個圓圈內的各數之和均不大于某個整數M.求 M 的最小值并完成你的填圖分析與解】要使 圓圈內的數特別小，有的特別大，那么 的.下面來驗證 M=28 時是否成立，注意到圓圈內全部數的總和是55，所以肯定是一邊五個的和是 28, 一邊是 27.因為數字都不一樣，所以和 28 肯定是相間排列，和 27 也是相問排列， 也就是說數組每隔 4 個差值為 I，這樣從 1 填起，容易排出適當的填圖7.(1 將 1, 2, 3, 4, 5, 6, 7, 8, 9 這 9 個數字排列在圓周上，使得任意相鄰兩數的差(大減

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

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

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

12、為它們參與的乘式比較多，把它們去掉有助于使剩下的構不成乘式，比較小的數肯定是用得最多的，因為它們的倍 數最多，所以考慮先把它們去掉，但關鍵是除到何處？考慮到 44 的平方為 1936，所以去到 44 就夠了，因為如果剩下的構成了乘式，那么乘式 中最小的數一定小于等于44,所以可以保證剩下的構不成乘式因為對結果沒有影響，所以可以將 1 保留，于這 43 個數.但是，是不是去掉 43 個數為最小的方法呢？構造 2X97, 3X96, 4X95,，44X45,發 現這 43組數全不相同而且結果都比1998 小,所以要去掉這些乘式就至少要去掉43 個數，所以 43 位最小值，即為所求觀愆級數：車拿車車

13、9. 組互不相同的自然數，其中最小的數是 I，最大的數是 25,除 1 之外，這組數中的任一個數 或者等于這組數中某一個數的 2 倍，或者等于這組數中某兩個數之和 問：這組數之和的最小 值是多少？當取到最小值時，這組數是怎樣構成的？【分析與解】 首先把這組數從小到大排列起來，那么最小的肯定為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 是奇數，只能是一個偶數加上一個奇數在中間省略的數中不能只有1 個數，所以至少還要添加兩個數，而且這兩個數的和不能小于25，否則就無法得到 25 這個數.要求求出最小值，先看這兩個數的和是25 的情況，因為省略的兩個數不同于前面的數，所以從 20+5 開始.25=20+5=19+6=18+7=17+8=16+9=15+10=14+11=13+12.這些數中 20 , 19, 18, 17 太大，無法產生，所以看:16+9=

15、15+10=14+1 仁 13+12.看這些誰能出現和最小的 I , 2, 3, 4,，25 中，檢驗發現沒有可以滿足的:再看 I , 2, 3, 5，25,發現 1, 2, 3, 5, 10, 15, 25 滿足，所以：1+2+3+5+10+15+25=36+25=6110.在 10X19 方格表的每個方格內，寫上0 或 1,然后算出每行及每列的各數之和問最多能得到多少個不同的和數？【分析與解】 首先每列的和最少為 0,最多是 10,每行的和最少是 0,最多是 19,所以 不同的和最多也就是 0, 1, 2, 3, 4,，18, 19 這 20 個.下面我們說明如果 0 出現，那么必然有另外

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

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

18、個紅點分布在 1000 行中，肯定有一些行含有 2 個或者以上的紅點，因為含有0 或 1 個紅點的行最多 999 個，所以其他行含有紅點肯定大于等于 1999-999=1000 ,如果是大于 1000,那么根據抽屜原理，肯定有兩個這樣紅點在一 列，那么就會出現紅色三角形；如果是等于 1000 而沒有這樣的 2 個紅點在一列，說明有999 行只含有 1 個紅點，而剩下的一行全是紅點，那也肯定已經出現直角三角形了，所以n 的最小值為 1999.級*1000北京市串七居円謖*杯“裁學北廉鼻蕎二翼齡“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