棋盤上的數學競賽

這里所說的棋盤，并非都是現實生活中真實的棋盤，而是泛指各種矩形方格表.數學競賽中有很多與方格表有關的問題，這類問題大多非常有趣又有一定的難度，這倒不是說解決它需要多么高深、專門的數學知識，恰恰相反，它用到的都是些我們司空見慣的非常淺顯的道理，如：奇偶分析、抽屜原理等.正因如此，常常使那些習慣了套用定理、公式者感到束手無策.事實上，這類問題主要考察你的數學機智，只要我們能擺脫固有的思維方式的束縛，做到隨機應變，很多問題三兩句話就可以干脆利索地解決了．

例1 圖1表示16間陳列室，凡鄰室(有公共邊的方格)都有門相通，一游客從A進入，他想每室都參觀一次且只參觀一次，最后從B室出來，這種路線是否存在？

分析 表面看來，似乎游客的愿望是可以實現的，但試驗幾次就會動搖最初的想法，可要證明滿足要求的路線不存在，又幾乎沒有可供運算的數據，所以我們必須認真分析參觀規則和16的奇偶性，很可能它就與16的奇偶性有關．

解 這種路線不存在．

如圖2，將陳列室染色，顯然，游客每次只能

由白室進入黑室或由黑室進入白室.由于第一次進入的是白室，從而他第奇數次進入的一定是白室，而第偶數次進入的是一定是黑室，所以，如果滿足要求的線路存在，那么這位游客第16次進入的一定是黑室，而不可能是B室，從而滿足要求的線路是不存在的．

例2 設有2n×2n的正方形方格棋盤，在其中任意3n個方格中各放一枚棋子.求證：可以選出n行n列，使得3n枚棋子都在這n行n列中(1990年全國初中數學聯賽試題)．

分析 要想使選出的n行n列能夠滿足要求，只要我們能使選出的n行(或列)中的棋子不少于2n就可以了，而要想使選出的n行(或列)中的棋子盡可能的多，我們必須選出棋子數較多的n行，所以我們只需證明這n行的棋子數不少于2n即可．

解 把各行的棋子數由多到少排列如下：p1≥p2≥p3≥…≥p2n.顯然前n行的棋子總數不少于后n行的棋子總數，只需證明前n行的棋子總數不少于2n即可．

假定前n行的棋子總數少于2n，則必有pn≥1，從而pn+1≥1，后n行的棋子總數不超過n，從而所有的棋子總數少于3n，矛盾．

選出棋子數較多的n行，這n行中的棋子至少有2n個，至多還有n個棋子不在這n行中，這些棋子至多分布在n列中，故必能選出n列，使這些剩余的棋子全部在這n列中．

例3 在中國象棋的棋盤上有一只馬，這只馬能否經過20112011步的跳躍之后，回到原來的出發點？

分析 20112011這個數字大得我們難以想象，經驗告訴我們，回不到出發點的可能性很大.遇到這種問題，一般我們都先考慮最簡單的情況，稍稍嘗試一下便會發現：經過1步、3步不能回到出發點，但經過2步和4步時可以回到出發點(沿原路返回就可以了)，至此，我們可以大膽猜想：這只馬經過奇數步回不到出發點，經過偶數步可以回到出發點.既然能不能回到出發點跟數的奇偶性有關，那么我們就從分析奇偶性開始．

