轉《數學奧林匹克專題講座》七(2009-01-31 12:37:41)
第12講染色和賦值
染色方法和賦值方法是解答數學競賽問題的兩種常用的方法。就其本質而言，染色方法是一種對題目所研究的物件進行分類的一種形象化的方法。而凡是能用染色方法來解的題，一般地都可以用賦值方法來解，只需將染成某一種顏色的物件換成賦於其某一數值就行了。
賦值方法的適用範圍要更廣泛一些，我們可將題目所研究的物件賦於適當的數值，然後利用這些數值的大小、正負、奇偶以及相互之間運算結果等來進行推證。
一、染色法
將問題中的物件適當進行染色，有利於我們觀察、分析物件之間的關係。像西洋棋的棋盤那樣，我們可以把被研究的物件染上不同的顏色，許多隱藏的關係會變得明朗，再通過對染色圖形的處理達到對原問題的解決，這種解題方法稱為染色法。常見的染色方式有：
點染色、線段染色、小方格染色和對區域染色。
例1 用15個「t」字形紙片和1個「田」字形紙片（如下圖所示），能否覆蓋乙個8×8的棋盤？
解：如下圖，將 8×8的棋盤染成黑白相間的形狀。如果15個「t」字形紙片和1個「田」字形紙片能夠覆蓋乙個8×8的棋盤，那麼它們覆蓋住的白格數和黑格數都應該是32個，但是每個「t」字形紙片只能覆蓋1個或3個白格，而1和3都是奇數，因此15個「t」字形紙片覆蓋的白格數是乙個奇數；又每個「田」字形紙片一定覆蓋2個白格，從而15個「t」字形紙片與1個「田」字形紙片所覆蓋的白格數是奇數，這與32是偶數矛盾，因此，用它們不能覆蓋整個棋盤。
例2 如左下圖，把正方體分割成27個相等的小正方體，在中心的那個小正方體中有乙隻甲蟲，甲蟲能從每個小正方體走到與這個正方體相鄰的6個小正方體中的任何乙個中去。如果要求甲蟲只能走到每個小正方體一次，那麼甲蟲能走遍所有的正方體嗎？
解：甲蟲不能走遍所有的正方體。我們如右上圖將正方體分割成27個小正方體，塗上黑白相間的兩種顏色，使得中心的小正方體染成白色，再使兩個相鄰的小正方體染上不同的顏色。
顯然，在27個小正方體中，14個是黑的，13個是白的。甲蟲從中間的白色小正方體出發，每走一步，方格就改變一種顏色。故它走27步，應該經過14個白色的小正方體、13個黑色的小正方體。
因此在27步中至少有乙個小正方體，甲蟲進去過兩次。由此可見，如果要求甲蟲到每乙個小正方體只去一次，那麼甲蟲不能走遍所有的小正方體。
例3 8×8的西洋棋棋盤能不能被剪成7個2×2的正方形和9個4×1的長方形？如果可以，請給出一種剪法；如果不行，請說明理由。
解：如下圖，對8×8的棋盤染色，則每乙個4×1的長方形能蓋住2白2黑小方格，每乙個2×2的正方形能蓋住1白3黑或3白1黑小方格。推知7個正方形蓋住的黑格總數是乙個奇數，但圖中的黑格數為32，是乙個偶數，故這種剪法是不存在的。
例4 在平面上有乙個27×27的方格棋盤，在棋盤的正中間擺好81枚棋子，它們被擺成乙個9×9的正方形。按下面的規則進行遊戲：每一枚棋子都可沿水平方向或豎直方向越過相鄰的棋子，放進緊挨著這枚棋子的空格中，並把越過的這枚棋子取出來。
問：是否存在一種走法，使棋盤上最後恰好剩下一枚棋子？
解：如下圖，將整個棋盤的每一格都分別染上紅、白、黑三種顏色，這種染色方式將棋盤按顏色分成了三個部分。按照遊戲規則，每走一步，有兩部分中的棋子數各減少了乙個，而第三部分的棋子數增加了乙個。
這表明每走一步，每個部分的棋子數的奇偶性都要改變。
因為一開始時，81個棋子擺成乙個9×9的正方形，顯然三個部分的棋子數是相同的，故每走一步，三部分中的棋子數的奇偶性是一致的。
如果在走了若干步以後，棋盤上恰好剩下一枚棋子，則兩部分上的棋子數為偶數，而另一部分的棋子數為奇數，這種結局是不可能的，即不存在一種走法，使棋盤上最後恰好剩下一枚棋子。
例5 圖1是由數字0，1交替構成的，圖2是由圖1中任選減1，如此反覆多次形成的。問：圖2中的a格上的數字是多少？
解：如左下圖所示，將8×8方格黑白交替地染色。
此題允許右上圖所示的6個操作，這6個操作無論實行在哪個位置上，白格中的數字之和減去黑格中的數字之和總是常數。所以圖1中白格中的數字之和減去黑格中的數字之和，與圖2中白格中的數字之和減去黑格中的數字之和相等，都等於32，由（31＋a）-32=32，得出a=33。
例6 有一批商品，每件都是長方體形狀，尺寸是1×2×4。現在有一批現成的木箱，內空尺寸是6×6×6。問：能不能用這些商品將木箱填滿？
解：我們用染色法來解決這個問題。先將6×6×6的木箱分成216個小正方體，這216個小正方體，可以組成27個稜長為2的正方體。
我們將這些稜長為2的正方體按黑白相間塗上顏色（如下圖）。
容易計算出，有14個黑色的，有13個白色的。現在將商品放入木箱內，不管怎麼放，每件商品要佔據8個稜長為1的小正方體的空間，而且其中黑、白色的必須各佔據4個。現在白色的小正方體共有8×13=104（個），再配上104個黑色的小正方體，一共可以放26件商品，這時木箱餘下的是8個黑色小正方體所佔據的空間。
這8個黑色的小正方體的體積雖然與一件商品的體積相等，但是容不下這件商品。因此不能用這些商品剛好填滿。
例7 6個人參加乙個集會，每兩個人或者互相認識或者互相不認識。證明：存在兩個「三人組」，在每乙個「三人組」中的三個人，或者互相認識，或者互相不認識（這兩個「三人組」可以有公共成員）。
證明：將每個人用乙個點表示，如果兩人認識就在相應的兩個點之間連一條紅色線段，否則就連一條藍色線段。本題即是要證明在所得的圖中存在兩個同色的三角形。
設這六個點為a，b，c，d，e，f。我們先證明存在乙個同色的三角形：
考慮由a點引出的五條線段ab，ac，ad，ae，af，其中必然有三條被染成了相同的顏色，不妨設ab，ac，ad同為紅色。再考慮△bcd的三邊：若其中有一條是紅色，則存在乙個紅色三角形；若這三條都不是紅色，則存在乙個藍色三角形。
下面再來證明有兩個同色三角形：不妨設△abc的三條邊都是紅色的。若△def也是三邊同為紅色的，則顯然就有兩個同色三角形；若△def三邊中有一條邊為藍色，設其為de，再考慮da，db，dc三條線段：
若其中有兩條為紅色，則顯然有乙個紅色三角形；若其中有兩條是藍色的，則設其為da，db。此時在ea，eb中若有一邊為藍色，則存在乙個藍色三角形；而若兩邊都是紅色，則又存在乙個紅色三角形。
故不論如何塗色，總可以找到兩個同色的三角形。
二、賦值法
將問題中的某些物件用適當的數表示之後，再進行運算、推理、解題的方法叫做賦值法。許多組合問題和非傳統的數論問題常用此法求解。常見的賦值方式有：
對點賦值、對線段賦值、對區域賦值及對其他物件賦值。
例8 一群旅遊者，從a村走到b村，路線如下圖所示。怎樣走才能在最短時間內到達b村？圖中的數字表示走這一段路程需要的時間（單位：分）。
解：我們先把從a村到各村的最短時間標註在各村的旁邊，從左到右，一一標註，如下圖所示。
由此不難看出，按圖中的粗黑線走就能在最短時間（60分鐘）內從a村走到b村。
例9 把下圖中的圓圈任意塗上紅色或藍色。問：有無可能使得在同一條直線上的紅圈數都是奇數？請說明理由。
解：假設題中所設想的染色方案能夠實現，那麼每條直線上代表各點的數字之和便應都是奇數。一共有五條直線，把這五條直線上代表各點的數字之和的這五個奇數再加起來，得到的總和數仍應是乙個奇數。
但是，由觀察可見，圖中每個點都恰好同時位於兩條直線上，在求上述總和數時，代表各點的數字都恰被加過兩次，所以這個總和應是乙個偶數。這就導致矛盾，說明假設不成立，染色方案不能實現。
例10 平面上n（n≥2）個點a1，a2，…，an順次排在同一條直線上，每點塗上黑白兩色中的某一種顏色。已知a1和an塗上的顏色不同。證明：
相鄰兩點間連線的線段中，其兩端點不同色的線段的條數必為奇數。
證明：賦予黑點以整數值1，白點以整數值2，點ai以整數
值為ai，當ai為黑點時，ai=1，當ai為白點時，ai=2。再賦予線段aiai+1以整數值ai+ai+1，則兩端同色的線段具有的整數值為2或4，兩端異色的線段具有的整數值為3。
所有線段對應的整數值的總和為
（a1＋a2）＋（a2＋a3）＋（a3＋a4）＋…＋（an-1＋an）
＝a1＋an＋2（a2＋a3＋…＋an-1）
＝2＋1＋2（a2＋a3＋…＋an-1）＝奇數。
設具有整數值2，3，4的線段的條數依次為l，m，n，則
2l＋m＋4n=奇數。
由上式推知，m必為奇數，證明完畢。
例11 下面的表1是乙個電子顯示盤，每一次操作可以使某一行四個字母同時改變，或者使某一列四個字母同時改變。改變的規則是按照英文本母的順序，每個英文本母變成它的下乙個字母（即a變成b，b變成c……z變成a）。問：
能否經過若干次操作，使表1變為表2？如果能，請寫出變化過程，如果不能，請說明理由。
s o b r k b d s
t z f p h e x g
h o c n r t b s
a d v x c f y a
表1 表2
解：不能。將表中的英文本母分別用它們在字母表中的序號代替（即a用1，b用2……z用26代替）。這樣表1和表2就分別變成了表3和表4。
每一次操作中字母的置換相當於下面的置換：
1→2，2→3，…，25→26，26→1。
19 15 2 18
20 26 6 16
8 15 3 14
1 4 22 24
表311 2 4 19
8 5 24 7
18 20 2 19
3 6 25 1
表4容易看出，每次操作使四個數字改變了奇偶性，而16個數字的和的奇偶性沒有改變。因為表3中16個數字的和為213，表4中16個數字的和為174，它們的奇偶性不同，所以表3不能變成表4，即表1不能變成表2。
例12 如圖（1）～（6）所示的六種圖形拼成右下圖，如果圖（1）必須放在右下圖的中間一列，應如何拼？
解：把右上圖黑、白相間染色（見上圖）。其中有11個白格和10個黑格，當圖形拼成後，圖形（2）（4）（5）（6）一定是黑、白各2格，而圖形（3）必須有3格是同一種顏色，另一種顏色1格。
因為前四種圖形，黑、白已各佔2×4=8（格），而黑格總共只有10格，所以圖形（3）只能是3白1黑。由此知道圖（1）一定在中間一列的黑格，而上面的黑格不可能，所以圖（1）在中間一列下面的黑格中。
數學奧林匹克專題講座第01講數論的方法技巧上
數學奧林匹克專題講座 第1講 數論的方法技巧 上 數論是研究整數性質的乙個數學分支，它歷史悠久，而且有著強大的生命力。數論問題敘述簡明，很多數論問題可以從經驗中歸納出來，並且僅用三言兩語就能向乙個行外人解釋清楚，但要證明它卻遠非易事 因而有人說 用以發現天才，在初等數學中再也沒有比數論更好的課程了。...
2023年小學數學奧林匹克預賽試卷
1 計算 8 1.2 1.5 742 2.544 2.4 2 計算 3 已知，那麼x 4 設表示，計算 5 圖中大長方形分別由面積為12平方厘公尺 24平方厘公尺 36平方厘公尺 48平方厘公尺的四個小長方形組成，那麼圖中的陰影面積為 6 按英國人的記法，2005年1月8日記作1 8 2005 按美...
高中數學奧林匹克競賽講座 04平面幾何證明
競賽專題講座04 平面幾何證明 競賽知識點撥 1 線段或角相等的證明 1 利用全等 或相似多邊形 2 利用等腰 3 利用平行四邊形 4 利用等量代換 5 利用平行線的性質或利用比例關係 6 利用圓中的等量關係等。2 線段或角的和差倍分的證明 1 轉化為相等問題。如要證明a b c，可以先作出線段p ...