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

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

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

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

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

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

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

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

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