簡單中的豐富
——例談組合問題

●虞金龍 (紹興市第一中學 浙江紹興 312000)

簡單中的豐富
——例談組合問題

●虞金龍 (紹興市第一中學 浙江紹興 312000)

組合數學歷史悠久．早在幾千年前，我國的《河圖》、《洛書》中就已經涉及一些簡單有趣的組合問題了．組合問題看似簡單，這個在小學數學就出現的知識點一直在各級競賽中占有一席之地．組合問題中豐富的內涵，又經常令廣大數學愛好者折服．組合問題在開闊學生思路、培養靈活思維習慣方面起著重要作用．

本文例舉討論組合問題中的幾個常見模型，旨在拋磚引玉．

1 組合中的極值問題

例1平面上給定 n個點 A1，A2，…，An(n≥3)，任意3個點不共線．由其中的k個點對確定的k條直線(即過k個點對中的每一點對作一條直線)，使得這k條直線不相交成3個頂點都是給定點的三角形．求k的最大值．

分析設過點對A1，A2的直線為l，則點A1，A2不能同時與其余n－2個點中的任意一點連接，即過點A1或A2的直線至多只有n－1條(包括l)．同理，對 A3，A4，…，An這 n －2 個點而言，過 A3或 A4的直線至多只有n－3條，所以

例2將1到n2這n2個自然數隨機地排列在n×n的正方形方格內，其中n≥2．對于在同一行或同一列中的任一對數，計算較大數與較小數之比．這n2(n－1)個比值分數中的最小值，稱為這種隨機排列的“特征值”，求“特征值”的最大值．

其中a，b分別是這一行或這一列中的最大數，且a＞b．如果所有這n個大數在不同的行與列中，那么當它們中的一個數與n2－n在同一行或同一列中時，有

其中a為與n2－n在同一行和同一列中的2個最大數中的較小的一個．對于排列

在第 j=2，3，…，n －1 列，從小到大排列為:j－1，j－2+n，j－3+2n，…，1+(j－2)n，n+(j－1)n，…，j+(n－1)n．其中前j－1項為公差為 d=n－1的等差數列，后n－j+1項仍為公差為d=n－1的等差數列，第j項與第j－1項的差為2n－1，于是

當j=n－1時，最后一個等號成立．

在第n列，當n≥3時，

例3在7×7個方格的正方形中，作出其中m個正方形的中心，使這m個點中的任意4個點都不能構成邊與網線平行的矩形，求m的最大值．

分析假設在7×7個方格的正方形中，已作出m個正方形的中心點且滿足題目要求，其中第i行有xi個中心點，則

按已知，如果在某行已作出2個點，那么在其余的每行中都不能再標出具有相同橫坐標的2個點，這意味著正方形中所有的同行兩點組的橫坐標對互不相同．由于方格的橫坐標有7個不同的值，因此不同的橫坐標對共有=21個，從而

圖1

即至多可作出21個方格的中心滿足條件．

當m=21時，構造如圖1所示的排列方法可以滿足條件，故m的最大值為21．

2 組合中的構造問題

例4能否將正整數集合N*分劃為2個不相交的集合A和B，使得

(1)A中任意3個數不成等差數列;

(2)不能有B中的元素組成一個非常數的無窮等差數列．

將A中的數從小到大排列，從第2項起，每一項大于前一項的2倍，因此A中任意3個數不成等差數列，其次B中沒有非常數的無窮等差數列．

假設有{a+nd}(n=0，1，2，…)是 B 中一個非常數的等差數列，這里 a，d∈N*．由A的構造可知，存在無窮多個m∈N*，使得m!+a∈A，故存在m≥d，使得 m!+a∈A．令 n=，則 m!+0a=a+n0d∈A，這與對任意 n∈N*，a+nd∈B 矛盾．

可見，存在滿足條件(1)，(2)的集合A，B．

