高中數(shù)學(xué)聯(lián)賽組合專題

1、課程簡(jiǎn)介：全國(guó)高中數(shù)學(xué)聯(lián)賽是中國(guó)高中數(shù)學(xué)學(xué)科的最高等級(jí)的數(shù)學(xué)競(jìng)賽，其地位遠(yuǎn)高于各省自行組織的數(shù)學(xué)競(jìng)賽。在這項(xiàng)競(jìng)賽中取得優(yōu)異成績(jī)的全國(guó)約90名學(xué)生有資格參加由中國(guó)數(shù)學(xué)會(huì)主辦的“中國(guó)數(shù)學(xué)奧林匹克（CMO）暨全國(guó)中學(xué)生數(shù)學(xué)冬令營(yíng)”。優(yōu)勝者可以自動(dòng)獲得各重點(diǎn)大學(xué)的保送資格。各省賽區(qū)一等獎(jiǎng)前6名可參加中國(guó)數(shù)學(xué)奧林匹克，獲得進(jìn)入國(guó)家集訓(xùn)隊(duì)的機(jī)會(huì)。中小學(xué)教育網(wǎng)重磅推出“全國(guó)高中數(shù)學(xué)聯(lián)賽”輔導(dǎo)課程，無(wú)論是有意向參加競(jìng)賽的初學(xué)者，還是已入圍二試的競(jìng)賽選手，都有適合的課程提供。本套課程由中國(guó)數(shù)學(xué)奧林匹克高級(jí)教練熊斌、人大附中數(shù)學(xué)教師李秋生等名師主講，輕松突破你的數(shù)學(xué)極限！課程招生簡(jiǎn)章： 選課中心地址： 第二章組合

2、專題 一、重要的概念與定理1、完全圖：每?jī)蓚€(gè)頂點(diǎn)之間均有邊相連的簡(jiǎn)單圖稱為完全圖,有個(gè)頂點(diǎn)的完全圖（階完全圖）記為.2、頂點(diǎn)的度：圖中與頂點(diǎn)相關(guān)聯(lián)的邊數(shù)（環(huán)按2條邊計(jì)算）稱為頂點(diǎn)的度（或次數(shù)）,記為.與分別表示圖的頂點(diǎn)的最小度與最大度.度為奇數(shù)的頂點(diǎn)稱為奇頂點(diǎn),度為偶數(shù)的頂點(diǎn)稱為偶頂點(diǎn).3、樹(shù)：沒(méi)有圈的連通圖稱為樹(shù),用表示,其中度為1的頂點(diǎn)稱為樹(shù)葉（或懸掛點(diǎn)）.階樹(shù)常表示為.4、部圖：若圖的頂點(diǎn)集可以分解為個(gè)兩兩不相交的非空子集的并,即并且同一子集內(nèi)任何兩個(gè)頂點(diǎn)沒(méi)有邊相連,則稱這樣的圖為部圖,記作. 2部圖又叫做偶圖,記為.5、完全部圖：在一個(gè)部圖中, ,若對(duì)任意均有邊連接和,則稱圖

3、為完全部圖,記為.6、歐拉跡：包含圖中所有邊的跡稱為歐拉跡.起點(diǎn)與終點(diǎn)重合的歐拉跡稱為閉歐拉跡.歐拉圖：包含歐拉跡的圖為歐拉圖. 歐拉圖必是連通圖.哈密頓鏈（圈）：經(jīng)過(guò)圖上各頂點(diǎn)一次并且僅僅一次的鏈（圈）稱為哈密頓鏈（圈）.包含哈密頓圈的圖稱為哈密頓圖.7、平面圖：若一個(gè)圖可畫(huà)在平面上,即可作一個(gè)與同構(gòu)的圖,使的頂點(diǎn)與邊在同一平面內(nèi),且任意兩邊僅在端點(diǎn)相交,則圖稱為平面圖.一個(gè)平面圖的頂點(diǎn)和邊把一個(gè)平面分成若干個(gè)互相隔開(kāi)的區(qū)域,稱為平面圖的一個(gè)面,在所有邊的外面的面稱為外部面,其余的稱為內(nèi)部面.8、競(jìng)賽圖：有向完全簡(jiǎn)單圖稱為競(jìng)賽圖.有個(gè)頂點(diǎn)的競(jìng)賽圖記作.9、有向路：在有向圖中,一個(gè)由不同的弧組

