組合極值問題

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

2、6個(gè)四元組。由于2000=256´7+208，故由抽屜原理知，有8份試卷上的答案屬于同一個(gè)四元組。取出這8份試卷后，余下的1992份試卷中仍有8份試卷屬于同一個(gè)四元組，再取出這8份試卷，余下的1984份試卷中又有8份屬于同一個(gè)四元組。又取出這8份試卷，三次共取出24份試卷。在這24份試卷中，任何4份中總有2份的答案屬于同一個(gè)四元組，當(dāng)然不滿足題目的要求，所以 n ³ 25 。下面證明 n 可以取到25。令，則 |S| =256 ，且S中任何2種答案都至多有3題相同。從 S 中去掉6個(gè)元素，當(dāng)余下的250種答案中的每種答案都恰有8人選用時(shí)，總有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，故），證明：對(duì)任意.分析：由于本題證明的是一個(gè)非嚴(yán)格不等式，則需要構(gòu)造一個(gè)單射或滿射來證之。證明：此題實(shí)質(zhì)上是要證因?qū)⒚總€(gè)n的拆法前加一個(gè)“1”，便可得一個(gè)n+1的拆法，故表示的是的拆法中的拆法數(shù)。同理是n+2的拆法中的拆法數(shù)?？紤]到，把一個(gè)的的拆法中的加上1，就可變?yōu)橐粋€(gè)的n+2的拆法，這樣就構(gòu)造了從的的拆法到的拆法的一個(gè)對(duì)應(yīng)，顯然這個(gè)對(duì)應(yīng)是一個(gè)單射，

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

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

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

7、È中至少有 m 個(gè)元素，故這 m 個(gè)人有2個(gè)公共朋友A和Ci ，與已知矛盾。由于¦ 是單射，故 ,因?yàn)?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是一個(gè) n 元集合，求最小的正整數(shù) k ，使得存在S的子集 A1 ,A2 , ¼ ，Ak 具有如下性質(zhì)：對(duì)S中的任意

8、兩個(gè)不同元素 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ì)的充分必要條件是兩兩不同。充分性：由兩兩不同，則對(duì)任意有，所以在某一行(設(shè)為第行)上，第列與第列的方格中一個(gè)為1，而另一個(gè)為0。這表明為單元素集，故具有題中性質(zhì)。必要性：由于對(duì)任意存在，使為單元素集，則與在第行處的兩個(gè)方格中的數(shù)一個(gè)為1，而另一個(gè)為0，故。所以

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

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

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

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

13、含三邊顏色相同的三角形y1ccaaaaabbbbb圖1 y5y2dddddccy4y3c圖2 對(duì)于，可用染的方法去染，至于的染法，可先加1點(diǎn)并將該點(diǎn)與原來的24點(diǎn)各連一條線段，然后，按的染法染好，再把加的1點(diǎn)及與該點(diǎn)所連的線段去掉，這樣，染后的也不含三邊顏色相同的三角開。4 歸納猜想 例8 給定平面上無三點(diǎn)共線的n個(gè)點(diǎn)，以這n個(gè)點(diǎn)為端點(diǎn)連出了m條線段，已知對(duì)這n個(gè)點(diǎn)中的任意兩點(diǎn)A、B，都有一點(diǎn)C，使得C與A、B都有線段相連，求m的最小值 解：記這n個(gè)點(diǎn)為A1，A2，An，先看一個(gè)例子 如果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個(gè)點(diǎn)至少需要連出條線段，才能達(dá)到題中要求。 事實(shí)上，如果A1，A2，An中任意一點(diǎn)都引出至少3條線段，則； 如果其中有一點(diǎn)（不妨設(shè)為A1）引出的線段條數(shù)不大于2，那么，有如下兩種情形： （1）A1只引出1條線段，不妨設(shè)為A1A2，則與A1，A2都有線段相連的點(diǎn)不存在，矛盾同樣地，若A1不引出線段也可得矛盾。 （2