組合構(gòu)造答案及講稿

1、【組合十講】組合構(gòu)造陶平生構(gòu)造法是解證組合問(wèn)題的重要方法與基本手段，使用它，常?？梢詫?wèn)題化難為易，化抽象為直觀， 它需要較強(qiáng)的結(jié)構(gòu)轉(zhuǎn)化與知識(shí)綜合能力常用的構(gòu)造方法有：數(shù)論構(gòu)造法；幾何構(gòu)造法；模型構(gòu)造法；旋轉(zhuǎn)、置換（群）構(gòu)造法；圖表構(gòu)造法；圖論構(gòu)造法等一、數(shù)論構(gòu)造法我們通過(guò)一些具體例子來(lái)說(shuō)明這一方法的運(yùn)用、空間有個(gè)點(diǎn)，無(wú)三點(diǎn)共線，現(xiàn)將每?jī)牲c(diǎn)之間用一種顏色的線連接，使得對(duì)于其中任意一點(diǎn)而言，由該點(diǎn)發(fā)出的任兩條線皆不同色，問(wèn)至少需要多少種不同顏色的線？證明你的結(jié)論若將個(gè)點(diǎn)改為個(gè)點(diǎn)，情況又將如何？解：一般化，將改為，其中正整數(shù)，線段顏色數(shù)的最小值記為，易知， 今證明，一般情況下有設(shè)個(gè)點(diǎn)為，由于每點(diǎn)都

2、要發(fā)出條線，諸線不同色，這樣至少需要色；再證色不夠，若總共只有色，則每點(diǎn)都要恰好屬于各色線的端點(diǎn)一次現(xiàn)在設(shè)總共有條紅色線，它們總共有個(gè)兩兩互異端點(diǎn)，于是，矛盾！因此，即下面說(shuō)明最小值可以取到，采用數(shù)論構(gòu)造法：用分別表示這色，而表示整數(shù)模的最小非負(fù)余數(shù)，即，對(duì)于任意兩點(diǎn)，將連線染第色，于是，對(duì)于任意一點(diǎn)，發(fā)自的任兩條線皆不同色事實(shí)上，假若與同色，則有，即，得，因，故有，矛盾！故這種染色方案合于條件，因此，又對(duì)于個(gè)點(diǎn)，由于每點(diǎn)都要向其余點(diǎn)共發(fā)出條線，諸線不同色，這樣至少需要色，只要證，色已足夠構(gòu)造，仍用分別表示這色，暫不考慮點(diǎn)，先對(duì)前個(gè)點(diǎn)兩兩間的連線依照上述個(gè)點(diǎn)的情形染色，我們注意到，對(duì)于其中任意

3、兩點(diǎn)的連線染色時(shí)，要求，也就是說(shuō)，由點(diǎn)發(fā)出的條線的顏色代號(hào)，為模的完系中缺少了一個(gè)剩余現(xiàn)將點(diǎn)與前個(gè)點(diǎn)中任一點(diǎn)的連線染第色，由于當(dāng)時(shí)與模不同余，故由點(diǎn)發(fā)出的條線互不同色，由其它點(diǎn)發(fā)出的條線也互不同色，故這種染色方案合于條件因此，從而于是對(duì)于個(gè)點(diǎn)或是個(gè)點(diǎn)，都至少需要種顏色的線 下面的圖形是和的情況由此可以看到，利用數(shù)論構(gòu)造法給出的染色方案，優(yōu)美和諧，渾然天成、證明：可以將集合中的元素分成組，使得每組的元素和相等證：我們可一般化為下述命題：若奇數(shù)，則集合可以分拆成個(gè)兩兩不交的元素之和相等的子集之并在集合中添加元素，并將諸元素依自小到大的順序排列，然后按每個(gè)數(shù)一段分成三段：易知，對(duì)于兩個(gè)具有個(gè)項(xiàng)的遞增

4、連續(xù)自然數(shù)數(shù)列及，它們按相反次序相加的每?jī)身?xiàng)之和為常數(shù)：即；因此只要證，可以將第一段的個(gè)數(shù)適當(dāng)排成，第二段的個(gè)數(shù)適當(dāng)排成，使得恰好組成個(gè)連續(xù)自然數(shù)；（此時(shí)只要將所得的這個(gè)數(shù)與第三段的數(shù)反序相加，就得到相等的個(gè)和）若將第二段的每個(gè)數(shù)各減，問(wèn)題又化為：若奇數(shù)，存在前個(gè)自然數(shù)的兩個(gè)排列：及，使得恰好組成個(gè)連續(xù)自然數(shù)；為此，采用構(gòu)造法，設(shè)個(gè)連續(xù)自然數(shù)中，最小的一數(shù)為，則此個(gè)數(shù)為，其和為，又據(jù)，故由，得，這樣，問(wèn)題化為：若奇數(shù)，存在前個(gè)自然數(shù)的兩個(gè)排列：及，使得，為直觀起見(jiàn)，記為；注意到，時(shí)，而；時(shí)，而；時(shí)，而；若用記號(hào)表示整數(shù)被除得的最小非負(fù)余數(shù)，據(jù)上述情況可以推測(cè)，對(duì)于奇數(shù)，可以構(gòu)作滿足條件的兩個(gè)數(shù)

5、列，其中，先說(shuō)明，以及，各自通過(guò)模的最小非負(fù)完全剩余系，事實(shí)上，對(duì)每個(gè)，并且這個(gè)中，任兩個(gè)不相等，因?yàn)槿粲惺?，即，也就是，由于為奇?shù)，則，而，矛盾！同理可知，也通過(guò)模的最小非負(fù)完全剩余系；于是，分別是的一個(gè)排列；又注意，因此構(gòu)成以為最小數(shù)的個(gè)連續(xù)自然數(shù)于是所證的結(jié)論成立、給定兩個(gè)正整數(shù)，其中，且；試求最小的正整數(shù)，使得在任意個(gè)滿足條件：“對(duì)一切，”的整數(shù)中，都存在兩個(gè)整數(shù)和，使得可被整除解：由于所考慮的是“被整除”這一特征，故可將題中所涉整數(shù)皆替換為“被除得的余數(shù)”來(lái)考慮；用表示整數(shù)被除得的最小正余數(shù)，即，；為了探求本題結(jié)論的一般性結(jié)構(gòu)，先分析以下特例：例、取，這時(shí)，且當(dāng)且僅當(dāng)，即；于是，有兩