4、成的序列,其中的起點(diǎn)為,終點(diǎn)為,稱這個(gè)序列為從到的有向路（簡(jiǎn)稱路）,為這個(gè)路的長(zhǎng),為路的起點(diǎn),為路的終點(diǎn).若,則稱這個(gè)路為回路.定理1 設(shè)是階圖,則中個(gè)頂點(diǎn)的度之和為邊數(shù)的2倍.定理2 對(duì)于任意圖,奇頂點(diǎn)的個(gè)數(shù)一定是偶數(shù).定理3（Turan定理） 有個(gè)頂點(diǎn)且不含三角形的圖的最大邊數(shù)為.定理4 圖為偶圖,當(dāng)且僅當(dāng)中不含長(zhǎng)度為奇數(shù)的圈.定理5 若樹(shù)的頂點(diǎn)數(shù),則中至少有兩個(gè)樹(shù)葉.定理6 若數(shù)有個(gè)頂點(diǎn),則的邊數(shù).定理7 設(shè)是有個(gè)頂點(diǎn)、條邊的圖,則下列命題等價(jià): 圖是樹(shù); 圖無(wú)圈,且; 圖連通,且.定理8 階連通圖中以樹(shù)的邊數(shù)最少,且階連通圖必有一個(gè)子圖是樹(shù).定理9（一筆畫(huà)定理） 有限圖是一條鏈或圈（可

5、以一筆畫(huà)成）的充要條件是是連通的,且奇頂點(diǎn)的個(gè)數(shù)為0或2. 當(dāng)且僅當(dāng)奇頂點(diǎn)個(gè)數(shù)為0時(shí),連通圖是一個(gè)圈.定理10 在偶圖中,若,則一定無(wú)哈密頓圈.若與的差大于1,則一定無(wú)哈密頓鏈.定理11 設(shè)是階簡(jiǎn)單圖,且對(duì)每一對(duì)頂點(diǎn)有,則圖有哈密頓鏈.定理12 設(shè)是階簡(jiǎn)單圖,且對(duì)每一對(duì)不相鄰的頂點(diǎn)有,則圖有哈密頓圈.定理13 設(shè)是階簡(jiǎn)單圖,若每個(gè)頂點(diǎn)的度,則圖有哈密頓圈.定理14 若圖有哈密頓圈,從中去掉若干個(gè)點(diǎn)及與它們關(guān)聯(lián)的邊得到圖,則圖的連通分支不超過(guò)個(gè).定理15（歐拉公式） 若一個(gè)連通的平面圖有個(gè)頂點(diǎn)、條邊、個(gè)面,則.定理16 一個(gè)連通的平面簡(jiǎn)單圖有個(gè)頂點(diǎn)、條邊,則,對(duì)于連通的偶圖,則有 .定理17 一

