第四十六章染色和覆蓋問題

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