組合極值問題

1、組合極值問題組合極值問題是各類數(shù)學(xué)競賽的熱點，它與代數(shù)，幾何，數(shù)論等相比風(fēng)格迥異。解組合極值問題往往需要某種技巧，因此，需要解題者具有豐富的解題經(jīng)驗與良好的題感。1 構(gòu)造法我們常常通過構(gòu)造抽屜，映射，表格等解決組合極值問題，有時還需要構(gòu)造例子說明取到極值。1.1構(gòu)造抽屜例1：(2000年中國數(shù)學(xué)奧林匹克)某次考試有5道選擇題，每題都有4個不同答案供選擇，每人每題恰好選1個答案。在2000份答案中發(fā)現(xiàn)存在一個 n ，使得任何 n 份答卷中都存在4份，其中每2份的答案都至多3題相同，求 n 的最小可能值。解：將每道題的4種答案分別記為1 ，2 ，3 ，4 ，每份試卷上的答案記為,其中。令,共得25

2、6個四元組。由于2000=256´7+208，故由抽屜原理知，有8份試卷上的答案屬于同一個四元組。取出這8份試卷后，余下的1992份試卷中仍有8份試卷屬于同一個四元組，再取出這8份試卷，余下的1984份試卷中又有8份屬于同一個四元組。又取出這8份試卷，三次共取出24份試卷。在這24份試卷中，任何4份中總有2份的答案屬于同一個四元組，當(dāng)然不滿足題目的要求，所以 n ³ 25 。下面證明 n 可以取到25。令，則 |S| =256 ，且S中任何2種答案都至多有3題相同。從 S 中去掉6個元素，當(dāng)余下的250種答案中的每種答案都恰有8人選用時，總有4份不相同。由于它們都在S中，當(dāng)

3、然滿足題目要求，這表明，n = 25滿足題目要求。綜上可知，所求的n 的最小可能值為25。1.2構(gòu)造映射例2將正整數(shù)n表示為一些正整數(shù)的和，即，其中，記是如此表示的方法種數(shù)（如4=4，4=1+3，4=2+2，4=1+1+2，4=1+1+1+1，故），證明：對任意.分析：由于本題證明的是一個非嚴(yán)格不等式，則需要構(gòu)造一個單射或滿射來證之。證明：此題實質(zhì)上是要證因?qū)⒚總€n的拆法前加一個“1”，便可得一個n+1的拆法，故表示的是的拆法中的拆法數(shù)。同理是n+2的拆法中的拆法數(shù)?？紤]到，把一個的的拆法中的加上1，就可變?yōu)橐粋€的n+2的拆法，這樣就構(gòu)造了從的的拆法到的拆法的一個對應(yīng)，顯然這個對應(yīng)是一個單射，

4、所以有評注：應(yīng)用映射法可以證明一些與計數(shù)有關(guān)的不等式。例3 設(shè)n是一個正整數(shù)，設(shè)T是所有頂點均在S中的正方形組成的集合，對于S中的一個點對（兩點組成），當(dāng)此點對恰是k個正方形的頂點時，則稱這個點對具有k重性，所有具有k重性的點對的個數(shù)記為試比較的大小。解 首先證明：一個點對至多屬于3個正方形，由于以點對間所連線段為一邊的正方形最多有兩個，而以該線段為對角線的正方形最多只有1個，故以一個點對為兩個頂點的正方形不超過3個，從而對任一點對，其重性只可能為0，1，2，3，另一方面，點對總數(shù)為，從而 (1) 將任意一點對及以該點對為兩頂點的正方形作為一個“頂點一正方形組”，簡稱VS組，規(guī)定：當(dāng)且僅當(dāng)點對