6、個(gè)圖是平面圖當(dāng)且僅當(dāng)它不包含同胚于或的子圖.定理18 設(shè)階競(jìng)賽圖的頂點(diǎn)為,則,且.定理19 競(jìng)賽圖中出度最大的點(diǎn)稱為“優(yōu)點(diǎn)”,“優(yōu)點(diǎn)”到其余各點(diǎn)都有長(zhǎng)度不超過(guò)2的鏈.定理20 競(jìng)賽圖中存在一條長(zhǎng)為的哈密頓路.定理21 競(jìng)賽圖中有一個(gè)回路是三角形的充要條件是有兩個(gè)頂點(diǎn) 滿足 .定理22（Ramsey定理） 任意2色完全圖中必存在同色三角形.二、例題選講例1 、某天晚上21個(gè)人之間通了電話,有人發(fā)現(xiàn)這21人共通話102次,且每?jī)扇酥炼嗤ㄔ捯淮?他還發(fā)現(xiàn),存在個(gè)人,第1個(gè)人與第2個(gè)人通了話,第2個(gè)人與第3個(gè)人通了話, 第個(gè)人與第個(gè)人通了話,第個(gè)人又與第1個(gè)人通了話,他不肯透露的具體值,只說(shuō)是奇數(shù).求

7、證: 21個(gè)人中必存在3人,他們兩兩通了話.例2、45個(gè)校友聚會(huì),在這些人中,任意兩個(gè)熟人數(shù)目相同的校友互不認(rèn)識(shí).問(wèn)在參加校友聚會(huì)的所有人中,熟人最多的人的數(shù)目最多是多少?1.平面上的 n（ 4）個(gè)點(diǎn)中，任何4個(gè)點(diǎn)都是凸四邊形的頂點(diǎn)。證明這n個(gè)點(diǎn)是一個(gè)凸n邊形的頂點(diǎn)。2.平面上有兩條線段 AB和CD使得ABDC是平行四邊形。我想把AB在平面上（連續(xù)地）移動(dòng)直到A與C重合，B與D重合。證明：不管這兩條線段多長(zhǎng)，也不管它們相距多遠(yuǎn)，我總可以使得在平移的過(guò)程中AB掃過(guò)的總面積小于1。3.證明:平面上任意 n（正整數(shù)）個(gè)點(diǎn)能被滿足下列條件的有限個(gè)圓盤(pán)（圓盤(pán)包含邊界）覆蓋:它們直徑之和小于n，而且任何兩

8、個(gè)圓盤(pán)之間的距離（指這兩個(gè)圓盤(pán)上各取一點(diǎn)的最小距離）都大于1。4.在平面直角坐標(biāo)系中，求所有滿足下列條件的過(guò)原點(diǎn)的直線 l:對(duì)于任意實(shí)數(shù)a，b以及d > 0,都存在整數(shù)m，n和l上的點(diǎn)P使得（a + m，b + n）和P的距離小于d。5.證明:任給正整數(shù) n，總存在正整數(shù)K使得下面的結(jié)論成立:如果平面上K個(gè)點(diǎn)中沒(méi)有三點(diǎn)共線，那么這些點(diǎn)中必定存在n個(gè)點(diǎn)是一個(gè)凸n邊形的頂點(diǎn)。6.一個(gè)矩形 R被切成了若干個(gè)（內(nèi)部不相交的而且拼起來(lái)恰好是整個(gè)R的）小矩形，這些小矩形的邊都與R的邊平行或垂直，而且每個(gè)小矩形至少有一條邊長(zhǎng)為整數(shù)。證明：R也至少有一條邊長(zhǎng)為整數(shù)。7.平面上的點(diǎn)集 S中有有限個(gè)不全共線

9、的點(diǎn)，它們被染成紅和藍(lán)兩種顏色。證明:存在一條直線使得它過(guò)S中至少兩個(gè)點(diǎn)，而且S中在這條直線上的所有點(diǎn)都是同一種顏色。1.試求n項(xiàng)的沒(méi)有兩個(gè)或以上連續(xù)的0的0，1序列的個(gè)數(shù)。 2.m，n是正整數(shù).證明:每個(gè)由mn+1個(gè)不同實(shí)數(shù)組成的數(shù)列一定有一個(gè)（m+1）項(xiàng)遞增子序列或者一個(gè)（n+1）項(xiàng)遞減子序列。 3.正整數(shù)n的一個(gè)分拆是指把n分成若干個(gè)正整數(shù)（不計(jì)次序）之和.證明對(duì)于任意正整數(shù)n,n的分成每部分都是奇數(shù)的分拆個(gè)數(shù)等于n的分成每部分互不相同的分拆個(gè)數(shù)。 4.n是給定正整數(shù).將n個(gè)黑子和n個(gè)白子任意放在一個(gè)圓周上.從某個(gè)白子起,按順時(shí)針?lè)较蛞来螌⑷w白子標(biāo)上1，2，n,再?gòu)哪硞€(gè)黑子起,按逆時(shí)針