6、種情況：、； 、，即問(wèn)題化為，從中取個(gè)數(shù)，為了保證這個(gè)數(shù)中必有兩數(shù)之差（大數(shù)減小數(shù)）為或，求的最小值.為此，將數(shù)排列于一個(gè)圓周之上，使得相鄰兩兩數(shù)之差（大數(shù)減小數(shù)）都為或，有右圖的排法：從其中任取個(gè)不同的數(shù)，為了保證取出的數(shù)中必有兩個(gè)相鄰，則至少要取六個(gè)數(shù)，即；例、取，這時(shí)，且當(dāng)且僅當(dāng)， 此時(shí)也有兩種情況：；或?qū)?shù)排列于一個(gè)圓周之上，使得相鄰兩兩數(shù)之差（大數(shù)減小數(shù)）都為或，這時(shí)排出三個(gè)圈：此處作成三個(gè)圈是因?yàn)榈木壒蕪闹腥稳€(gè)不同的數(shù)，為了保證取出的數(shù)中必有兩個(gè)相鄰，則在三個(gè)圈中，總共至少要取七個(gè)數(shù)，即；（若總共只取六個(gè)數(shù)，可以選擇每個(gè)圈上各取兩個(gè)數(shù)，且不相鄰，這樣得到的六數(shù)不能滿足條件）現(xiàn)分析

7、的數(shù)字結(jié)構(gòu)：其中是圓周的個(gè)數(shù)；數(shù)是在同一個(gè)取出的元素個(gè)數(shù)，使得在同一個(gè)圓周上可能不存在相鄰數(shù)的最大允許值，它當(dāng)然與該圓周上元素的個(gè)數(shù)有關(guān)，而，； 于是猜測(cè)，一般有： 其中，.今考慮一般情況：由等價(jià)于，而，所以，條件等價(jià)于，且，而條件等價(jià)于，即，于是，由，得 或，即，或，記，設(shè)，則，據(jù)得或 由知，而由得；因此由得 ，設(shè)，；， 今按的取值情況討論：、若，則化為，或 且因及，由知均不為，即，改記，則，于是式可改寫(xiě)為對(duì)稱形式：和引理：設(shè)，為正整數(shù)，從中取出一個(gè)元子集，使得中的任兩數(shù)之差，既不為，也不為，則的最大值為采用數(shù)論構(gòu)造法為了導(dǎo)出一般性方法，先分析一個(gè)特例:取，將按圖中順序排列于圓周上，使得相鄰

8、兩數(shù)之差或者為，或者為，而不相鄰的任兩數(shù)之差，既不是，也不是；若將圓周上的個(gè)數(shù)按順時(shí)針?lè)较蜃x出，就是：，圈中不相鄰的數(shù)最多可取到個(gè)由于對(duì)一般的，我們不可能一個(gè)個(gè)地去構(gòu)造，為此，重新研究這組數(shù)的結(jié)構(gòu)，對(duì)于，不難發(fā)現(xiàn)，前三項(xiàng)分別可看作，由此想到，后續(xù)的項(xiàng)當(dāng)是，即是說(shuō)，對(duì)于一般的，填寫(xiě)于圓周上的個(gè)數(shù)順次為；另一方面，據(jù)對(duì)稱性，我們也可順次寫(xiě)出，它與上面填寫(xiě)于圓周上的個(gè)數(shù)實(shí)際上是重合的一組，只不過(guò)是按相反的方向從圓周上讀出而已下面證明，排在圓周上的這組數(shù)符合要求.由，知，即，而是整數(shù)被除得的最小正余數(shù)，故上述個(gè)數(shù)，每個(gè)皆屬于；這組數(shù)中，任兩個(gè)皆不相等：假若，則，即，于是，而，矛盾！因此就是的一個(gè)排列；

9、并且相鄰兩數(shù)之差滿足：， 由于中的數(shù)，任兩個(gè)不等，故相鄰兩數(shù)之差（大數(shù)減小數(shù)）屬于集，而為模的一個(gè)完全剩余系，故其中與同余的只有，與同余的只有，因此由中兩式得，相鄰兩數(shù)之差，要么是，要么是因此，要想在此圓周上所取的數(shù)不含相鄰數(shù)，至多只能取個(gè)數(shù)而當(dāng)取出個(gè)數(shù)時(shí)，其中必有兩數(shù)相鄰，其差為或、當(dāng)時(shí)，由得 ，即，式化為，或，這與的形式完全相同，因此仿照的討論可知，對(duì)于每個(gè)，我們也分別可以得到一個(gè)含有個(gè)數(shù)的圈，使得相鄰兩數(shù)之差，要么是，要么是為了在每個(gè)圈上不取到相鄰的數(shù)，至多只能取個(gè)數(shù)而當(dāng)取出個(gè)數(shù)時(shí)，其中必有兩數(shù)相鄰，其差為或并且，任兩個(gè)圈上的數(shù)顯然不同：假若，則，于是，得，矛盾！若取出的元素個(gè)數(shù)，則上述

10、個(gè)圈中，必有一個(gè)圈至少取出了個(gè)數(shù)，導(dǎo)致該圈上必有兩數(shù)相鄰，即有，使；另一方面，若取出的元素個(gè)數(shù)時(shí)，則有取法，即在每個(gè)圈上各取個(gè)數(shù)，使得任兩數(shù)在圈上都不相鄰，這時(shí) ，因此，適合條件的的最小值是，（其中）、支足球隊(duì)進(jìn)行單循環(huán)賽，即每輪將支球隊(duì)分成組，每組的兩隊(duì)比賽一場(chǎng)，下一輪重新分組進(jìn)行比賽，共賽輪，使得每隊(duì)都與另外支球隊(duì)各賽一場(chǎng)按任意可行的程序比賽了輪之后，總存在支球隊(duì)，它們之間總共只賽了一場(chǎng)；求的最大可能值解：先構(gòu)造一種比賽方案：將支球隊(duì)順次編號(hào)為，并按奇數(shù)與偶數(shù)分成兩個(gè)子集：，再將每場(chǎng)比賽的隊(duì)依照其和被除的余數(shù)情況而規(guī)定輪次，并且先在同奇偶的隊(duì)之間各安排場(chǎng)，再將“掛單”的兩個(gè)隊(duì)安排一場(chǎng)比賽；

11、即要求，第輪中每場(chǎng)比賽的隊(duì)滿足：即第一輪的：；第二輪的：；第三輪的：；第四輪的：；第五輪的：；第六輪的：；第七輪的：；第八輪的：；第九輪的：；在這九輪比賽中，共含有個(gè)（奇、奇）型搭配，個(gè)（偶、偶）型搭配，而，故知在這九輪中，一切（奇、奇）型搭配，（偶、偶）型搭配均已出現(xiàn)，即任一對(duì)（奇、奇）號(hào)球隊(duì)都比賽過(guò)，任一對(duì)（偶、偶）號(hào)球隊(duì)也都比賽過(guò)于是，當(dāng)賽完上述的九輪后，在這支球隊(duì)中任取四個(gè)隊(duì)，設(shè)其編號(hào)為，由于三數(shù)中必有兩數(shù)同奇偶，設(shè)為，則他們已賽過(guò)，去掉，在三數(shù)中，又有兩數(shù)同奇偶，他們也已賽過(guò)；因此若按這種分組方式進(jìn)行了輪比賽之后，任何四個(gè)隊(duì)之間都至少比賽過(guò)兩場(chǎng)，于是適合條件的必應(yīng)滿足：此外，我們尚需