解 設馬的出發點坐標為(a，b)，由中國象棋的規則可知，這只馬下一步的落點坐標只可能是(a+1， b+2)， (a+1 ，b-2)，(a+2， b+1)， (a+2， b-1)， (a-1， b+2)((a-1， (b-2)， (a-2，b+1)，(a-2，b-1)，顯然這8個點中每個點的坐標和都和出發點的坐標和的奇偶性相反，不妨把坐標和為奇數的點稱為奇點，坐標和為偶數的點稱為偶點，那么由以上的分析可知，馬每一步只能由奇點跳到偶點，或由偶點跳到奇點，故在經過奇數步的跳躍之后，馬的落點坐標和一定與a+b的奇偶性相反，而20112011是奇數，所以這只馬無論如何也回不到出發點． --!>

例3 將1990×1990的方格表中的每個單位方格都染成黑色或白色，使得關于方格表中心對稱的每兩個單位方格的顏色都不相同，試問：是否可以染得每一行每一列的黑色方格和白色方格都相等(第24屆全蘇數學奧林匹克試題)

分析 方格表中的單位方格實在太多，也幾乎沒有可供運算的數據，先取特殊值嘗試就會發現情況比較復雜，有時候染法存在，有時候又不存在(2×2的方格表不存在滿足要求的染法，但4×4的方格表存在滿足要求的染法)，難以理出頭緒，可見能否染成一定與1990這個數字有關!讓我們仔細研究一下題目條件，先把它轉化成一個明確的數學問題．

由于要染的顏色只有兩種，故我們可以用1和-1來表示，通過計算數值來判斷是否存在滿足要求的染法．

解 如圖3，假定O為1990×1990的方格表的對稱中心，白格用1表示，黑格用-1表示.假定995×995的方格表A中所有的單位方格的和為a，同樣大小的方格表B、C中所有單位方格的和分別為b、c，顯然A中的每一個單位方格關于O的對稱方格都在C中，而C中的每一個單位方格關于O的對稱方格也都在A中，故若存在滿足要求的染法，則必有a+b=0，a+c=0，b+c=0，從而a=b=c=0，這說明A、B、C中的單位方格都有一半為黑，一半為白，從而A、B、C中的單位方格數都是偶數，但995×995是奇數，矛盾!故滿足要求的染法是不存在的．

例4 一個4×7的矩形棋盤，每個單位方格均被涂上白色或黑色.證明：對于任何一種涂法，棋盤上必有一個矩形，它的四個角上的單位方格顏色相同(美國數學奧林匹克試題)

分析 由于涂色方法是任意的，所以矩形棋盤上的方格的顏色也就毫無規律可言，企圖直接找出來一個滿足要求的矩形是不明智的，也是不可能的.怎么辦呢？一般的方法是，先從分析某一行(或列)中的某種顏色的方格開始，然后利用抽屜原理，步步推進，直到最后得出要證明的結論．

證明 假定該棋盤有4行7列．

由抽屜原理可知，第1列至少有兩個某種顏色的單位方格，無妨設為白格．

若其余6列每列也至少有兩個白格，因C24=6，故7列中必有兩列中的白格分別位于相同的行中，命題成立，排除這種情況．

假定其余6列中有一列至多有一個白格，無妨設為第7列，則該列至少有3個黑格.若其余6列中有一列至少也有3個黑格，則命題成立，排除這種情況.假定其余6列中每列至多有2個黑格，則這6列中每列至少有2個白格.若這6列中某一列有3個白格，顯然存在一個四個角都是白格的矩形；若這6列中每一列都恰有2個白格，那么這6列中每一列也恰有2個黑格，由于第7列有三個黑格，從而一定存在一個四個角都是黑格的矩形.

例5 給定兩張3×3的方格紙，并且在每一個方格內填上“+”或“-”號，現在對方格紙中任何一行或一列作全部變號的操作，問可否經過若干次操作，使圖4變成圖5？

分析 由于方格中的符號只有兩種，所以每個符號經過偶數次變換后仍是原來的符號，而經過奇數次變換后就變成了相反的符號，可見圖5中的符號只跟圖4中相同位置的符號的變換次數的奇偶性有關，而圖5中每個符號變換的次數等于它在圖4中所處的的行和列變換的次數之和，要證明圖4不能變成圖5，我們只需證明圖5中的某些符號不能由圖4中對應的符號變換得到即可．

解 我們用aij表示圖4中第i行第j列交叉處的符號，bij表示圖5中第i行第j列交叉處的符號(方格表自上而下分別記為第一、二、三行，自左至右分別記為第一、二、三列) ．

假定b11的符號是由a11所在的行、列分別變化了a、b次得到的，b12的符號是由a12所在的行、列分別變化了a、c次得到的，b21的符號是由a21所在的行、列分別變化了d、b次得到的，b22的符號是由a22所在的行、列分別變化了d、c次得到的，則a+b必為奇數，a+c必為奇數，d+b必為偶數，d+c必為奇數，故a+b+a+c=2a+b+c必為偶數，從而b+c必為偶數；另一方面，d+b+d+c=2d+b+c必為奇數，從而b+c必為奇數，矛盾，故不論經過多少次操作，也無法使圖4變成圖5．

例6 在8×8的棋盤的左下角放有9枚棋子，組成一個3×3的正方形(圖6)，假定每枚棋子可以以它旁邊的棋子為中心作對稱運動，可以橫跳、豎跳或沿著斜線跳(圖7中的1號棋子可以跳到2、3、4號位置)，問：這些棋子能否跳到棋盤右上角3×3的正方形中？

分析 要證明的不是一個明確的結論，而且要移動的棋子也太多，所以嘗試著移動幾步就會發現，要把左下角的9枚棋子全部移到右上角是非常困難的，這提示我們結論很可能是否定的，不應再花費時間和精力去進行無謂的嘗試了，而應把注意力放在對移動規則的分析上，特別是前后步之間的位置關系，答案很可能就在這里．

解 不能．

將方格所在的列自左至右分別記為第1，2，…，8列，由棋子的跳躍規則可知，每次跳躍后它所在列的奇偶性不變，故不論跳躍多少次，原來位于奇數列中的棋子仍然位于奇數列中，由于最初位于奇數列中的棋子有6枚，但右上角的奇數列中的空格只有3個，故無論跳躍多少次，

左下角的棋子也不可能全部跳到右上角．

例7 兩人輪流在101×101的方格表中擺放棋子，每人每次擺放一枚棋子(不能不擺，且每個方格只能擺放一枚棋子)，先放者可以把棋子放在任何一個這樣的空格中：該格所在的行與列中已擺放的棋子總數為偶數，后放者則可以把棋子放在任何一個這樣的空格中：該格所在行與列中已擺放的棋子總數為奇數，誰不能再放棋子就算誰輸.試問：誰有取勝策略，先放者還是后放者？(1996年圣彼得堡數學奧林匹克試題)

分析 直覺地想來，先放者獲勝的可能性較大，因為他有充分的選擇余地，可以搶占先機，但若處置不當，也可能輸掉比賽，怎么辦？先放者要想獲勝，他必須保證只要后放者有處放，他就一定有處放，由于101×101是奇數，故最后一個擺放棋子的一定是先放者．

解 我們用甲、乙表示兩人.由比賽的規則可知，先放的有取勝策略．

我們首先證明一個結論：先放者甲每次擺放棋子后都能使所有有棋子的行和列中的棋子數都是奇數.顯然，甲第一次擺放后結論成立.假定甲第p次擺放后結論成立，那么按照規則，所有有棋子的行和有棋子的列交叉處的空格乙都不能填，從而乙只能在有棋子的行與無棋子的列的交叉處的空格里放棋子，這樣只有這一行的棋子數為偶數，其他各行和所有的列中的棋子數都是奇數，由于輪流擺放，故在乙擺放后棋子總數為偶數，又因為所有的列中的棋子數為奇數，故有棋子的列數必為偶數，從而必有一列沒有棋子，第p+1次甲只需在該列與棋子數為偶數的行交叉處的空格里放上一個棋子，則所有有棋子的行和列中的棋子數都變成了奇數，從而只要乙有處放，甲必有處可放，但顯然不能無限放下去，當各行各列都有棋子時，乙就無處可放了，從而必輸無疑．

例9 在7×7的方格表的64個網格線的交點(稱為結點)處放棋子，每點至多放1枚，一共放了k枚棋子，若無論怎樣放，總存在4枚棋子，它們所在的結點構成一個矩形(矩形的邊平行于棋盤的網格線)的四個頂點，試求k的最小值(第6屆北方數學奧林匹克試題)

圖8分析 本題難就難在要證明的不是一個明確的結論，所以我們必須首先大體確定出這個最小值，然后再設法證明.如何確定呢？我們可以反過來考慮，先確定出盡可能多的點不能保證出現滿足要求的矩形的情形，這樣我們就可以大體上確定出k的最小值了.顯然8個點是不行的，16個點也是不行的，我們再試試24個點的情形，經過嘗試，24個點也不行，如圖8，那么25個點可不可以呢？我們在圖8的任一個沒有棋子的結點上放一個棋子，都有滿足條件的矩形出現，這說明25很可能就是k的最小值，下面我們來證明這個結論．

解 網格線自上而下分別記為第1行，第2行，…，第8行，自左至右分別記為第1列，第2列，…，第8列，用aij表示位于第i行和第j列交叉處的結點.以下證明k的最小值為25．

由抽屜原理可知，必有一行至少放了4枚棋子，不失一般性，無妨令第1行放的棋子最多，假如放了8枚棋子，那么要想沒有滿足條件的矩形出現，第2行到第8行每行只能放一枚棋子，棋盤總共只能放15枚棋子，矛盾，故這種情況下結論成立．

同理可證，若第1行有7枚棋子，結論同樣成立．

若第1行有6枚棋子，無妨令a11，a12，…，a16(下同)有棋子，要想沒有滿足條件的矩形出現，則以a21，a81，a86，a26為頂點的矩形內(含邊，下同)每行的結點處只能放1枚棋子，從而以a11，a81，a86，a16為頂點的矩形內的結點處的棋子至多有13枚，那么易知以a27，a87，a88，a28為頂點的矩形內的結點必須放12枚棋子，結論顯然成立．

若第1行放5枚棋子，由前面的討論可知，要想沒有滿足條件的矩形出現，則以a26，a86，

a88，a28為頂點的矩形內的結點處必須放13枚棋子，故第6、7、8列中必有一列至少放了5枚棋子，無妨令第6列放的棋子最多，若該列放了6枚或7枚棋子，結論顯然成立，若該列恰放了5枚棋子，無妨令a26，a36，…，a66處放了棋子，那么要想沒有滿足條件的矩形出現，a27，a37，…，a67中只能有一個結點處有棋子，a28，a38，…，a68也只能有一個結點處有棋子，從而a77，a78，a87，a88這4個結點處必須放6枚棋子，矛盾，故結論成立．

若第1行有4枚棋子，那么以a25，a85，a88，a28為頂點的矩形內的結點處必須放置14枚棋子，所以第5、6、7、8列中必有一列至少放了4枚棋子.無妨令第5列放的棋子最多，若該列至少放了5枚棋子，則易知結論成立，假定恰有4枚棋子，無妨令a25，a35，a45，a55處放了棋子，那么要想沒有滿足條件的矩形出現，則以a66，a86，a88，a68為頂點的矩形內的結點處必須放置7枚棋子，顯然無論這7枚棋子怎樣放置，都有滿足條件的矩形，故k的最小值為25． --!>

作者簡介 向中軍，男，河南省方城縣人，中學高級教師，主要從事數學奧林匹克研究，發表論文數十篇．