5、及正方形都相同時，VS組相同，設(shè)，一方面，對于每一個正方形包括6個點對，故有6S個VS組；另一方面，從點對的角度考慮VS組，對于k重性的任一點對必屬于k個正方形，從而VS組的總數(shù)為，綜合可得 （2）最后計算T中正方形的個數(shù)S。記T中兩邊為水平與豎直方向的正方形組成的集合為A，那么，T中任一個正方形a，都對應(yīng)著A中的一個正方形b，使得a的頂點全在b的邊界上，而對于A中一個邊長為i的正方形，在T中恰好有i個正方形，使得它們的頂點全在這個正方形的邊界上，又A中邊長為i的正方形有個，故即 （3）綜合（1），（2），（3），可知注 本題中，計算點對及VS組個數(shù)時，運用了算兩次，計算|T|時，則運用了映射

6、法計數(shù)。例4：在一節(jié)車廂中，任何 m ( m ³ 3 )個旅客都有唯一的公共朋友(當(dāng)甲是乙的朋友時，乙也是甲的朋友，任何人不作為他自己的朋友)。問在這節(jié)車廂中，朋友最多的人有多少個朋友？解：設(shè)朋友最多的人A有 k 個朋友，記為 B1 , B2 , ¼ , Bk , 并記。顯然， 。若 k > m ,設(shè)是S的任一個 m 元子集，則這 m 個人有1個公共朋友，記為 Ci ,因為Ci是A的朋友，所以Ci Î S 。定義映射：，則¦ 是從S的所有 m - 1元子集的集合到S的一個單射。事實上，若存在S的兩個不同的m - 1元子集和均有相同的像Ci ,又因為

7、È中至少有 m 個元素，故這 m 個人有2個公共朋友A和Ci ，與已知矛盾。由于¦ 是單射，故 ,因為 m ³ 3 , m - 1 ³ 2 ,所以( k - 1 ) ( k - 2 ) ( k -3 ) ( k - m + 2 ) > ( m - 1 ) ( m - 2 ) ¼2 = ( m - 1) !故矛盾，可見所求 k = m .1.3構(gòu)造圖表例5：設(shè) n Î N+ , n ³ 2 , S是一個 n 元集合，求最小的正整數(shù) k ，使得存在S的子集 A1 ,A2 , ¼ ，Ak 具有如下性質(zhì)：對S中的任意

8、兩個不同元素 a , b ，存在 j Î 1 ,2 , ¼ , k , 使 Aj Ç a , b 為S的一元子集。解：設(shè)，構(gòu)造表格1：123nA1100A2010A3AkP1P2P3Pn如果，那么，在所在行，所在列處的方格中標(biāo)上1，其余的方格中標(biāo)上0?？紤]表1的列構(gòu)成的序列 ，下面證明：S 的子集具有題中性質(zhì)的充分必要條件是兩兩不同。充分性：由兩兩不同，則對任意有，所以在某一行(設(shè)為第行)上，第列與第列的方格中一個為1，而另一個為0。這表明為單元素集，故具有題中性質(zhì)。必要性：由于對任意存在，使為單元素集，則與在第行處的兩個方格中的數(shù)一個為1，而另一個為0，故。所以

9、兩兩不同。根據(jù)表1知：2 染色法例6：設(shè)n 是一個固定的正偶數(shù)，考慮一塊的正方形板，它被分成n2個單位正方形格，板上2個不同的正方形格如果有一條公共邊，就稱它們?yōu)橄噜彽?。將板上N個單位正方形格作上標(biāo)記，使得板上的任意正方形格(作上標(biāo)記的或者沒有作上標(biāo)記的)都與至少一個作上標(biāo)記的正方形格相鄰，試確定N的最小值。解：設(shè)n = 2k，首先將正方形板黑白相間地染成像國際象棋棋盤那樣。設(shè)為所求的N的最小值，為必須作上標(biāo)記的白格子的最小數(shù)目，使得任一黑格子都有一個作上標(biāo)記的白格子與之相鄰。同樣的，定義為必須作上標(biāo)記的黑格子的最小數(shù)目，使得任一白格子都有一個作上標(biāo)記的黑格子與之相鄰。由于n是偶數(shù)，“棋盤”是