12、補(bǔ)充說(shuō)明，上述的輪比賽確實(shí)是一種符合要求安排中的前輪即，在以上輪賽完后，我們還可以繼續(xù)安排后續(xù)輪比賽，從而保證全部輪比賽可以順利進(jìn)行下去為此，作兩個(gè)同心圓盤(pán)，且各分成個(gè)相等的扇形小格，按反時(shí)針?lè)较蝽槾螌⒕艂€(gè)奇數(shù)以及九個(gè)偶數(shù)分別填入外盤(pán)及內(nèi)盤(pán)的格子中，然后轉(zhuǎn)動(dòng)內(nèi)盤(pán)，使得在前九輪中已經(jīng)比賽過(guò)的每一對(duì)（奇、偶）型搭配，分別位于對(duì)齊后的同一個(gè)小扇形中，于是得到圖一在前九輪比賽中，外圈的任兩隊(duì)之間，內(nèi)圈的任兩隊(duì)之間，以及任一個(gè)小扇形中的兩隊(duì)之間都已比賽過(guò)為敘述方便，令向量，這樣圖一便可改記為圖二在前九輪比賽中，已賽過(guò)，已賽過(guò)，已賽過(guò)，而未賽過(guò)，今用下述方法安排后續(xù)輪比賽：將內(nèi)盤(pán)固定，讓外盤(pán)繞中心作反時(shí)針

13、旋轉(zhuǎn)，每次轉(zhuǎn)過(guò)一格，對(duì)齊后，便在每一扇形內(nèi)的兩隊(duì)之間各安排一場(chǎng)比賽，個(gè)扇形中的兩隊(duì)共安排出場(chǎng)比賽，這樣便構(gòu)成一輪比賽；八次旋轉(zhuǎn)共得輪比賽，其中第次旋轉(zhuǎn)后的場(chǎng)比賽是：，（約定），經(jīng)過(guò)這樣的輪比賽后，所有都已賽過(guò)，從而在全部輪比賽過(guò)后，這支球隊(duì)的任兩支球隊(duì)都賽過(guò)一場(chǎng)，且僅賽過(guò)一場(chǎng)，因此這輪比賽是符合要求的比賽，從而它的前九輪及后八輪比賽都合要求 接下來(lái)考慮比賽輪數(shù)的情況，我們?nèi)魧⑸鲜鲚啽荣惖捻樞蝾嵉惯^(guò)來(lái)，即先安排后面的輪比賽，再安排前面的輪比賽，顯然，這也是一種可行的安排經(jīng)過(guò)這樣的輪比賽后，支球隊(duì)滿足：未賽過(guò)，未賽過(guò)，未賽過(guò)，而皆已賽過(guò) 今從支球隊(duì)中任取四個(gè)隊(duì)，據(jù)對(duì)稱性，不妨設(shè)，取自中的球隊(duì)較多，

14、則有以下三種情況：、若四個(gè)隊(duì)全取自中，則這四個(gè)隊(duì)兩兩之間皆未賽過(guò)；、若三個(gè)隊(duì)來(lái)自，一個(gè)隊(duì)來(lái)自，設(shè)為及，由于中至少有兩個(gè)數(shù)異于，因此至少與中的兩個(gè)隊(duì)賽過(guò)，于是這四個(gè)隊(duì)之間至少賽過(guò)兩場(chǎng)；、若兩個(gè)隊(duì)來(lái)自，兩個(gè)隊(duì)來(lái)自，設(shè)為與，則至少和中的一個(gè)隊(duì)賽過(guò)，也至少和中的一個(gè)隊(duì)賽過(guò)，于是這四個(gè)隊(duì)之間至少賽過(guò)兩場(chǎng)因此，按這種分組方式比賽輪之后，任何四個(gè)隊(duì)之間，或者沒(méi)有賽過(guò)，或者至少賽了兩場(chǎng)，也就是不存在恰好只賽了一場(chǎng)的情況于是適合條件的應(yīng)當(dāng)滿足： 下面證明，的最大值就是即需證，無(wú)論每一輪怎樣分組，當(dāng)比賽輪數(shù)時(shí)，其中必有四個(gè)隊(duì)，他們兩兩之間恰好只比賽了一場(chǎng)設(shè)支球隊(duì)按任一可行的方式分組，并賽完輪，則每一隊(duì)恰好賽過(guò)場(chǎng)（

15、與個(gè)隊(duì)賽過(guò)），而與另外的個(gè)隊(duì)未賽過(guò)（這里注意，）今用個(gè)點(diǎn)表示這支球隊(duì)，如果兩隊(duì)賽過(guò)，則在點(diǎn)間連一條邊，于是得階圖，的每個(gè)頂點(diǎn)的度數(shù)皆為（記為）在中取兩個(gè)不相鄰的頂點(diǎn)，因，故在中異于的個(gè)點(diǎn)中，必有一點(diǎn)，它與都不相鄰于是中的點(diǎn)互不相鄰，將中由其余個(gè)頂點(diǎn)組成的集記為，由于的三點(diǎn)互不相鄰，每點(diǎn)的度數(shù)為，故連接之間的邊恰有條，（注意）、若集合中有一點(diǎn)，例如，向集合只發(fā)了一條邊，則四點(diǎn)為所求（它們之間恰有一條邊）；、若中的每個(gè)點(diǎn)，或者向不發(fā)邊，或者向發(fā)出的邊數(shù)，由于連接之間的總邊數(shù)，則的個(gè)點(diǎn)之中，向發(fā)邊的點(diǎn)不能多于個(gè)點(diǎn)，即至少有個(gè)點(diǎn)與中的點(diǎn)不相鄰，設(shè)這點(diǎn)為；若這點(diǎn)中有某兩點(diǎn)相鄰，設(shè)為，則四點(diǎn)為所求；若中的

16、任兩點(diǎn)不相鄰，則將其并入；令，這時(shí)中有個(gè)點(diǎn)、改記，其余點(diǎn)構(gòu)成集合集中，任兩點(diǎn)不相鄰，每點(diǎn)的度數(shù)為，則連接之間的邊數(shù)為，于是的個(gè)點(diǎn)之中必有一點(diǎn)向發(fā)出的邊數(shù)，設(shè)此點(diǎn)為若，即是說(shuō)，至少與中的兩個(gè)點(diǎn)不相鄰，且必與中的一點(diǎn)相鄰，數(shù)與不相鄰，而與相鄰，則四點(diǎn)為所求；若，即與中的每個(gè)點(diǎn)都不相鄰，改記為，且將其并入；令，；中任兩點(diǎn)不相鄰，每一點(diǎn)度數(shù)為，故連接之間的邊有條；由于中的個(gè)點(diǎn)，每點(diǎn)的度數(shù)也是，則的每點(diǎn)必須向發(fā)出條邊，故中任兩點(diǎn)也不相鄰取，由于向發(fā)出條邊，而，故中必有兩點(diǎn)與不相鄰，設(shè)為，且必有一點(diǎn)與相鄰，設(shè)為，則四點(diǎn)為所求綜以上討論得，當(dāng)比賽輪數(shù)時(shí)，按任何可行的方案分組，當(dāng)賽完輪后，總有四個(gè)隊(duì)，它們之間

