第四十六章染色和覆蓋問(wèn)題

第四十六章染色與覆蓋問(wèn)題概念本講我們將一起學(xué)習(xí)染色與覆蓋。而這里所說(shuō)的染色問(wèn)題并不是規(guī)定如何染色，然后有多少種染色辦法等數(shù)學(xué)問(wèn)題。而是一種解決邏輯推理題的一種辦法，一種將研究對(duì)象分類的形象化的辦法。通過(guò)將要解決的問(wèn)題適宜的染色，能夠使我們更形象的觀察分析其中所蘊(yùn)含的關(guān)系，在通過(guò)一定的推理從而得到問(wèn)題的答案。具體介紹：座位染色問(wèn)題分析題中規(guī)定每個(gè)座位的前后左右都是他的鄰座，那么35名同窗每個(gè)人都正好坐到它的鄰座上能否辦到？像這種問(wèn)題我們?cè)撊绾慰紤]呢？直接一步一步操作嗎？很顯然是很不現(xiàn)實(shí)的，那么有什么辦法能讓我們更直接的找到答案呢？染色。我們將35個(gè)座位染成黑白相間的形式，一眼就能看出，每個(gè)黑色的座位都是白色座位的鄰座，也就是說(shuō)如果35名同窗每個(gè)人都正好能坐到它的鄰座上，那么必然是，黑白位置對(duì)換，但從圖中我們看到黑色17格，白色18格，黑白個(gè)數(shù)不相等，因此無(wú)法辦到。二、途徑問(wèn)題分析如果一次次的操作的話很難看出與否能夠按規(guī)定辦到。因此我們按例1的辦法，將9個(gè)小格染成黑白相間的顏色，很明顯就能看出是不能辦到的。由于從A格出去，第一步不管往哪走都會(huì)走入黑格，接著第二步又都會(huì)走入黑格，即走奇數(shù)步后進(jìn)黑格，偶數(shù)步后進(jìn)白格，這個(gè)人若要從A格出去又要回到A格，必須走9個(gè)格，因此最后一格必為黑才能夠，而A格為白格，因此不能夠。三、結(jié)點(diǎn)問(wèn)題分析與途徑問(wèn)題相似，只但是我們這回染得不再是小格而是點(diǎn)，染成黑白相間的點(diǎn)。我們會(huì)發(fā)現(xiàn)一共14個(gè)點(diǎn)，6個(gè)黑點(diǎn)8個(gè)白點(diǎn)，每次的路線仍是從黑點(diǎn)走到白點(diǎn)或者從白點(diǎn)走到黑點(diǎn)，因此若想每個(gè)點(diǎn)不重復(fù)的都走一遍的話必須黑白相等或相差1個(gè)，但本題黑白差2個(gè)，因此不能夠。四、普通覆蓋將這14個(gè)小格染成黑白相間的，那么7個(gè)相鄰兩方格應(yīng)當(dāng)是一黑一白的，因此如果能覆蓋的話，14個(gè)格中的黑白格數(shù)應(yīng)當(dāng)是相等的，但圖中有8個(gè)黑格，6個(gè)白格。因此不能夠。特殊覆蓋分析由于每次有兩個(gè)數(shù)同時(shí)加上或減去同一種數(shù)（假設(shè)次數(shù)為a），因此通過(guò)一次這樣的操作后，相稱于加上或減去了a的2倍，那么9個(gè)數(shù)總和就會(huì)多或者少偶數(shù)個(gè)數(shù)，也就是說(shuō)9個(gè)數(shù)的總和為45，通過(guò)1次操作后總和加上或減去一種偶數(shù)后應(yīng)當(dāng)還是奇數(shù)，但表（2）中的總和是4，因此不可能。例題如圖29-1(a),3行7列小方格每一種染上紅色或藍(lán)色.試證:存在一種矩形,它的四個(gè)角上的小方格顏色相似.(第2屆全國(guó)部分省市初中數(shù)學(xué)通訊賽題)證明:用15塊大小是4×1的矩形瓷磚和1塊大小是2×2的矩形瓷磚，不能正好鋪蓋8×8矩形的地面.（1986年北京初二數(shù)學(xué)競(jìng)賽題）如圖29-4（1）是4個(gè)1×1的正方形構(gòu)成的“L”形，用若干個(gè)這種“L”形硬紙片無(wú)重迭拼成一種m×n（長(zhǎng)為m個(gè)單位，寬為n個(gè)單位）的矩形如圖29-4（2）.試證明mn必是8的倍數(shù).（1947年匈牙利數(shù)學(xué)奧林匹克試題）世界上任何六個(gè)人中，一定有3個(gè)人或者互相認(rèn)識(shí)或者互相都不認(rèn)識(shí).?（1953年美國(guó)普特南數(shù)學(xué)競(jìng)賽題）空間六點(diǎn)，任三點(diǎn)不共線，任四點(diǎn)不共面，成對(duì)地連接它們得十五條線段，用紅色或藍(lán)色染這些線段（一條線段只染一種顏色）.求證:無(wú)論如何染,總存在同色三角形.?(第6屆國(guó)際數(shù)學(xué)奧林匹克試題)有17位科學(xué)家,其中每一種人和其它全部人的人通信,他們的通信中只討論三個(gè)題目.求證:最少有三個(gè)科學(xué)家互相之間討論同一種題目.（首屆全國(guó)中學(xué)生數(shù)學(xué)冬令營(yíng)試題）能否把1，1，2，2，3，3，…，1986，1986這些數(shù)排成一行，使得兩個(gè)1之間夾著一種數(shù)，兩個(gè)2之間夾著兩個(gè)數(shù)，…，兩個(gè)1986、之間夾著一千九百八十六個(gè)數(shù)？請(qǐng)證明你的結(jié)論.對(duì)平面上一種點(diǎn)，任意染上紅、藍(lán)、黑三種顏色中的一種.證明:平面內(nèi)存在端點(diǎn)同色的單位線段.9.?6×6的方格盤，能否用一塊大小為3格，形如的彎角板與11塊大小為3×1的矩形板，不重迭不遺漏地來(lái)鋪滿整個(gè)盤面.10.?（第49屆蘇聯(lián)基輔數(shù)學(xué)競(jìng)賽題）在兩張1982×1983的方格紙涂上紅、黑兩種顏色，使得每一行及每一列都有偶數(shù)個(gè)方格是黑色的.如果將這兩張紙重迭時(shí)，有一種黑格與一種紅格重疊，證明最少尚有三個(gè)方格與不同顏色的方格重疊.11.?有九名數(shù)學(xué)家，每人至多會(huì)講三種語(yǔ)言，每三名中最少有2名能通話，那么其中必有3名能用同一種語(yǔ)言通話.12.?如果把上題中的條件9名改為8名數(shù)學(xué)家，那么，這個(gè)結(jié)論還成立嗎？為什么？13.?設(shè)n=6（r-2）+3（r≥3），求證：如果有n名科學(xué)家，每人至多會(huì)講3種語(yǔ)言，每3名中最少有2名能通話，那么其中必有????r名能用同一種語(yǔ)言通話.14.?（1966年波蘭數(shù)學(xué)競(jìng)賽題）大廳中會(huì)聚了100個(gè)客人，他們中每人最少認(rèn)識(shí)67人，證明在這些客人中一定能夠找到4人，他們之中任何兩人都彼此相識(shí).15.?（首屆全國(guó)數(shù)學(xué)冬令營(yíng)試題）用任意方式給平面上的每一種點(diǎn)染上黑色或白色.求證：一定存在一種邊長(zhǎng)為1或的正三角形，它三個(gè)頂點(diǎn)是同色的.16.六年級(jí)一班全班有35名同窗，共分成5排，每排7人，坐在教室里，每個(gè)座位的前后左右四個(gè)位置都叫做它的鄰座．如果要讓這35名同窗各人都正好坐到他的鄰座上去，能辦到嗎?為什么？17.右圖是某一湖泊的平面圖，圖中全部曲線都是湖岸.(1)如果P點(diǎn)在岸上，那么A點(diǎn)是在岸上還是在水中？(2)某人過(guò)此湖泊，他下水時(shí)脫鞋，上岸時(shí)穿鞋.如果他從A點(diǎn)出發(fā)走到某點(diǎn)B，他穿鞋與脫鞋的總次數(shù)是奇數(shù)，那么B點(diǎn)是在岸上還是在水中？為什么？某班有45名同窗按9行5列坐好．老師想讓每位同窗都坐到他的鄰座(前后左右)上去，問(wèn)這能否辦到?右圖是某一套房子的平面圖，共12個(gè)房間，每相鄰兩房間都有門相通．請(qǐng)問(wèn)：你能從某個(gè)房間出發(fā)，不重復(fù)地走完每個(gè)房間嗎?20.有一次車展共6×6=36個(gè)展室，如右圖，每個(gè)展室與相鄰的展室都有門相通，入口和出口如圖所示．參觀者能否從入口進(jìn)去，不重復(fù)地參觀完每個(gè)展室再?gòu)某隹诔鰜?lái)？21.在一種正方形的果園里，種有63棵果樹，加上右下角的一間小屋，整潔地排列成八行八列，如圖（1）.守園人從小屋出發(fā)通過(guò)每一棵樹，不重復(fù)也不遺漏(不許斜走)，最后又回到小屋，行嗎？如果有80棵果樹，如圖（2），連小屋排成九行九列呢？22.右圖是半張中國(guó)象棋盤，棋盤上已放有一只馬.眾所周知，馬是走“日”字的.請(qǐng)問(wèn)：這只馬能否不重復(fù)地走遍這半張棋盤上的每一種點(diǎn)，然后回到出發(fā)點(diǎn)？右圖是由14個(gè)大小相似的方格構(gòu)成的圖形.試問(wèn)能不能剪裁成7個(gè)由相鄰兩方格構(gòu)成的長(zhǎng)方形？右圖是由40個(gè)小正方形構(gòu)成的圖形，能否將它剪裁成20個(gè)相似的長(zhǎng)方形？下面的三個(gè)圖形都是從4×4的正方形紙片上剪去兩個(gè)1×1的小方格后得到的.問(wèn)：能否把它們分別剪成1×2的七個(gè)小矩形.用11個(gè)和5個(gè)能否蓋住8×8的大正方形?27.能否用9個(gè)所示的卡片拼成一種6×6的棋盤？28.9個(gè)1×4的長(zhǎng)方形不能拼成一種6×6的正方形，請(qǐng)你闡明理由！29.用若干個(gè)2×2和3×3的小正方形不能拼成一種11×11的大正方形，請(qǐng)你闡明理由！對(duì)于表（1），每次使其中的任意兩個(gè)數(shù)減去或加上同一種數(shù)，能否通過(guò)若干次后（各次減去或加上的數(shù)能夠不同），變?yōu)楸恚?）？為什么？右圖是一種圓盤，中心軸固定在黑板上.開始時(shí)，圓盤上每個(gè)數(shù)字所對(duì)應(yīng)的黑板處均寫著0.然后轉(zhuǎn)動(dòng)圓盤，每次能夠轉(zhuǎn)動(dòng)90°的任意整數(shù)倍，圓盤上的四個(gè)數(shù)將分別正對(duì)著黑板上寫數(shù)的位置，將圓盤上的數(shù)加到黑板上對(duì)應(yīng)位置的數(shù)上.問(wèn)：通過(guò)若干次后，黑板上的四個(gè)數(shù)與否可能都是999？有7個(gè)蘋果要平均分給12個(gè)小朋友，園長(zhǎng)規(guī)定每個(gè)蘋果最多分成5份．應(yīng)當(dāng)如何分？有一位老人，他有三個(gè)兒子和十七匹馬.他在臨終前對(duì)他的兒子們說(shuō)：“我已經(jīng)寫好了遺囑，我把馬留給你們，你們一定要按我的規(guī)定去分.”老人逝世后，三兄弟看到了遺囑.遺囑上寫著：“我把十七匹馬全都留給我的三個(gè)兒子.長(zhǎng)子得1/2,次子得1/3,給幼子1/9,不許流血，不許殺馬.你們必須遵從父親的遺愿！”請(qǐng)你協(xié)助他們分分馬吧！34.8個(gè)金幣中，有一種比真金幣輕的假金幣，你能用天平稱兩次就找出來(lái)嗎（天平無(wú)砝碼）？9個(gè)金幣中，有一種比真金幣輕的假金幣，你能用天平稱兩次就找出來(lái)嗎（天平無(wú)砝碼）？36.據(jù)說(shuō)有一天，韓信騎馬走在路上，看見(jiàn)兩個(gè)人正在路邊為分油發(fā)愁，這兩個(gè)人有一只容量10斤的簍子，里面裝滿了油；尚有一只空的罐和一只空的葫蘆，罐可裝7斤油，葫蘆可裝3斤油.要把這10斤油平分，每人5斤.但是誰(shuí)也沒(méi)有帶秤，只能拿手頭的三個(gè)容器倒來(lái)倒去.應(yīng)當(dāng)如何分呢？大桶能裝5公斤油，小桶能裝4公斤油，你能用這兩只桶量出6公斤油嗎?怎么量？有一種小朋友叫小滿，他學(xué)會(huì)了韓信分油的辦法，心里很是得意.一天，他碰到了兩位農(nóng)婦.兩位農(nóng)婦有兩個(gè)各裝滿了10升奶的罐子，尚有一種5升和一種4升的小桶，她們請(qǐng)求小滿就用這些容器將罐子中的奶給兩個(gè)小桶中各倒入2升奶.小滿按照韓信分油的辦法，略加變通，就將奶分好了！你說(shuō)說(shuō)具體的做法！有大，中，小3個(gè)瓶子，最多分別能夠裝入水1000克，700克和300克.現(xiàn)在大瓶中裝滿水，但愿通過(guò)水在3個(gè)瓶子間的流動(dòng)使得中瓶和小瓶上標(biāo)出100克水的刻度線，問(wèn)最少要倒幾次水40.老師在黑板上畫了9個(gè)點(diǎn)，規(guī)定同窗們用一筆畫出一條通過(guò)這9個(gè)點(diǎn)的折線(只許拐三個(gè)彎兒)．你能辦到嗎?如右圖所示，將1～12順次排成一圈.如果報(bào)出一種數(shù)a（在1～12之間），那么就從數(shù)a的位置順時(shí)針走a個(gè)數(shù)的位置.例如a=3，就從3的位置順時(shí)針走3個(gè)數(shù)的位置達(dá)成6的位置；a=11，就從11的位置順時(shí)針走11個(gè)數(shù)的位置達(dá)成10的位置.問(wèn)：a是多少時(shí)，能夠走到7的位置？對(duì)于任意一種自然數(shù)n，當(dāng)n為奇數(shù)時(shí)，加上121；當(dāng)n為偶數(shù)時(shí)，除以2，這算一次操作現(xiàn)在對(duì)231持續(xù)進(jìn)行這種操作，在操作過(guò)程中與否可能出現(xiàn)100？43.一只電動(dòng)老鼠從左下圖的A點(diǎn)出發(fā)，沿格線奔跑，并且每到一種格點(diǎn)不是向左轉(zhuǎn)就是向右轉(zhuǎn)。當(dāng)這只電動(dòng)老鼠又回到A點(diǎn)時(shí)，甲說(shuō)它共轉(zhuǎn)了81次彎，乙說(shuō)它共轉(zhuǎn)了82次彎。如果甲、乙二人有一人說(shuō)對(duì)了，那么誰(shuí)對(duì)的？44.如圖（1），對(duì)相鄰的兩格內(nèi)的數(shù)同時(shí)加上1或同時(shí)減去1叫做一次操作.通過(guò)若干次操作后由1變成圖2，則圖2中A處的數(shù)是多少？45.一種大桶裝了12升水，另外有正好能裝8升和5升水的桶各一種.運(yùn)用這三個(gè)桶最少倒幾次才干把這12升水平均分成兩份?46.一種正方形果園里種有48棵果樹，加上右下角的一間小屋，整潔地排列成七行七列（見(jiàn)右圖）守園人從小屋出發(fā)通過(guò)每一棵樹，不重復(fù)也不遺漏（不許斜走），最后又回到小屋.能夠做到嗎？47.如右圖，缺兩格的8×8方格有62個(gè)格，能否用31個(gè)圖不重復(fù)地蓋住它且不留空隙?只有5升和8升的容器，要如何量出2升的水呢?49.下圖的七種圖形都是由4個(gè)相似的小方格構(gòu)成的。現(xiàn)在要用這些圖形拼成一種4×7的長(zhǎng)方形（能夠重復(fù)使用某些圖形），那么，最多能夠用上幾個(gè)不同的圖形？50.用1×1，2×2，3×3的小正方形拼成一種11×11的大正方形，最少要用1×1的正方形多少個(gè)？51.用七個(gè)1×2的小長(zhǎng)方形覆蓋下圖，共有多少種不同的覆蓋方法？有許多邊長(zhǎng)為1厘米、2厘米、3厘米的正方形硬紙片。用這些硬紙片拼成一種長(zhǎng)5厘米、寬3厘米的長(zhǎng)方形的紙板，共有多少種不同的拼法？（通過(guò)旋轉(zhuǎn)及翻轉(zhuǎn)能互相得到的拼法認(rèn)為是相似的拼法）53.小明有8張連在一起的電影票（如右圖），他自己要留下4張連在一起的票，其它的送給別人。他留下的四張票能夠有多少種不同狀況？有若干個(gè)邊長(zhǎng)為1、邊長(zhǎng)為2、邊長(zhǎng)為3的小正方形，從中選出某些拼成一種邊長(zhǎng)為4的大正方形，共有多少種不同拼法？（只要選擇的多個(gè)小正方形的數(shù)目相似就算相似的拼法）能不能用9個(gè)1×4的長(zhǎng)方形卡片拼成一種6×6的正方形？某影院有31排，每排29個(gè)座位，某天放映了兩場(chǎng)電影，每個(gè)座位上都坐了一種觀眾，如果規(guī)定每個(gè)觀眾在看第二場(chǎng)電影時(shí)必須跟他前后左右相鄰的某一觀眾交換座位，這樣能辦到嗎？五年級(jí)一班有49名同窗，共分成7排，每排7個(gè)人。新年到了，每個(gè)同窗都準(zhǔn)備了一種禮物送給自己前后左右相鄰的某一種同窗，那么有無(wú)可能每個(gè)同窗都剛好收到一種別人送的禮物？58.有一次車展共4×4=16個(gè)展室，如圖，每個(gè)展室與相鄰的展室都有門相通，入口和出口如圖所示，參觀者能否從入口進(jìn)去，不重復(fù)的參觀完每個(gè)展室再?gòu)某隹诔鰜?lái)？有一次車展共6×6=36個(gè)展室，如圖，每個(gè)展室與相鄰的展室都有門相通，入口和出口如圖所示，參觀者能否從入口進(jìn)去，不重復(fù)的參觀完每個(gè)展室再?gòu)某隹诔鰜?lái)？60.有一次車展共5×5=25個(gè)展室，如圖，每個(gè)展室與相鄰的展室都有門相通，入口和出口如圖所示，參觀者能否從入口進(jìn)去，不重復(fù)的參觀完每個(gè)展室再?gòu)某隹诔鰜?lái)？答案與解析1.【分析與解】證明?由抽屜原則,第1行的7個(gè)小方格最少有4個(gè)不同色,不妨設(shè)為紅色(帶陰影)并在1、2、3、4列（如圖29-1（b））.在第1、2、3、4列（下列不必再考慮第5，6，7列）中，如第2行或第3行出現(xiàn)兩個(gè)紅色小方格，則這個(gè)問(wèn)題已經(jīng)得證；如第2行和第3行每行最多只有一種紅色小方格（如圖29-1（c）），那么在這兩行中必出現(xiàn)四角同為藍(lán)色的矩形，問(wèn)題也得到證明.闡明：（1）在上面證明過(guò)程中除了運(yùn)用抽屜原則外，還要用到一種思考問(wèn)題的有效辦法，就是逐步縮小所要討論的對(duì)象的范疇，把復(fù)雜問(wèn)題逐步化為簡(jiǎn)樸問(wèn)題進(jìn)行解決的辦法.此例的行和列都不能再減少了.顯然只有兩行的方格盤染兩色后是不一定存在頂點(diǎn)同色的矩形的.下面我們舉出一種3行6列染兩色不存在頂點(diǎn)同色矩形的例子如圖29-2.這闡明3行7列是染兩色存在頂點(diǎn)同色的矩形的最小方格盤了.至今,染k色而存在頂點(diǎn)同色的矩形的最小方格盤是什么還不得而知.【分析與解】分析?將8×8矩形地面的二分之一染上一種顏色，另二分之一染上另一種顏色，再用4×1和2×2的矩形瓷磚去蓋，如果蓋住的兩種顏色的小矩形不是同樣多，則闡明在給定條件不完滿鋪蓋不可能.證明?如圖29-3，用間隔為兩格且與副對(duì)角線平行的斜格同色的染色方式，以黑白兩種顏色將整個(gè)地面的方格染色.顯然，地面上黑、白格各有32個(gè).每塊4×1的矩形磚不管是橫放還是豎蓋，且不管蓋在何處，總是占據(jù)地面上的兩個(gè)白格、兩個(gè)黑格，故15塊4×1的矩形磚鋪蓋后還剩兩個(gè)黑格和兩個(gè)白格.但由于與副對(duì)角線平行的斜格總是同色，而與主對(duì)角線平行的相鄰格總是異色，因此，不管如何放置，一塊2×2的矩形磚，總是蓋住三黑一白或一黑三白.這闡明剩余的一塊2×2矩形磚無(wú)論如何蓋不住剩余的二黑二白的地面.從而問(wèn)題得證.??3.【分析與解】證明∵m×n矩形由“L”形拼成，∴m×n是4的倍數(shù)，∴m、n中必有一種是偶數(shù)，不妨設(shè)為m.把m×n矩形中的m列按一列黑、一列白間隔染色（如圖29-4（2）），則不管“L”形在這矩形中的放置位置如何（“L”形的放置，共有8種可能），“L”形或占有3白一黑四個(gè)單位正方形（第一種），或占有3黑一白四個(gè)單位正方形（第二種）.設(shè)第一種“L”形共有p個(gè)，第二種“L”形共q個(gè)，則m×n矩形中的白格單位正方形數(shù)為3p+q，而它的黑格單位正方形數(shù)為p+3q.∵m為偶數(shù)，∴m×n矩形中黑、白條數(shù)相似，黑、白單位正方形總數(shù)也必相等.故有3p+q=p+3q，從而p=q.因此“L”形的總數(shù)為2p個(gè)，即“L”形總數(shù)為偶數(shù)。因此m×n一定是8的倍數(shù).?4.【分析與解】我們不直接證明這個(gè)命題，而來(lái)看與之等價(jià)的下述命題5.【分析與解】證明?設(shè)A、B、C、D、E、F是所給六點(diǎn).考慮以A為端點(diǎn)的線段AB、AC、AD、AE、AF，由抽屜原則這五條線段中最少有三條顏色相似，不妨設(shè)就是AB、AC、AD，且它們都染成紅色.再來(lái)看△BCD的三邊，如其中有一條邊例如BC是紅色的，則同色三角形已出現(xiàn)（紅色△ABC）；如△BCD三邊都不是紅色的，則它就是藍(lán)色的三角形，同色三角形也現(xiàn)了.總之,不管在哪種狀況下,都存在同色三角形.如果將例4中的六個(gè)人當(dāng)作例5中六點(diǎn),兩人認(rèn)識(shí)的連紅線,不認(rèn)識(shí)的連藍(lán)線,則例4就變成了例5.例5的證明事實(shí)上用染色辦法給出了例4的證明.6.【分析與解】證明?用平面上無(wú)三點(diǎn)共線的17個(gè)點(diǎn)A1,A2,…，A17分別表達(dá)17位科學(xué)家.設(shè)他們討論的題目為x,y,z,兩位科學(xué)家討論x連紅線,討論y連藍(lán)線,討論z連黃線.于是只須證明以這17個(gè)點(diǎn)為頂點(diǎn)的三角形中有一同色三角形.考慮以A1為端點(diǎn)的線段A1A2,A1A3,…，A1A17，由抽屜原則這16條線段中最少有6條同色，不妨設(shè)A1A2，A1A3，…，A1A7為紅色.現(xiàn)考察連結(jié)六點(diǎn)A2，A3，…，A7的15條線段，如其中最少有一條紅色線段，則同色（紅色）三角形已出現(xiàn)；如沒(méi)有紅色線段，則這15條線段只有藍(lán)色和黃色，由例5知一定存在以這15條線段中某三條為邊的同色三角形（藍(lán)色或黃色）.問(wèn)題得證.上述三例同屬圖論中的接姆賽問(wèn)題.在圖論中,將n點(diǎn)中每?jī)牲c(diǎn)都用線段相連所得的圖形叫做n點(diǎn)完全圖,記作kn.這些點(diǎn)叫做“頂點(diǎn)”，這些線段叫做“邊”.現(xiàn)在我們分別用圖論的語(yǔ)言來(lái)敘述例5、例6.定理1?若在k6中，任染紅、藍(lán)兩色，則必有一只同色三角形.定理2?在k17中,任染紅、藍(lán)、黃三角，則必有一只同色三角形.【分析與解】證明?將1986×2個(gè)位置按奇數(shù)位著白色，偶數(shù)位著黑色染色，于是黑白點(diǎn)各有1986個(gè).現(xiàn)令一種偶數(shù)占據(jù)一種黑點(diǎn)和一種白色，同一種奇數(shù)要么都占黑點(diǎn)，要么都占白點(diǎn).于是993個(gè)偶數(shù)，占據(jù)白點(diǎn)A1=993個(gè)，黑色B1=993個(gè).993個(gè)奇數(shù)，占據(jù)白點(diǎn)A2=2a個(gè)，黑點(diǎn)B2=2b個(gè)，其中a+b=993.因此，共占白色A=A1+A2=993+2a個(gè).黑點(diǎn)B=B1+B2=993+2b個(gè)，由于a+b=993（非偶數(shù)?。郺≠b，從而得A≠B.這與黑、白點(diǎn)各有1986個(gè)矛盾.故這種排法不可能.“點(diǎn)”能夠是有限個(gè)，也能夠是無(wú)限個(gè)，這時(shí)染色問(wèn)題總是與對(duì)應(yīng)的幾何問(wèn)題聯(lián)系在一起的.8.【分析與解】證明?作出一種如圖29-7的幾何圖形是可能的,其中△ABD、△CBD、△AEF、△GEF都是邊長(zhǎng)為1的等邊三角形，CG=1.不妨設(shè)A點(diǎn)是紅色，如果B、E、D、F中有紅色，問(wèn)題顯然得證.當(dāng)B、E、D、F都為藍(lán)點(diǎn)或黃點(diǎn)時(shí)，又如果B和D或E和F同色，問(wèn)題也得證.現(xiàn)設(shè)B和D異色E和F異色,在這種狀況下,如果C或G為黃色或藍(lán)點(diǎn),則CB、CD、GE、GF中有兩條是端點(diǎn)同色的單位線段，問(wèn)題也得證.否則的話,C、G均為紅點(diǎn)，這時(shí)CG是端點(diǎn)同色的單位線段.證畢.尚有一類較難的對(duì)區(qū)域染色的問(wèn)題，就不作介紹了.【分析與解】將１、４行染紅色、２、５行染黃色、３、６行染藍(lán)色，然后就彎角板蓋住板面的不同狀況分類討論．【分析與解】設(shè)第一張紙上的黑格Ａ與第二張紙上的紅格Ａ′重疊．如果在第一張紙上Ａ所在的列中，其它的黑格（奇數(shù)個(gè)）均與第二張紙的黑格重疊，那么由第二張紙上這一列的黑格個(gè)數(shù)為偶數(shù)，知必有一黑格與第一張紙上的紅格重疊，即在這一列，第一張紙上有一方格Ｂ與第二張紙上不同顏色的方格Ｂ′重疊．同理在Ａ、Ｂ所在行上各有一種方格Ｃ、Ｄ，第二張紙上與它們重疊的方格Ｃ′、Ｄ′的顏色分別與Ｃ、Ｄ不同．11.【分析與解】把９名數(shù)學(xué)家用點(diǎn)Ａ１，Ａ２，…，Ａ９表達(dá)．兩人能通話，就用線連結(jié)，并涂某種顏色，以表達(dá)不同語(yǔ)種。兩人不通話，就不連線．（１）果任兩點(diǎn)都有連線并涂有顏色，那么必有一點(diǎn)如Ａ１，以其為一端點(diǎn)的８條線段中最少有兩條同色，例如Ａ１Ａ２、Ａ１Ａ３．可見(jiàn)Ａ１，Ａ２，Ａ３之間可用同一語(yǔ)言通話．②如狀況①不發(fā)生，則最少有兩點(diǎn)不連線，例如Ａ１、Ａ２．由題設(shè)任三點(diǎn)必有一條連線知，其它七點(diǎn)必與Ａ１或Ａ２有連線．這時(shí)七條線中，必有四條是從某一點(diǎn)如Ａ１引出的．而這四條線中又必有二條同色，則問(wèn)題得證．【分析與解】結(jié)論不成立，如圖所示（圖中每條線旁都有一種數(shù)字，以表達(dá)不同語(yǔ)種）．【分析與解】類似于第11題證明．【分析與解】用點(diǎn)Ａ１、Ａ２、…、Ａ１００表達(dá)客人，紅、藍(lán)的連線分別表達(dá)兩人相識(shí)或不相識(shí)，由于由一種頂點(diǎn)引出的藍(lán)色的線段最多有３２條，因此其中最少有三點(diǎn)之間連紅線．這三個(gè)點(diǎn)（設(shè)為Ａ１、Ａ２、Ａ３）引出的藍(lán)色線段最多為９６條．去掉全部這些藍(lán)色的線段（連同每條線段上的一種端點(diǎn)ＡＩ，Ｉ≠１，２，３），這樣，在圖中最少還剩余四個(gè)點(diǎn)，除Ａ１、Ａ２、Ａ３外，設(shè)第四點(diǎn)為Ａ４，這四個(gè)點(diǎn)中Ａ１，Ａ２，Ａ３每一種點(diǎn)與其它的點(diǎn)都以紅色的線段相連，于是客人Ａ１、Ａ２、Ａ３、Ａ４彼此兩兩相識(shí)．15.【分析與解】先運(yùn)用右圖證明＂若平面上有兩個(gè)異色的點(diǎn)距離為２，地么必然能夠找到符合題意的三角形＂．再找長(zhǎng)為２端點(diǎn)異色的線段．以Ｏ（白色）為圓心，４為半徑作圓．如圓內(nèi)皆白點(diǎn)，問(wèn)題已證．否則圓內(nèi)有一黑點(diǎn)Ｐ，以ＯＰ為底作腰長(zhǎng)為２的三角形ＯＰＲ，則Ｒ最少與Ｏ、Ｐ中一點(diǎn)異色，這樣的線段找到．【分析與解】劃一種5×7的方格表，其中每一種方格表達(dá)一種座位．將方格黑白相間地染上顏色，這樣黑色座位與白色座位都成了鄰座．因此每位同窗都坐到他的鄰座相稱于全部白格的坐到黑格，全部黑格的坐到白格．而實(shí)際圖中有17個(gè)黑格18個(gè)白格，個(gè)數(shù)不等，故不能辦到．17.【分析與解】（1）已知P點(diǎn)在陸地上，如果在圖上用陰影表達(dá)陸地，就能夠看出A點(diǎn)在水中.（2）從水中通過(guò)一次陸地到水中，脫鞋與穿鞋的次數(shù)的和為2，由于A點(diǎn)在水中，因此不管怎么走，走在水中時(shí)，脫鞋、穿鞋的次數(shù)的和總是偶數(shù).既然題中說(shuō)“脫鞋的次數(shù)與穿鞋的次數(shù)的和是個(gè)奇數(shù)”，那么B點(diǎn)必然在岸上.【分析與解】將5×9長(zhǎng)方形自然染色，發(fā)現(xiàn)黑格的鄰座都是白格，白格的鄰座都是黑格，因此每位同窗都坐到他的鄰座相稱于全部白格的坐到黑格，全部黑格的坐到白格．而實(shí)際圖中有23個(gè)黑格22個(gè)白格，個(gè)數(shù)不等，故不能辦到．【分析與解】如圖所示，將房間黑白相間染色，發(fā)現(xiàn)只有5個(gè)白格，7個(gè)黑格．由于每次只能由黑到白或由白到黑，路線必然黑白相問(wèn)，顯然應(yīng)當(dāng)從多的白格開始．但路線上1白1黑1白1黑,,直到5白5黑后還余2黑，不可能從黑格到黑格，故無(wú)法實(shí)現(xiàn)不重復(fù)走遍．【分析與解】如右下圖，對(duì)每個(gè)展室黑白相間染色，同樣每次只能黑格到白格或白格到黑格．入口和出口處都是白格，故路線黑白相間，首尾都是白格，于是應(yīng)當(dāng)白格比黑格多1個(gè)，而事實(shí)上白格、黑格都是18個(gè)，故不可能做到不重復(fù)走遍每個(gè)展室．21.【分析與解】下圖(1)中能夠回到小屋，守園人只能黑白相間地走，走到的第奇數(shù)棵樹是白的，第偶數(shù)棵樹是黑的，走到第63棵樹應(yīng)是白的，在小屋相鄰的樹都標(biāo)注白色，因此能夠回到小屋圖(2)不行,從小屋出發(fā),當(dāng)走到80棵樹應(yīng)是黑色,而黑樹與小木屋不相鄰，無(wú)法直接回到小木屋.22.【分析與解】馬走“日”字，在中國(guó)象棋盤上走有什么規(guī)律呢？為方便研究規(guī)律，以下圖所示，先在棋盤各交點(diǎn)處相間標(biāo)上○和●，圖中共有22個(gè)○和23個(gè)●.由于馬走“日”字，每步只能從○跳到●，或由●跳到○，因此馬從某點(diǎn)跳到同色的點(diǎn)（指○或●），要跳偶數(shù)步；跳到不同色的點(diǎn)，要跳奇數(shù)步。現(xiàn)在馬在○點(diǎn)，要跳回這一點(diǎn)，應(yīng)跳偶數(shù)步，可是棋盤上共有23+22=45（個(gè)）點(diǎn)，不可能做到不重復(fù)地走遍全部的點(diǎn)后回到出發(fā)點(diǎn).如果馬的出發(fā)點(diǎn)不是在○點(diǎn)上而是在●點(diǎn)上，那么這只馬能不能不重復(fù)地走遍這半張棋盤上的每個(gè)點(diǎn)，最后回到出發(fā)點(diǎn)上呢？按照上面的分析，顯然也是不可能的.但是如果放棄“回到出發(fā)點(diǎn)”的規(guī)定，那么狀況就不同了.從某點(diǎn)出發(fā)，跳遍半張棋盤上除起點(diǎn)以外的其它44點(diǎn)，要跳44步，44是偶數(shù)，因此起點(diǎn)和終點(diǎn)應(yīng)是同色的點(diǎn)（指○或●）.由于44步跳過(guò)的點(diǎn)○與點(diǎn)●各22個(gè)，因此起點(diǎn)必是●，終點(diǎn)也是●.也就說(shuō)是，當(dāng)不規(guī)定回到出發(fā)點(diǎn)時(shí)，只要從●出發(fā)，就能夠不重復(fù)地走遍半張棋盤上的全部點(diǎn).【分析與解】將這14個(gè)小方格黑白相間染色（見(jiàn)右下圖），有8個(gè)黑格，6個(gè)白格.相鄰兩個(gè)方格必然是一黑一白，如果能剪裁成7個(gè)小長(zhǎng)方形，那么14個(gè)格應(yīng)當(dāng)是黑、白各7個(gè)，與實(shí)際狀況不符，因此不能剪裁成7個(gè)由相鄰兩個(gè)方格構(gòu)成的長(zhǎng)方形【分析與解】將40個(gè)小正方形想剪裁成20個(gè)相似的長(zhǎng)方形，就是將圖形分割成20個(gè)1×2的長(zhǎng)方形，將其黑白相間染色后，發(fā)現(xiàn)有21黑，19白，黑白格數(shù)不等，而1×2的小矩形一次覆蓋黑白格各一種.【分析與解】如右上圖，（1）能，黑白格數(shù)相等；（2）（3）不能，黑白格數(shù)不等，而1×2的小矩形一次覆蓋黑白格各一種.26.【分析與解】如右圖，對(duì)8×8正方形黑白相問(wèn)染色后，發(fā)現(xiàn)必然蓋住2白2黑，5個(gè)則蓋住10白10黑．則蓋住了3白1黑或3黑1白，從奇偶性考慮，都是奇數(shù)．而這種形狀共11個(gè)，奇數(shù)個(gè)奇數(shù)相加仍為奇數(shù)，故這種形狀蓋住的黑格和白格都是奇數(shù)，加另一種形狀的10白10黑，兩種形狀共蓋住奇數(shù)個(gè)白格奇數(shù)個(gè)黑格．但實(shí)際染色后共32個(gè)白格32個(gè)黑格，故不可能按題目規(guī)定蓋?。ⅲ罕绢}中每個(gè)蓋3白1黑或3黑1白，11個(gè)這種形狀蓋住的不一定是33白11黑或33黑11白，由于可能一部分蓋3白1黑，另一部分蓋3黑1白.這是一種容易出錯(cuò)的地方.27.【分析與解】不能.將6×6的棋盤黑白相間染色（見(jiàn)右圖），有18個(gè)黑格.每張卡片蓋住的黑格數(shù)不是1就是3，9張卡片蓋住的黑格數(shù)之和是奇數(shù)，不可能蓋住18個(gè)黑格.28.【分析與解】本題若用傳統(tǒng)的自然染色法，不能闡明問(wèn)題.我們對(duì)6×6正方形用四種顏色染色，由于要用1×4來(lái)覆蓋．為了方便起見(jiàn)，這里用1、2、3、4分別代表四種顏色．也為了使每個(gè)1×4長(zhǎng)方形在任何位置蓋住的都同樣，我們采用沿對(duì)角線染色，如右圖．這樣，能夠發(fā)現(xiàn)無(wú)論將1×4長(zhǎng)方形放于何處，蓋住的必然是1、2、3、4各一種．要不重疊地拼出6×6，需9個(gè)1×4長(zhǎng)方形，則必然蓋住1、2、3、4各9個(gè)．但事實(shí)上圖中一共是9個(gè)l、10個(gè)2、9個(gè)3、8個(gè)4，因而不可能用9個(gè)1×4長(zhǎng)方形拼出6×6正方形．29.【分析與解】如右圖所示，將2×2或3×3的小正方形沿格線擺在右圖的任何位置，必然蓋住偶數(shù)個(gè)陰影方格，而陰影方格共有77個(gè)，是奇數(shù)，因此只用2×2和3×3的小正方形，不可能拼成11×11的大正方形.30.【分析與解】由于每次有兩個(gè)數(shù)同時(shí)被加上或減去同一種數(shù)，因此表中九個(gè)數(shù)碼的總和通過(guò)變化后，等于原來(lái)的總和加上或減去那個(gè)數(shù)的2倍，因此總和的奇偶性沒(méi)有變化。原來(lái)九個(gè)數(shù)的總和為1+2++9=45，是奇數(shù)，通過(guò)若干次變化后，總和仍應(yīng)是奇數(shù)，與右上表九個(gè)數(shù)的總4矛盾。因此不可能變成右上表.【分析與解】不可能.由于每次加上的數(shù)之和是1＋2＋3＋4=10，因此黑板上的四個(gè)數(shù)之和永遠(yuǎn)是10的整數(shù)倍.999×4=3996，不是10的倍數(shù)，因此黑板上的四個(gè)數(shù)不可都是999.【分析與解】顯然每人應(yīng)當(dāng)分7/12=4/12+3/12=1/3+1/4,于是，拿4個(gè)蘋果，每個(gè)蘋果3等分；拿3個(gè)蘋果，每個(gè)蘋果4等分．【分析與解】這三個(gè)兄弟困惑不解，盡管他們?cè)趯W(xué)校里學(xué)習(xí)成績(jī)都不錯(cuò)，可是他們還是不會(huì)用17除以2、用17除以3、用17除以9，又不讓馬流血.于是他們就去請(qǐng)教本地一位公認(rèn)的智者.這位智者看了遺囑后來(lái)說(shuō)：“我借給你們一匹馬，去按你們父親的遺愿分吧！”老人原有17匹馬，加上智者借給的一匹，一共18匹.于是三兄弟按照18匹馬的1/2,1/3,1/9,分別得到了九匹、六匹和兩匹.9+6+2=17（匹）還剩余一匹，是智者借給的那匹，還給智者.【分析與解】解說(shuō)此題前，教師可先問(wèn)學(xué)生：“3個(gè)金幣，有1個(gè)假的比較輕，你稱1次能把它找出來(lái)么？”將8個(gè)金幣分成：3+3+2，3組，把3和3進(jìn)行稱量，如果重量相似，稱剩余的2個(gè)金幣即可找到假幣；如果重量不同，將比較重的3個(gè)金幣拿出，用天平稱量2個(gè)，剩余1個(gè)，天平不平衡易得答案，若此時(shí)天平平衡則剩余的那個(gè)是假的.35.【分析與解】第一次在左右兩托盤各放置3個(gè)：(一)如果不平衡，那么較輕的一側(cè)的3個(gè)中有一種是假的．從中任取兩個(gè)分別放在兩托盤內(nèi)：①如果不平衡，較低的一側(cè)的那個(gè)是假的；②如果平衡，剩余的一種是假的；(二)如果平衡，剩余的三個(gè)中必有一種為假的．從中任取兩個(gè)分別放在兩托盤內(nèi)：①如果不平衡，較低的一側(cè)的那個(gè)是假的；②如果平衡，剩余的那個(gè)是假的．這類稱量找假幣的問(wèn)題，一定要會(huì)分類，并盡量是每一類對(duì)應(yīng)天平稱量時(shí)的不同狀態(tài)(輕，重，平)，因此分成3堆是很常見(jiàn)的分法．36.【分析與解】韓信給兩人說(shuō)了一句話：“葫蘆歸簍，簍歸罐”，兩人按此分油，果然把油分成了兩半.具體做法以下表：韓信的話指明了倒油的方向，始終按從簍向罐中倒，從罐向葫蘆中倒，從葫蘆向簍中倒的方向操作.按攝影反的方向倒，即“葫蘆歸罐，罐歸簍”如何?我們?cè)囋?看來(lái)也行，只是多倒了一次.要注意的是：保持一定的方向很重要.如果在倒油的過(guò)程中，出現(xiàn)從甲倒向乙，又從乙倒回甲(這兩步不一定挨著)，那么這兩步互相抵消，必定能夠簡(jiǎn)化掉，因此最佳的倒油辦法是始終按一種方向倒?！痉治雠c解】先將5公斤的桶倒?jié)M油；再用大桶將小桶倒?jié)M，大桶中尚有5-4=1(公斤)油；然后將小桶倒空，將大桶中1公斤倒到小桶中；最后注滿大桶，連小桶中共是5+1=6(公斤)．這道題要學(xué)會(huì)借助于大桶小桶容積的差量出想獲得的中間量(1公斤)38.【分析與解】答案如表所示39.【分析與解】通過(guò)對(duì)三個(gè)數(shù)字的分析，我們發(fā)現(xiàn)700-300-300=100，是計(jì)算步數(shù)最少的得到100的辦法．而由于我們每計(jì)算一步就相稱于倒一次水，因此倒水最少的方案應(yīng)當(dāng)是：1．大瓶往中瓶中倒?jié)M水．2．中瓶往小瓶中倒?jié)M水，這時(shí)中瓶中還剩余400克水．3．小瓶中水倒回大瓶．4．中瓶再往小瓶中倒?jié)M水，這時(shí)中瓶中只剩余100克水，標(biāo)記．5．小瓶中水倒回大瓶．6．中瓶中100水倒入小瓶，標(biāo)記．因此最少要倒6次水．本題核心是，小瓶中的水每次都要倒掉，否則無(wú)法再往小瓶中倒水的40.【分析與解】大家開始嘗試多次之后可能會(huì)得出“不可能”的結(jié)論，但是大家不要無(wú)視一點(diǎn)，題中并沒(méi)規(guī)定所有折線只能限定在這9個(gè)點(diǎn)的范疇之內(nèi)．我們把折線的范疇沖破本題9個(gè)點(diǎn)所限定的正方形，那么問(wèn)題就容易解決了，如上右圖。41.【分析與解】不存在.當(dāng)1≤a≤6時(shí)，從a的位置順時(shí)針走a個(gè)數(shù)的位置，應(yīng)達(dá)成2a的位置；當(dāng)7≤a≤12時(shí)，從a的位置順時(shí)針走a個(gè)數(shù)的位置，應(yīng)達(dá)成2a-12的位置.由上面的分析知，不管a是什么數(shù)，成果總是走到偶數(shù)的位置，不會(huì)走到7的位置.42.【分析與解】同窗們碰到這種題，可能會(huì)“具體操作”一下，得到這個(gè)過(guò)程還能夠繼續(xù)下去，即使始終沒(méi)有得到100，但也不能必定得不到100.固然，持續(xù)操作下去會(huì)發(fā)現(xiàn)，數(shù)字一旦重復(fù)出現(xiàn)后，這一過(guò)程就進(jìn)入循環(huán)，這時(shí)就能夠必定不會(huì)出現(xiàn)100.由于這一過(guò)程很長(zhǎng)，因此這不是好辦法.由于231和121都是11的倍數(shù)，2不是11的倍數(shù)，因此在操作過(guò)程中產(chǎn)生的數(shù)也應(yīng)當(dāng)是11的倍數(shù).100不是11的倍數(shù)，因此不可能出現(xiàn).操作問(wèn)題不要一味地去“操作”，而要找到解決問(wèn)題的竅門.43.【分析與解】甲.如右下圖所示，將格點(diǎn)黑白相間染色，由于老鼠碰到格點(diǎn)必須轉(zhuǎn)彎，因此通過(guò)多少格點(diǎn)就轉(zhuǎn)了多少次彎。如左下圖所示，老鼠從黑點(diǎn)出發(fā)，達(dá)成任何一種黑點(diǎn)都轉(zhuǎn)了奇多次彎，因此甲對(duì)的.【分析與解】按圖中規(guī)定操作，圖3中陰影方格的數(shù)字之和與空白方格的數(shù)字之和的差不變.因此A=（1+1+1+1+1）-（0+0+0+0）=5.45.【分析與解】答案如表所示【分析與解】不能夠.如右下圖所示.守園人只能黑白相間地走，走到的第奇數(shù)棵樹是白的，第偶數(shù)棵樹是黑的，走到第48棵樹應(yīng)是黑的，而黑樹與小木屋不相鄰，無(wú)法直接回到小木屋?！痉治雠c解】這種覆蓋問(wèn)題是典型的用染色辦法解決的問(wèn)題之一．用來(lái)覆蓋，則用黑白相間染色，能夠發(fā)現(xiàn)它無(wú)論橫放、豎放，必然蓋住一白一黑．要不重復(fù)不留空白，那總共能蓋住的黑格數(shù)、白格數(shù)應(yīng)當(dāng)相等．但從染色后整個(gè)圖看，黑格30個(gè)，白格32個(gè)，故不可能將整個(gè)圖不重不漏地蓋住．48.【分析與解】將5升的容器裝滿水，倒在8升的容器中去，8升的容器中裝入了5升的水，再一次將5升的容器裝滿水，倒在8升的容