例5設k為給定的正整數，試求最小正整數n，使得對任意n個整數，其中總存在2個整數，它們的和或差被2k整除．

分析設a1，a2，…，an為任意 n個整數，它們被 2k 除的余數依次為 r1，r2，…，rn，于是 ri∈{0，1，2，…，2k－1}，將 2k 個數的集合{0，1，2，…，2k －1}分為下列兩數和能被2k整除(只有一個數的組，同數相加或相減)的k+1組:

于是當n≥k+2時，根據抽屜原理，n個整數r1，r2，…，rn中必有 2 個數 ri，rj(1≤i＜j≤n)屬于同一組，它們之和或差被2k整除，從而ai與aj的和或差被2k整除，故所求的最小正整數n≤k+2．

另一方面，取下列 k+1 個整數:0，1，2，…，k，它們中任意2個數之和在1與2k－1之間，任意2個數之差在－k與k之間并且不為0，這些和與差不能被2k整除，因此最小的正整數n≥k+2．

綜上得所求的最小正整數n=k+2．

3 組合中的覆蓋問題

例6在100×100的方格棋盤上放置著800個T形塊，每個這樣的圖形恰好蓋住棋盤上的4個方格，且任何2個圖形都不重疊，求證:在棋盤上還可以再放置1個這樣的圖形，使它完全蓋住4個空方格．

圖2

圖3

分析將圖2中陰影方格稱為中心方格，假設在棋盤上已經放好1個T圖形，這個T圖形與其周圍的8個方格如圖3所示．如果棋盤上再放置一個T圖形，且其中心格不在圖3所示的12個方格中，則后放入的T圖形與原來的T圖形不相互重疊．另一方面，若放入的T圖形的中心格不在棋盤四周的邊格中，則此圖形不會超出棋盤之外．由于棋盤內部共有98×98個方格，而982－12×800=4，故知還可以再放入1個T形圖，使得它與已有的T圖形不相互重疊．

例7能否用如圖4所示的9塊“田字型”方塊和7塊“L型”的模塊把國際象棋盤覆蓋?

圖4

分析國際象棋盤是8×8的64個方格，將奇數列的每一個小方格內賦值1，偶數列的每一小方格內賦值－1，于是每塊田字形塊蓋住的方格內的數字之總和為0;而L形模塊蓋住的方格內的數字之和為3+(－1)=2或1+3×(－1)= －2，設L形中的x塊蓋住數字和為2，7－x塊蓋住的數字之和為－2．如果滿足題目條件的覆蓋存在，那么蓋住的各小格內的數字總和應為

另一方面，8×8的棋盤上各小格內的數字之和應為32×1+32×(－1)=0，因此4x－14=0，得 x=?Z，矛盾．故滿足題設的覆蓋是不存在的．

4 組合中的計數問題

例8設 n≥2，S={1，2，…，n}，對于每個 1≤k≤n，記xk是S的所有k元子集合的最小元素的和，試求

因此，只要考慮n作為最小元素在和中的貢獻．顯然以n為最小元的集合只有一元集合{n}，從而n在所求和中的貢獻為n，故所求的值是n．

例9某次經貿洽談會共有12m(m∈N*)個單位參加，其中每個單位都恰好同其余3m+6個單位簽過合同．對任何2個單位，同這2個單位簽過合同的單位數是相同的．問共有多少個單位參加這次經貿洽談會?

1 2 3 4 5 6 6 1 2 3 4 5 5 6 1 2 3 4 4 5 6 1 2 3 3 4 5 6 1 2 2 3 4 5 6 1

用1，2，3，4，5，6 表示 6 種顏色，將單位染色，按上表排列，每單位恰好與它同行或同列或與它具有相同顏色的單位簽約，這樣保證每個單位恰與15個單位簽約，只需再證這種構造滿足第2個條件即可．設P，Q是任意2個單位，若他們坐在同一行，則與這2單位簽約的單位有這一行的其余4個單位及位于P所在列與Q同色的單位和位于Q所在列與P同色的單位，則2個單位共同簽約的6個單位分別是:位于P所在的行和Q所在的列的1個單位(與P，Q均不同色)、位于P所在列和Q所在的行的1個單位、位于P所在行和列且與Q同色的2個單位、位于Q所在行和列且與P同色的2個單位．