17、恰好只賽了一場(chǎng)因此，的最大可能值是二、旋轉(zhuǎn)、置換（群）構(gòu)造法、集合組由個(gè)五元集組成，其中任意兩個(gè)集合的交都不是空集，令，中含有元素的集合數(shù)目為，記，求的最小值解：易得 這一事實(shí)利用“算兩次”原理可立即得到：作一張的表，若，則在表中第行、列的交叉處填寫(xiě)一個(gè)“*”號(hào)；*于是若按行計(jì)算，第行共有個(gè)“*”號(hào)，全表共有個(gè)“*”號(hào)，再按列計(jì)算，由于每列恰有個(gè)“*”號(hào)，全表的“*”號(hào)數(shù)是個(gè)，因此含有的個(gè)集合，共作成個(gè)“集合對(duì)”，由于任兩個(gè)集合的交不是空集，故和式包含了所有的“集合對(duì)”，其中含有重復(fù)（因?yàn)橛行┘蠈?duì)可能不止一個(gè)公共元，有些元素可能屬于多個(gè)集合）據(jù)條件，集合組中的個(gè)集兩兩的交不空，它們構(gòu)成個(gè)不重

18、復(fù)的“集合對(duì)”，因此，即 ，據(jù)，則由，所以再證，反證法，若有，即對(duì)任何，皆有，這時(shí)將會(huì)導(dǎo)致所有；事實(shí)上，若有某個(gè)，即含有元素的集合不多于個(gè)，于是集合組中至少有個(gè)集不含，設(shè)不含的集合是，而含，記，由于，則，因此四個(gè)元素中，必有一個(gè)元素，例如，要屬于中至少三個(gè)集合，即屬于中至少四個(gè)集合，這與矛盾！于是所有；但這又導(dǎo)致，矛盾！所以，即再說(shuō)明，是可以取到的，為此，采用幾何構(gòu)造法，考慮如圖的五角星，它的個(gè)結(jié)點(diǎn)以及各邊中點(diǎn)，共得個(gè)點(diǎn)，分別標(biāo)志為，今構(gòu)造集合的個(gè)五元集如下：由五角星的外接圓上個(gè)點(diǎn)，五條邊上的各個(gè)點(diǎn)，五個(gè)形如的“十字架”上的個(gè)點(diǎn)，分別作為一個(gè)集，這樣共得個(gè)集，它們分別是：，因此，的最小值為（注

19、意，也可將集合換成集合，同樣可以確保任兩個(gè)集的交不空）、在一個(gè)圓周上給定十二個(gè)紅點(diǎn)；求的最小值，使得存在以紅點(diǎn)為頂點(diǎn)的個(gè)三角形，滿足：以紅點(diǎn)為端點(diǎn)的每條弦，都是其中某個(gè)三角形的一條邊解：設(shè)紅點(diǎn)集為：，過(guò)點(diǎn)的弦有條，而任一個(gè)含頂點(diǎn)的三角形，恰含兩條過(guò)點(diǎn)的弦，故這條過(guò)點(diǎn)的弦，至少要分布于個(gè)含頂點(diǎn)的三角形中；同理知，過(guò)點(diǎn)的弦，也各要分布于個(gè)含頂點(diǎn)的三角形中，這樣就需要個(gè)三角形，而每個(gè)三角形有三個(gè)頂點(diǎn)，故都被重復(fù)計(jì)算了三次，因此至少需要個(gè)三角形再說(shuō)明，下界可以被取到不失一般性，考慮周長(zhǎng)為的圓周，其十二等分點(diǎn)為紅點(diǎn)，以紅點(diǎn)為端點(diǎn)的弦共有條若某弦所對(duì)的劣弧長(zhǎng)為，就稱該弦的刻度為；于是紅端點(diǎn)的弦只有種刻度，

20、其中，刻度為的弦各條，刻度為的弦共條； 如果刻度為（）的弦構(gòu)成三角形的三條邊，則必滿足以下兩條件之一：或者；或者；于是紅點(diǎn)三角形邊長(zhǎng)的刻度組只有如下種可能：；下面是刻度組的一種搭配：取型各六個(gè)，型四個(gè)；這時(shí)恰好得到條弦，且其中含刻度為的弦各條，刻度為的弦共條；今構(gòu)造如下：先作型的三角形各六個(gè)，型的三角形三個(gè)，再用三個(gè)型的三角形來(lái)補(bǔ)充型六個(gè)：其頂點(diǎn)標(biāo)號(hào)為：；型六個(gè)：其頂點(diǎn)標(biāo)號(hào)為：；型六個(gè)：其頂點(diǎn)標(biāo)號(hào)為：；型三個(gè)：其頂點(diǎn)標(biāo)號(hào)為：；型三個(gè)：其頂點(diǎn)標(biāo)號(hào)為：（每種情況下的其余三角形都可由其中一個(gè)三角形繞圓心適當(dāng)旋轉(zhuǎn)而得）這樣共得到個(gè)三角形，且滿足本題條件，因此，的最小值為、在一個(gè)圓周上給定個(gè)點(diǎn)求最小的正

21、整數(shù)，使得以這個(gè)點(diǎn)為頂點(diǎn)的任意個(gè)三角形中，必存在兩個(gè)有公共邊的三角形解：先考慮兩兩無(wú)公共邊的三角形個(gè)數(shù)的最大值個(gè)點(diǎn)，每?jī)牲c(diǎn)連一條弦，共得條弦，若每條弦只屬于一個(gè)三角形，則這些弦至多能構(gòu)成兩兩無(wú)公共邊的三角形個(gè)數(shù)個(gè)，但若有個(gè)這樣的三角形，共得個(gè)頂點(diǎn)，則八邊形必有一頂點(diǎn)，至少屬于個(gè)三角形，設(shè)為，共頂點(diǎn)的個(gè)三角形，的對(duì)邊都是之中的兩點(diǎn)連線，其中必有一點(diǎn)，設(shè)為，出現(xiàn)了兩次，那么相應(yīng)的兩個(gè)三角形將有一條公共邊，這不可能；故另一方面，當(dāng)時(shí)，我們確實(shí)可以作出這樣的個(gè)三角形，使得其中任兩個(gè)三角形都無(wú)公共邊；注意這樣的個(gè)三角形，共產(chǎn)生個(gè)頂點(diǎn)，若使每點(diǎn)所參與的三角形個(gè)數(shù)都小于，那么每點(diǎn)恰好屬于個(gè)三角形，也就是說(shuō)，