10、方向依次將全體黑子標(biāo)上1，2，n.證明:在圓周上必可以找到連續(xù)n個(gè)棋子,使得它們標(biāo)號(hào)所成的集合恰好為1，2，n。5.設(shè)n和k是正整數(shù),且（k n）是非負(fù)偶數(shù).有2n盞燈依次編號(hào)為1，2，2n,每一盞燈可以開(kāi)和關(guān).開(kāi)始時(shí)所有的燈都是關(guān)的, 現(xiàn)在要對(duì)這些燈進(jìn)行k次操作,每次操作改變且只改變一盞燈的開(kāi)關(guān)狀態(tài).用N表示滿足“k次操作以后燈1，2，n是開(kāi)的,其它燈都是關(guān)的”的不同操作序列總數(shù),用M表示滿足“k次操作以后燈1，2，n是開(kāi)的,其它燈都是關(guān)的而且從來(lái)沒(méi)有被開(kāi)過(guò)”的不同操作序列總數(shù).試求比值。6.給定n，k是正整數(shù),.假設(shè)F是1，2，n的子集族,如果F中的每個(gè)集合都有k個(gè)元素,而且F中任何兩個(gè)集

11、合都相交非空,那么F的最大可能值是多少? 7.有12個(gè)人,其中任何9人中都有5人兩兩認(rèn)識(shí).證明:這12人中必有6人兩兩認(rèn)識(shí)。 【知識(shí)儲(chǔ)備】【例題精講】1.p1是實(shí)數(shù)，n是正整數(shù).證明閔可夫斯基不等式：任給實(shí)數(shù)a1,a2.,b1,b2,.,bn,必有：2.如果函數(shù)f：ZR滿足：存在正數(shù)M使得對(duì)于任意正數(shù)a和正整數(shù)d，（這里I=a-d,a+d,表示f在I上的平均值），那么就稱f是BMO的，M則稱為f的一個(gè)BMO模長(zhǎng).證明存在正的常數(shù)C，使得對(duì)于任何BMO的函數(shù)f，只要M是f的一個(gè)BMO模長(zhǎng)，就有對(duì)任何正數(shù)a和正整數(shù)d,3.設(shè)n是給定的正整數(shù).S=1,2,n.求|AS|+|BS|+|CS|的最小值.

12、這里A,B是非空有限實(shí)數(shù)集合，C=A+B=x+y|xA,yB.XY表示由恰好屬于X,Y中一個(gè)的元素組成的集合.4.證明存在正的常數(shù)C，使得平面直角坐標(biāo)系中的任意有限個(gè)（邊平行于坐標(biāo)軸的）正方形中必能挑出一些正方形兩兩內(nèi)部無(wú)公共點(diǎn)，而且他們覆蓋的總面積不小于全體正方形覆蓋總面積的C倍.5.設(shè)A是一個(gè)有限實(shí)數(shù)集.A1,A2,An是A的非空子集，且滿足：（i）A中所有元素之和為0；（ii）對(duì)任意xiAi（i=1,2，,n）,都成立.證明:存在1i1<i2<<ikn使得6.設(shè)m和n是給定的正整數(shù)，4<m<n.A1A2A2n+1是一個(gè)正（2n+1）邊形，P=A1， A 2，A2n+1.求頂點(diǎn)屬于