10、對稱的，故有，為方便起見，將“棋盤”按照最長的黑格子對角線水平放置，則各行黑格子的個數(shù)分別為。在含有個黑格子的那行下面，將奇數(shù)位置的白格子作上標(biāo)記。當(dāng)該行在對角線上方時，共有個白格子作上了標(biāo)記；當(dāng)該行在對角線下方時，共有個白格子作上了標(biāo)記。從而，作上了標(biāo)記的白格子共有個，所以這時每個黑格子都與1個作上標(biāo)記的白格子相鄰，故得?？紤]這個作上標(biāo)記的白格子，它們中的任意兩個沒有相鄰的公共黑格子，所以，至少還需要將個黑格子作上標(biāo)記，以保證這些白格子中的每一個都有一個作上標(biāo)記的黑格子與之相鄰，從而，故。因此，。3 調(diào)整法例7：給定平面上的點集，且P中任三點均不共線。將P中所有的點任意分成83組，使得每組至

11、少有三個點，且每點恰好屬于一組，然后，將在同一組的任兩個點用一條線段相連，不在同一組的兩個點不連線段，這樣得到一個圖案G。不同的分組方式得到不同的圖案。將圖案G中所含的以P中的點為頂點的三角形的個數(shù)記為m(G)。(1) 求m(G)的最小值 ；(2) 設(shè)是使的一個圖案，若將中的線段(指以P的點為端點的線段)用4種顏色染色，每條線段恰好染1種顏色。證明：存在一種染色方案，使染色后不含以P的點為頂點的三邊顏色相同的三角形。 解：(1)設(shè)m(G)= ，G由分組得到，其中為第組的點構(gòu)成的集合，。令，則有，且。下面證明：當(dāng)時，有。事實上，若存在使得，不妨設(shè)，作P的點的分組(為第i組的點構(gòu)成的集合，)，使得

12、 這樣的分組存在(只需從原來的中取一點到中，其余組的不動)，于是對于由分組得到的圖案G，有故=因為，所以，故與m0的最小性矛盾又1994=83×24+2=81×24+2×25故（2）設(shè)圖案由分組得到，這里Xi表示第i組的點構(gòu)成的集合（i=1,2,，83）。由（1），不妨設(shè)下面給出G*的一種染色方法，使得G*用4種不同顏色染后不含三邊顏色相同的三角形。將集合Xi及所連線段構(gòu)成的圖形稱為G*的第i塊，記為對于，令使得將每個子集中任兩個點所連線段用圖1所示的方法去染，將不同子集與之間所連線段用圖2所示的方法去染，圖中a、b、c、d分別代表4種不同顏色，這樣，染后的顯然不

13、含三邊顏色相同的三角形y1ccaaaaabbbbb圖1 y5y2dddddccy4y3c圖2 對于，可用染的方法去染，至于的染法，可先加1點并將該點與原來的24點各連一條線段，然后，按的染法染好，再把加的1點及與該點所連的線段去掉，這樣，染后的也不含三邊顏色相同的三角開。4 歸納猜想 例8 給定平面上無三點共線的n個點，以這n個點為端點連出了m條線段，已知對這n個點中的任意兩點A、B，都有一點C，使得C與A、B都有線段相連，求m的最小值 解：記這n個點為A1，A2，An，先看一個例子 如果n為奇數(shù)，連線段A1A2，A1A3，A1An；A2A3，A4A5，An-1An. 如果n為偶數(shù)，連線段A1A2，A1A3，A1An；A2A3，A4A5，An-2An-1, A2An. 顯然，依上述方法連出的線段滿足條件，所以，所求m的最小值小于或等于。（注：為上面連出的線段的條數(shù)，這里表示不超過x的最大整數(shù)。）下面證明：這n個點至少需要連出條線段，才能達到題中要求。 事實上，如果A1，A2，An中任意一點都引出至少3條線段，則； 如果其中有一點（不妨設(shè)為A1）引出的線段條數(shù)不大于2，那么，有如下兩種情形： （1）A1只引出1條線段，不妨設(shè)為A1A2，則與A1，A2都有線段相連的點不存在，矛盾同樣地，若A1不引出線段也可得矛盾。 （2