22、每個(gè)點(diǎn)，恰與其余七點(diǎn)中的點(diǎn)有邊相連，而與另一點(diǎn)不連邊；考慮每點(diǎn)度數(shù)皆為的八階圖：為簡(jiǎn)明起見(jiàn)，取圓周的八等分點(diǎn)作為圖的八個(gè)頂點(diǎn)，作階完全圖，然后去掉其中條直徑，這樣共得條邊，且每點(diǎn)均屬于條邊；在由這些邊所構(gòu)成的三角形中，選取八個(gè)等腰三角形：以及它們兩兩無(wú)公共邊；（每一組的四個(gè)三角形，皆可由其中一個(gè)三角形繞圓心適當(dāng)旋轉(zhuǎn)而得到）因此，從而所求的最小值、將時(shí)鐘盤(pán)面上標(biāo)有數(shù)字的十二個(gè)點(diǎn)分別染上紅、黃、藍(lán)、綠四色，每色三個(gè)點(diǎn)，現(xiàn)以這些點(diǎn)為頂點(diǎn)構(gòu)作個(gè)凸四邊形，使其滿足：（）每個(gè)四邊形的四個(gè)頂點(diǎn)染有不同的顏色；（）對(duì)于其中任何三個(gè)四邊形，都存在某一色，染有該色的三個(gè)頂點(diǎn)所標(biāo)數(shù)字互不相同求的最大值解：為敘述方便

23、，改用分別表示這四種顏色，而同色的三點(diǎn)，則分別用；以及來(lái)表示今考慮其中一色，例如色；若在這個(gè)四邊形中，色點(diǎn)出現(xiàn)的次數(shù)分別為，則，設(shè)；如果，則；再考慮這個(gè)四邊形（其色頂點(diǎn)要么是，要么是），它們中色點(diǎn)出現(xiàn)的次數(shù)分別為，則，據(jù)對(duì)稱性，可設(shè)，則，即；繼續(xù)考慮這個(gè)四邊形（其色頂點(diǎn)要么是，要么是；色頂點(diǎn)要么是，要么是），它們中色點(diǎn)出現(xiàn)的次數(shù)分別為，則，據(jù)對(duì)稱性，可設(shè)，則，即；最后考慮這個(gè)四邊形，記為（其色頂點(diǎn)要么是，要么是；色頂點(diǎn)要么是，要么是；色頂點(diǎn)要么是，要么是），由于色點(diǎn)只有三個(gè)，故其中必有兩個(gè)四邊形，其色點(diǎn)相同，設(shè)的色點(diǎn)都為；那么，三個(gè)四邊形中，無(wú)論哪種顏色的頂點(diǎn)，所標(biāo)數(shù)字皆有重復(fù)，這與條件相矛盾

24、！因此，再說(shuō)明，最大值可以取到；采用構(gòu)造法，我們只要作出這樣的九個(gè)四邊形即可作三個(gè)“同心圓環(huán)圖”，給出標(biāo)號(hào)，并適當(dāng)旋轉(zhuǎn)相應(yīng)的圓，標(biāo)號(hào)對(duì)齊后，圖中的每根線（半徑）上的四個(gè)點(diǎn)分別表示一個(gè)四邊形的四個(gè)頂點(diǎn)顏色及其標(biāo)號(hào)，九條半徑共給出九個(gè)四邊形，且都滿足條件（）；再說(shuō)明，它們也滿足條件（）：從中任取三條半徑（三個(gè)四邊形）；如果三條半徑（三個(gè)四邊形）來(lái)自同一個(gè)圖，則除了色之外，其余每色的頂點(diǎn)，三數(shù)全有；如果三條半徑（三個(gè)四邊形）分別來(lái)自三個(gè)圖，則色的頂點(diǎn)，三數(shù)全有；如果三條半徑（三個(gè)四邊形）分別來(lái)自兩個(gè)圖：將三個(gè)圖分別稱為圖、圖、圖，每圖的三條半徑分別稱為“向上半徑”、“向左半徑”、“向右半徑”；且分別

25、記為來(lái)自兩個(gè)圖的三條半徑，如果“向上”、“向左”、“向右”三種半徑都有，那么相應(yīng)的三個(gè)四邊形，色的頂點(diǎn)，三數(shù)全有；如果三條半徑，只涉及兩個(gè)圖，兩個(gè)方位，將圖分別簡(jiǎn)記為，則按三個(gè)圖的搭配情況，可得下表：因此本題所求的的最大值為三、幾何構(gòu)造法、設(shè)有個(gè)正整數(shù)及，滿足：證明：可以從方格表中選出個(gè)方格，在選出的每格中各填寫(xiě)一個(gè)自然數(shù)，使得表中第行的填數(shù)和為，而第列的填數(shù)和為證：采用幾何構(gòu)造法，設(shè)，則為正整數(shù)，在坐標(biāo)系數(shù)第一象限作一個(gè)邊長(zhǎng)為的正方形，在上順次截出長(zhǎng)度為的線段，得到個(gè)分點(diǎn)，其中，；（稱為型線段）在上順次截出長(zhǎng)度為的線段，得到個(gè)分點(diǎn)，其中，；又在上順次截出長(zhǎng)度為的段，得到個(gè)分點(diǎn)，其中，；（稱為

26、型線段）在上順次截出長(zhǎng)度為的段，得到個(gè)分點(diǎn)，其中，；過(guò)諸點(diǎn)，分別作的垂線，再過(guò)點(diǎn)，分別作的垂線過(guò)第條型線段兩端點(diǎn)的垂線所夾矩形長(zhǎng)條稱為第個(gè)型條，過(guò)第條型線段兩端點(diǎn)的垂線所夾矩形長(zhǎng)條稱為第個(gè)型條，線段上的分點(diǎn)各有個(gè)（其中有些分點(diǎn)可能是重合），它們將線段，各分成段，每一段的長(zhǎng)度都是整數(shù)（重合的分點(diǎn)構(gòu)成的線段長(zhǎng)度為）；兩組垂線構(gòu)成了許多正方形，我們主要關(guān)注對(duì)角線在上且未被其它正方形所覆蓋的正方形，稱為單純正方形（有些正方形可能蛻化成一個(gè)點(diǎn)），這種正方形共有個(gè)，它們的邊長(zhǎng)皆為非負(fù)整數(shù)；現(xiàn)在我們這樣在方格表上填數(shù)：如果一個(gè)單純正方形夾在第個(gè)型條與第個(gè)型條中，則將正方形的邊長(zhǎng)填入方格表第行、列的交叉處；由

