36.構(gòu)造與論證二匯總

1、第36講構(gòu)造與論證2內(nèi)容概述組合證明題，在論證中，有時需進行分類討論，有時則要著眼于極端情形，或從整體把握若干點及連接它們的一些線段組成圖，與此相關(guān)的題目稱為圖論問題，這里宜從特殊的點或線著手進行分析各種以染色為內(nèi)容，或通過染色求解的組合問題，基本的染色方式有相間染色與條形染色典型問題2甲、乙、丙三個班人數(shù)相同，在班級之間舉行象棋比賽各班同學(xué)都按l，2，4,依次編號.當兩個班比賽時，具有相同編號的同學(xué)在同一臺對壘.在甲、乙兩班比賽時，有15臺是男、女生對壘；在乙、丙班比賽時，有9臺是男、女生對壘試說明在甲、丙班比賽時,男、女生對壘的臺數(shù)不會超過24并指出在什么情況下,正好是24？【分析與解】不

2、妨設(shè)甲、乙比賽時，115號是男女對壘，乙、丙比賽時.在115號中有a臺男女對壘，15號之后有9-a臺男女對壘（0WaW9甲、丙比賽時，前15號，男女對壘的臺數(shù)是15-a（如果1號乙與1號丙是男女對壘，那么1號甲與1號丙就不是男女對壘，15號之后，有9-a臺男女對壘.所以甲、丙比賽時，男女對壘的臺數(shù)為15-a+9-a=24-2aW24.僅在a=0，即必須乙、丙比賽時男、女對壘的號碼，與甲、乙比賽時男、女對壘的號碼完全不同，甲、丙比賽時，男、女對壘的臺數(shù)才等于24將15X15的正方形方格表的每個格涂上紅色、藍色或綠色.證明：至少可以找到兩行，這兩行中某一種顏色的格數(shù)相同【分析與解】如果找不到兩行的

3、某種顏色數(shù)一樣，那么就是說所有顏色的列與列之問的數(shù)目不同那么紅色最少也會占：0+1+2+.+14=105個格子.同樣藍色和綠色也是，這樣就必須有至少：3X（0+l+2+-+14=315個格子.但是，現(xiàn)在只有15X15=225個格子，所以和條件違背，假設(shè)不成立，結(jié)論得證6.4個人聚會，每人各帶2件禮品，分贈給其余3個人中的2人試證明：至少有2對人，每對人是互贈過禮品的【分析與解】將這四個人用4個點表示，如果兩個人之間送過禮，就在兩點之間連一條線由于每人送出2件禮物，圖中共有4X2=8條線，由于每人禮品都分贈給2個人，所以每兩點之間至多有1+1=2條線四點間，每兩點連一條線，一共6條線，現(xiàn)在有8條

4、線，說明必有兩點之間連了2條線，還有另外兩點（有一點可以與前面的點相同之間也連了2條線即為所證結(jié)論。8若干臺計算機聯(lián)網(wǎng)，要求：任意兩臺之間最多用一條電纜連接；任意三臺之間最多用兩條電纜連接；兩臺計算機之間如果沒有電纜連接，則必須有另一臺計算機和它們都連接有電纜若按此要求最少要用79條電纜問：（1這些計算機的數(shù)量是多少臺?（2這些計算機按要求聯(lián)網(wǎng)，最多可以連多少條電纜?【分析與解】將機器當成點，連接電纜當成線，我們就得到一個圖，如果從圖上一個點出發(fā)，可以沿著線跑到圖上任一個其它的點，這樣的圖就稱為連通的圖，條件表明圖是連通圖.我們看一看幾個點的連通圖至少有多少條線可以假定圖沒有圈（如果有圈，就在

5、圈上去掉一條線，從一點出發(fā)，不能再繼續(xù)前進，將這一點與連結(jié)這點的線去掉考慮剩下的n-l個點的圖，它仍然是連通的用同樣的辦法又可去掉一點及一條線這樣繼續(xù)下去，最后只剩下一個點因此n個點的連通圖至少有n-l條線（如果有圈，線的條數(shù)就會增加，并且從一點A向其他n-l個點各連一條線，這樣的圖恰好有n-l條線.因此，（1的答案是n=79+l=8，并且將一臺計算機與其他79臺各用一條線相連，就得到符合要求的聯(lián)網(wǎng).下面看看最多連多少條線.與，相連的點是，”，由于在這80個點（80臺計算機中，設(shè)從引出的線最多，有k條,條件，“/之間沒有線相連.，九每一點至多引出k條線，圖中v（耐IJt）=MOO設(shè)與J不相連的

6、點是，小，J，則m+k=80,而，至多有mk條線，因為人所以mXk1600，即連線不超過1600條.另一方面，設(shè)80個點分為兩組：第一組的每一點與第二組的每一點各用一條線相連，這樣的圖符合題目要求，共有40X40=1600條線.10.在一個6X6的方格棋盤中，將若干個1X1的小方格染成紅色如果隨意劃掉3行3列，在剩下的小方格中必定有一個是紅色的那么最少要涂多少個方格?【分析與解】方法一：顯然，我們先在每行、每列均涂一個方格，使之成為紅色，如圖A所示，但是在圖B中，劃去3行3列后，剩下的方格沒有紅色的，于是再將兩個方格涂成紅色（依據(jù)對稱性，應(yīng)將2個方格同時涂成紅色，如圖C所示，但是圖D的劃法，又

7、使剩下的方格沒有紅色，于是再將兩個方格涂成紅色（還是由于對稱的緣故，將2個方格涂成紅色，得到圖E,圖E不管怎么劃去3行3列，都能使剩下的方格含有紅色的.這時共涂了10個方格.方法二：一方面，圖F表明無論去掉哪三行哪三列總會留下一個涂紅的方格.另一方面，如果只涂9個紅色方格，那么紅格最多的三行至少有6個紅格（否則第三多的行只有1個紅格，紅格總數(shù)冬5+3=8，去掉這三行至多還剩3個紅格，再去掉三列即可將這三個紅格也去掉.綜上所述，至少需要將10個方格涂成紅色.12.證明：在6X6X6的正方體盒子中最多可放入52個1XIX4的小長方體，這里每個小長方體的面都要與盒子的側(cè)面平行【分析與解】先將6X6X

8、6的正方體盒子視為實體，那么6X6X6的正方體可分成216個小正方體，這216個小正方體可以組成27個棱長為2的正方體我們將這27個棱長為2的正方體按黑白相間染色，如下圖所示其中有14個黑色的，13個白色的，而一個白色的2X2X2的正方體可以對應(yīng)的放人4個每個面都與盒子側(cè)面平行的1X1X4的小長方體，所以最多可以放入13X4=52個1X1X4的小長方體.評注：6X6X6的正方體的體積為216，1X1X4的小長方體的體積為4，所以可放入的小正方體數(shù)目不超過2164=54個.14.用若干個1X6和1X7的小長方形既不重疊，也不留孔隙地拼成一個11X12的大長方形，最少要用小長方形多少個?分析與解】我們先通過面積計算出最優(yōu)情況：11X12=132，設(shè)用1X6的小長方形x個，用1X7的小長方形y個，有，-1.Jt=十7解得：=-肌(t為可取0的自然數(shù)，共需x+y=19+t個小長方形.(1當t=0時，即x+y=l+18=19,表示其中的1X6的小長方形只有1個，剩下的18個小長方形都是1X