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

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

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

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

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

1 組合中的極值問題

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

分析設(shè)過點對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個自然數(shù)隨機(jī)地排列在n×n的正方形方格內(nèi)，其中n≥2．對于在同一行或同一列中的任一對數(shù)，計算較大數(shù)與較小數(shù)之比．這n2(n－1)個比值分?jǐn)?shù)中的最小值，稱為這種隨機(jī)排列的“特征值”，求“特征值”的最大值．

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

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

在第 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的等差數(shù)列，后n－j+1項仍為公差為d=n－1的等差數(shù)列，第j項與第j－1項的差為2n－1，于是

當(dāng)j=n－1時，最后一個等號成立．

在第n列，當(dāng)n≥3時，

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

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

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

圖1

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

當(dāng)m=21時，構(gòu)造如圖1所示的排列方法可以滿足條件，故m的最大值為21．

2 組合中的構(gòu)造問題

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

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

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

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

假設(shè)有{a+nd}(n=0，1，2，…)是 B 中一個非常數(shù)的等差數(shù)列，這里 a，d∈N*．由A的構(gòu)造可知，存在無窮多個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設(shè)k為給定的正整數(shù)，試求最小正整數(shù)n，使得對任意n個整數(shù)，其中總存在2個整數(shù)，它們的和或差被2k整除．

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

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

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

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

3 組合中的覆蓋問題

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

圖2

圖3

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

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

圖4

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

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

4 組合中的計數(shù)問題

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

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

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

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個單位簽約，只需再證這種構(gòu)造滿足第2個條件即可．設(shè)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任意地將數(shù)1，2，…，n寫在一個圓周上．允許每一次交換相鄰的位置，只要這2個數(shù)之差的絕對值大于1，試證經(jīng)過若干次這樣的交換之后，可以使得所有數(shù)按自然順序排列在圓周上．

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

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

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

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

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

(1)(2，2，2);

(2)(3，3，3)．

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

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

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

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

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

經(jīng)過n次操作可得

由于1 999=31+123×16，因此若取 a=31，則(17，31，47)需要123次擦去中間數(shù)的操作可達(dá)(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)經(jīng)過 9 次操作達(dá)到，所以(17，1 999，2 015)可由(3，3，3)經(jīng)過 123+9=132次操作達(dá)到．

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