27、于這些單純正方形的對(duì)角線覆蓋了正方形的對(duì)角線，且互不重疊，所以第個(gè)型條中的單純正方形的邊長(zhǎng)之和恰等于第個(gè)型條的寬度，第個(gè)型條中的單純正方形的邊長(zhǎng)之和恰等于第個(gè)型條的寬度，即有，表中第行的填數(shù)和為，而第列的填數(shù)和為因此結(jié)論得證下面的例子是的情形、一百個(gè)正數(shù)滿足：，證明：中必有三數(shù)之和大于證：據(jù)對(duì)稱性，不妨設(shè)，只要證，；反證法，假若，作三個(gè)邊長(zhǎng)為的正方形，拼成一個(gè)矩形，再把邊長(zhǎng)為的小正方形一個(gè)接一個(gè)依次放入矩形中，恰好鋪成由到的一長(zhǎng)條，記為，據(jù)反證法假設(shè)知，小正方形都在大正方形內(nèi)，長(zhǎng)條含于正方形內(nèi)的這一部分，被的矩形所覆蓋，而落入大正方形中的部分當(dāng)被的矩形所覆蓋，落入大正方形中的部分當(dāng)被的矩形所覆

28、蓋，因此全體小正方形的面積和應(yīng)不大于三個(gè)矩形的面積和；另一方面，由于，我們可以在正方形中剪出的三個(gè)矩形；因此可以將矩形分別放置于大正方形中的處，于是，全體小正方形的面積和不大于正方形的面積，即，此為矛盾！因此假設(shè)不真，從而本題結(jié)論成立、平面上給定個(gè)點(diǎn)，無(wú)三點(diǎn)共線，現(xiàn)將每?jī)牲c(diǎn)用一線段連接，并在每條線段上配置一個(gè)箭頭，以給定點(diǎn)為頂點(diǎn)的三角形稱為“環(huán)形”的，如果從任一頂點(diǎn)出發(fā)，沿箭頭方向可環(huán)繞三角形周界行走一周，而返回原出發(fā)頂點(diǎn)；試求環(huán)形三角形個(gè)數(shù)的最大值與最小值解：配置箭頭后的三角形只有“環(huán)形”與“非環(huán)形”兩種形狀，因此，環(huán)形三角形個(gè)數(shù)非環(huán)形三角形個(gè)數(shù)全體三角形個(gè)數(shù)先求，我們注意到，一個(gè)三角形是“

29、非環(huán)形”的，當(dāng)且僅當(dāng)其三個(gè)頂點(diǎn)中，恰有一個(gè)頂點(diǎn)發(fā)出兩個(gè)箭頭，也有一個(gè)頂點(diǎn)收到兩個(gè)箭頭我們將“發(fā)自同一頂點(diǎn)的一對(duì)箭頭”或者“指向同一頂點(diǎn)的一對(duì)箭頭”統(tǒng)稱為一個(gè)“同型對(duì)”于是，一個(gè)“非環(huán)形”三角形恰有兩個(gè)“同型對(duì)”對(duì)于一個(gè)確定的頂點(diǎn)而言，關(guān)聯(lián)的每一個(gè)“同型對(duì)”，恰好產(chǎn)生一個(gè)“非環(huán)形”三角形設(shè)是任一個(gè)給定的點(diǎn)，以為端點(diǎn)的線段共有條，設(shè)點(diǎn)發(fā)出個(gè)箭頭，收到個(gè)箭頭，自發(fā)出的個(gè)箭頭，組成個(gè)同型對(duì)，收到的個(gè)箭頭，組成個(gè)同型對(duì)，因此關(guān)聯(lián)的同型對(duì)有個(gè)為求的最小值，即需求的最大值當(dāng)為奇數(shù)，則在時(shí)，有最大值；此時(shí)；當(dāng)為偶數(shù)，則在或時(shí)，有最大值；此時(shí)讓跑遍全部個(gè)點(diǎn)，得到個(gè)“非環(huán)形”三角形，由于每個(gè)“非環(huán)形”三角形恰有兩

30、個(gè)同型對(duì)，故均被計(jì)算了兩遍，因此，“非環(huán)形”三角形共有個(gè)，當(dāng)每個(gè)點(diǎn)所關(guān)聯(lián)的“非環(huán)形”三角形個(gè)數(shù)都取得最小值時(shí)，全體“非環(huán)形”三角形個(gè)數(shù)也取得最小值，所以，則此值可以取到，構(gòu)造法，考慮圓周的等分點(diǎn)，對(duì)于不經(jīng)過(guò)圓心的每條弦配置箭頭時(shí)，可使繞圓周成反時(shí)針?lè)较颍?，順著箭頭方向沿每條弦行走時(shí)，圓心總在左側(cè)），而對(duì)于經(jīng)過(guò)圓心的弦（直徑），箭頭方向可任意配置，這樣，每個(gè)點(diǎn)的出入箭頭數(shù)至多相差一個(gè)再求環(huán)形三角形個(gè)數(shù)的最小值，（注意上面的方法不能用于此情形，因?yàn)樯厦娴墓绞菍?duì)于每個(gè)點(diǎn)都使關(guān)聯(lián)的“非環(huán)形”三角形個(gè)數(shù)取得最小值時(shí)求得的）我們指出，環(huán)形三角形個(gè)數(shù)的最小值為構(gòu)造法，將個(gè)點(diǎn)分別標(biāo)號(hào)為，配置箭頭按小數(shù)指向

31、大數(shù)進(jìn)行、設(shè)的個(gè)七元子集滿足：、，；、對(duì)于的任何元子集，都存在某個(gè)，使得求這組子集個(gè)數(shù)的最小值解：采用“元素跟蹤”法，因中有個(gè)元素，其中含的元子集，共計(jì)（不重不漏）.此外，若元素在個(gè)子集中出現(xiàn)，每個(gè)有個(gè)元素，其中含的元子集有個(gè)，個(gè)這種子集共收集到這種元子集（在不同的元子集中，有些元子集可能會(huì)出現(xiàn)重復(fù)，這是因條件的緣故）（不漏但可重）.于是.因?yàn)檎麛?shù)，則.再?gòu)脑貍€(gè)數(shù)考慮，個(gè)元子集共得個(gè)元素（它們來(lái)自，且有重復(fù)）.另一方面，中的每個(gè)元素在諸中至少出場(chǎng)次，而這種有個(gè),故個(gè)集中的元素個(gè)數(shù)和至少是個(gè)（可重，但為“至少重”）所以，則.以下說(shuō)明確為所求的最小值。需構(gòu)造集的個(gè)元子集,使其覆蓋的全體元子集（以

32、下稱為“三角形”）.(注意，本題的構(gòu)造過(guò)程是一項(xiàng)比前一階段論證過(guò)程更為精細(xì)的工作，仍采用幾何構(gòu)造法，以便于檢驗(yàn)).先計(jì)算一下中的“三角形”個(gè)數(shù)，為個(gè).再分析的數(shù)字結(jié)構(gòu)，其中有個(gè)偶數(shù)，個(gè)奇數(shù).進(jìn)而對(duì)中的“三角形”按“頂點(diǎn)”分類.(偶 偶 偶)型三角形，共個(gè)；(偶 偶 奇)型三角形，共個(gè)；(奇 奇 偶)型三角形，共個(gè)；(奇 奇 奇)型三角形，共個(gè)為解決第一類(偶 偶 偶)型三角形，只須取即可.而為滿足，每個(gè)后續(xù)的至多只能含有個(gè)偶數(shù)，并且必需覆蓋所有后三類三角形.因此，這個(gè)集，每個(gè)集必須取三個(gè)偶數(shù)，四個(gè)奇數(shù).先考慮偶數(shù)搭配.順次將個(gè)偶數(shù)填寫(xiě)于圓周的個(gè)等分點(diǎn)上，易知圓內(nèi)接正邊形只有三種長(zhǎng)度的弦.將其搭