5 組合中的操作問題

例10任意地將數1，2，…，n寫在一個圓周上．允許每一次交換相鄰的位置，只要這2個數之差的絕對值大于1，試證經過若干次這樣的交換之后，可以使得所有數按自然順序排列在圓周上．

分析規定順時針方向為正向．首先，可以交換1與其他數的位置，使得1與2相鄰且1排在前面，然后將2按順時針方向交換并前進，直到與3相鄰，接著再將1與其他數交換，使之與2相鄰，從而得到1，2，3按順時針方向排好，再用3倍的交換步驟，依次使3與4，2與3，1與2靠攏，于是1，2，3，4已經排好．這樣繼續下去，最后便可使全部各數都按正方向排好，顯然，反方向排列同樣也可以操作成功．

例11國際象棋盤有32個黑格與32個白格，每次操作把位于內部的2×2正方形的每個方格改變成另外的顏色，問能否通過若干次操作使得棋盤里恰好剩下一個白色的方格?

分析8×8國際象棋盤中有32個黑格與32個白格，規定給每個黑色的格子賦值1，給每個白色的格子賦值－1，初始狀態有32個1和32個－1，它們的乘積為

每次操作改變2×2=4個方格的顏色，相當于把4個方格的數值改變符號，對于64個格子的數值乘積S而言，每次操作相當于乘以(－1)4．如果先后共進行了k次操作，k次操作后格子中數值的乘積為不可能為163×(－1)，因此無論通過多少次操作不可能使得棋盤里恰好剩下一個白色的方格．

例12在黑板上寫上3個整數，然后將其中一個擦去，換上其他2個數之和與1的差．將這個過程重復若干次之后得到(17，1 999，2 015)，則這3個數的初始值能否是

(1)(2，2，2);

(2)(3，3，3)．

分析由于3個數在題述的操作過程中奇偶性的變化關系為(偶，偶，偶)→(偶，偶，奇)→(偶，偶，奇)，因此(2，2，2)無法經過若干次操作達到(17，1 999，2 015)．

若(奇，奇，奇)→(奇，奇，奇)→(奇，奇，奇)，則(3，3，3)有可能是操作過程的初始值．

若先考慮(3，3，3)經過若干次變化后達到(17，a，b)(17 ＜a ＜b)，則

顯然2 015=1 999+16也滿足．

固定17，選擇盡可能小的 a＞17，使得(17，a，a+16)經過若干次調整操作能達到(17，1 999，2 015)．對(17，a，a+16)，若擦去 a+16，則操作后仍為自己不動，故應考慮擦去a，此時經操作后得(17，a+16，a+2 ×16)．再擦去 a+16，經操作后得

經過n次操作可得

由于1 999=31+123×16，因此若取 a=31，則(17，31，47)需要123次擦去中間數的操作可達(17，1 999，2 015)．

又因為由遞推:(17，31，47)←(15，17，31)←(3，15，17)←(3，13，15)←(3，11，13)←(3，9，11)←(3，7，9)←(3，5，7)←(3，3，5)←(3，3，3)，知(17，31，47)可由(3，3，3)經過 9 次操作達到，所以(17，1 999，2 015)可由(3，3，3)經過 123+9=132次操作達到．

數學競賽中出現的組合問題，其表達形式往往簡單、明了，而求解它們卻需要敏銳的觀察力、豐富的想象力和必要的技巧，通常沒有一定的模式可循，而且各種難易程度的問題都非常豐富．因此各種程度的智力訓練和數學競賽中，大多離不開組合問題．