33、配成一個(gè)三角形，然后順時(shí)針旋轉(zhuǎn)次，得到個(gè)三角形：.這組三角形有特征：任二個(gè)三角形恰有一個(gè)公共頂點(diǎn)，而無(wú)公共邊；任一個(gè)偶點(diǎn)恰屬于三個(gè)三角形.每個(gè)三角形有三條邊，共得條偶頂線段.任二條皆不相同.它恰好窮盡了所有個(gè)二元的偶數(shù)子集.由于只有個(gè)偶頂三角形，為組成個(gè)元子集，每個(gè)偶頂三角形必須使用二次，稱為一對(duì)“重置偶三角”，對(duì)于“重置偶三角”，需要將個(gè)奇數(shù)分成互補(bǔ)的兩組，不能有公共元素,又因任兩個(gè)“相異偶三角”恰有一個(gè)公共元，因此，與之搭配的四元奇數(shù)集，至少允許有兩個(gè)相同元素.據(jù)此，我們來(lái)對(duì)個(gè)奇數(shù)構(gòu)成的集，設(shè)計(jì)種互補(bǔ)分拆，使之滿足條件.將個(gè)奇數(shù)順次填寫(xiě)于圓周的八等分點(diǎn)上，然后作種形狀的元分拆（四邊形分拆）

34、：十字分拆（正方形分拆）：半圓分拆（薄梯形分拆）：，矩形分拆：，梯形分拆（厚梯形分拆）：，易知，分拆有特征：同一分拆中的兩組奇數(shù)，無(wú)公共元素（互補(bǔ)）；不同分拆中的任二組奇數(shù)（任二個(gè)四邊形）恰有二個(gè)公共元（一條線段）；任一條線段（一個(gè)奇數(shù)對(duì)）恰好出現(xiàn)三次.每個(gè)完全四邊形有條邊，個(gè)四邊形共得條邊，而每條邊重復(fù)三次，故得條不同的邊.另一方面，八個(gè)奇數(shù)的集共有個(gè)二元奇子集.因此，這些四元奇數(shù)組窮盡了所有二元奇數(shù)子集.又知，每個(gè)四元組產(chǎn)生個(gè)三元子集，且任二個(gè)四元組沒(méi)有共同的三元子集（因至多一條公共邊）.故個(gè)四元組共得個(gè)三元奇子集.它們恰窮盡了所有個(gè)三元奇子集.下面，我們來(lái)完成后續(xù)個(gè)元子集的搭配.首先,只

35、要個(gè)四元集一齊用上,便完成了對(duì)所有的奇頂三角形的覆蓋；只要每一對(duì)“重置三角形”分別搭配一對(duì)互補(bǔ)的元分拆，便完成了對(duì)所有“偶偶奇”型三角形的覆蓋.在滿足前述情況的前提下，我們作出搭配，使之滿足對(duì)于全部“奇奇偶”型三角形（共個(gè)）的覆蓋.據(jù)前面的討論知，每個(gè)偶頂在七個(gè)三角形中出現(xiàn)三次，而每條“奇頂邊”在個(gè)四邊形中也出現(xiàn)三次.由對(duì)稱性，只要考慮元子集對(duì)于偶數(shù)和奇數(shù)對(duì)所形成的“奇奇偶”型三角形的覆蓋.采用“先入為主”的辦法.先從和入手.含的偶頂三角形有三個(gè)：和含的四邊形也有三個(gè)：和先讓它們?nèi)我鈱?duì)搭配，而讓其互補(bǔ)四邊形與相應(yīng)的重置偶頂三角形搭配，這樣得到六個(gè)元組：； （*）；不含的偶頂三角形有個(gè)，為，和，

36、而含的四邊形（四元組）也剩了個(gè)，為，和，今讓一對(duì)一搭配，而讓其互補(bǔ)四邊形與相應(yīng)的重置偶頂三角形搭配，于是得到個(gè)元組：，；，；，； （），；由（*）（）共得到個(gè)元子集.由于每一條奇頂線段（這種線段共條）在三個(gè)四邊形中出現(xiàn)，而與這三個(gè)四邊形搭配的三個(gè)偶頂三角形含有全部偶點(diǎn)（例如，與所在四邊形搭配的偶頂三角形為，這三個(gè)三角形含有全部個(gè)偶點(diǎn)，因此型三角形全被覆蓋，其余可類似檢查，全部檢驗(yàn)共次）.因此，個(gè)奇奇偶型三角形全被覆蓋.于是，個(gè)元集滿足條件，的最小值為.四、圖論、圖形、圖表構(gòu)造法、給定個(gè)正整數(shù)，若其中至少有對(duì)數(shù)互質(zhì)，證明：其中必存在四個(gè)數(shù)，滿足：證：采用圖形構(gòu)造法：用點(diǎn)分別代表這個(gè)正整數(shù)，若，則

37、令相應(yīng)點(diǎn)相鄰，于是得階簡(jiǎn)單圖，設(shè)點(diǎn)的度數(shù)為，據(jù)條件，圖至少有條邊，不妨設(shè)，圖恰有條邊，否則我們就去掉其中一些邊，并不影響問(wèn)題的性質(zhì)；與點(diǎn)相鄰的點(diǎn)有個(gè)，它們構(gòu)成個(gè)“點(diǎn)對(duì)”，據(jù)條件，；若記 ，則，由柯西不等式，因此，故在中必有兩個(gè)點(diǎn)，其所鄰接的點(diǎn)中，具有相同的一個(gè)“點(diǎn)對(duì)”，設(shè)為，即為四邊形，從而，、個(gè)正整數(shù)的和為，如果這個(gè)數(shù)既可分為和相等的個(gè)組，又可分為和相等的個(gè)組，求的最小值解：設(shè)分成的個(gè)組為，每組中的各數(shù)和皆為，稱這種組為類組；而分成的個(gè)組為，每組中的各數(shù)和皆為，稱這種組為類組顯然，每個(gè)項(xiàng)恰好屬于一個(gè)類組和一個(gè)類組，即同類組之間沒(méi)有公共項(xiàng)，如果兩個(gè)組中有兩個(gè)公共項(xiàng)，則可以將這兩個(gè)數(shù)合并為一個(gè)項(xiàng)

38、，這樣可使值減少，故不妨設(shè)，每對(duì)至多有一個(gè)公共項(xiàng)構(gòu)造圖論模型：今用點(diǎn)分別表示，而點(diǎn)表示組，如果組有公共項(xiàng)，則在相應(yīng)的點(diǎn)之間連一條邊，于是得二部圖，它恰有條邊和個(gè)頂點(diǎn)下面證明是連通圖如果圖的最大連通分支為，其頂點(diǎn)數(shù)少于，設(shè)在分支中，有個(gè)類頂點(diǎn)和個(gè)類頂點(diǎn)，其中，則在相應(yīng)的類組和類組中，類組中的每個(gè)數(shù)都要在某個(gè)類組中出現(xiàn)；而類組中的每個(gè)數(shù)也都要在某個(gè)類組中出現(xiàn)，（否則將有邊與分支外的頂點(diǎn)連接，發(fā)生矛盾），因此個(gè)類組中各數(shù)的和應(yīng)等于個(gè)類組中各數(shù)的和，即有，由此得，所以，矛盾！因此是連通圖于是圖至少有條邊，即；另一方面，我們可實(shí)際構(gòu)造一個(gè)具有項(xiàng)的數(shù)列，滿足本題條件例如取，（該數(shù)組有個(gè)取值為的項(xiàng)；個(gè)取值為

39、的項(xiàng)；另將其余七個(gè)拆成七對(duì)，其中四對(duì)，兩對(duì)，一對(duì)，又得到個(gè)項(xiàng)），于是，每個(gè)類組可由一個(gè)，一個(gè)，或者由一個(gè)，添加一對(duì)和為的項(xiàng)組成；這樣共得個(gè)類組，每組各數(shù)的和皆為；為了獲得和為的個(gè)類組，可使各成一組，其余的數(shù)可以拼成八個(gè)類組：的組四個(gè)，的組兩個(gè)，的組一個(gè)，的組一個(gè)故的最小值為 、設(shè)，求最小的正整數(shù)，使得的任一個(gè)元子集中，都存在兩個(gè)不同的數(shù)和，滿足：解：設(shè)中不同的數(shù)和，滿足：，記，有，其中為正整數(shù)，且，則，由，得，又由得，所以從而 ，則，因?yàn)榛ギ?，則，又由互異，且由，則，即，于是 ，可取不妨設(shè)，討論不同情況、若，則，由，則，可取，所以，；、當(dāng)，則，由，則，可取，；、當(dāng)，則或，前者可取，后者可取，；

40、、當(dāng)，則，；、當(dāng)，則，故；、當(dāng)，則，因，去掉這組，；、當(dāng)，則，去掉后兩組，則以上我們共得到個(gè)數(shù)對(duì)，其中每個(gè)數(shù)對(duì)都滿足：為了找出滿足條件的最小的，先求最大的，使得存在的元子集，其中任一對(duì)數(shù)都不滿足條件為此，構(gòu)作階圖，以中的數(shù)為頂點(diǎn)，如果兩數(shù)屬于以上數(shù)對(duì)，則令相鄰，于是圖恰有條邊（圖中的孤立點(diǎn)未標(biāo)出）從中刪去一些點(diǎn)，使得圖中的邊一起被刪去，則至少要?jiǎng)h去個(gè)點(diǎn)，例如將點(diǎn)集中的點(diǎn)刪去，這時(shí)，圖還剩下個(gè)點(diǎn)，由這個(gè)數(shù)作成集合，則中不含以上任一個(gè)數(shù)對(duì)即中任一個(gè)數(shù)對(duì)都不滿足條件因此，故所求的最小數(shù)以下證，滿足條件首先從圖中取條兩兩無(wú)公共頂點(diǎn)的邊（個(gè)數(shù)對(duì)）：，（其中每條邊恰有一個(gè)點(diǎn)在集中），這條邊的頂點(diǎn)共有個(gè)，相

41、應(yīng)的個(gè)數(shù)構(gòu)成的元子集；中其余的數(shù)共有個(gè)，它們構(gòu)成子集；今從中任取一個(gè)元子集，則至多有個(gè)數(shù)取自中，也就是至少有個(gè)數(shù)取自，其中必有兩個(gè)數(shù)取自上述個(gè)數(shù)對(duì)中的同一對(duì)，設(shè)為，則因此，滿足條件的最小的值為、數(shù)學(xué)奧林匹克集訓(xùn)隊(duì)中共有名隊(duì)員，其中每人在隊(duì)中具有同樣多的朋友，已知在一次考試中，所有人的得分各不相同；若某個(gè)隊(duì)員在他的朋友圈中比多數(shù)人的得分都高，則稱該隊(duì)員為“高手”，問(wèn)集訓(xùn)隊(duì)中至多有幾名“高手”？解：設(shè)每名隊(duì)員有個(gè)朋友，而這次考試總共產(chǎn)生了個(gè)“高手”，隊(duì)中成績(jī)最好的一名隊(duì)員，在他的個(gè)“朋友對(duì)”中成績(jī)也是最好的，當(dāng)然是“高手”；而其余的每個(gè)“高手”，都至少在其個(gè)朋友對(duì)中，成績(jī)占優(yōu)所以“高手”們至少一共

42、在個(gè)朋友對(duì)成績(jī)占優(yōu)由于任一個(gè)“朋友對(duì)”至多為“高手”作一次貢獻(xiàn)，故不會(huì)被重復(fù)計(jì)算，因此上述數(shù)目不會(huì)超過(guò)集訓(xùn)隊(duì)中“朋友對(duì)”的總數(shù)，即（這相當(dāng)于一個(gè)階圖，每點(diǎn)的度數(shù)為，其邊數(shù)為）所以，故得 另一方面，集訓(xùn)隊(duì)中比最差的“高手”的成績(jī)還差的隊(duì)員人數(shù)不多于個(gè)（其中是“高手”總數(shù)），由于最差的“高手”也至少勝了人，所以，即 代入式，并注意的右邊是的增函數(shù)，則得到，即 ， 也就是 ，（注意），則滿足及條件的正整數(shù)的最大值是，即“高手”數(shù)不超過(guò)個(gè)；另一方面，我們可說(shuō)明，個(gè)“高手”的情況是可能的，采用構(gòu)造法：用表示隊(duì)員的排名（成績(jī)好的排名在前），當(dāng)時(shí)，由得，即每人恰有個(gè)朋友；今列出一張的表，并這樣定義朋友關(guān)系：若某對(duì)學(xué)生為朋友，當(dāng)且僅當(dāng)滿足以下三情形之一：、兩人同在第一行；、兩人在同一列，但其中一人位于最下面一行；、兩人分別在相鄰的兩行，但是不同列；這樣，每人恰有個(gè)朋友，并且前名都是“高手”五、模型構(gòu)造法、（售票問(wèn)題）個(gè)游客排隊(duì)購(gòu)買(mǎi)參觀票，每張票價(jià)元，其中人各持有一張?jiān)獛?，另外人各持有一張?jiān)獛牛_(kāi)初時(shí)售票機(jī)中無(wú)零錢(qián)可找，試確定，使得不發(fā)生售