Question

【題目】設(shè)V是空間中2019個(gè)點(diǎn)構(gòu)成的集合，其中任意四點(diǎn)不共面某些點(diǎn)之間連有線段，記E為這些線段構(gòu)成的集合.試求最小的正整數(shù)n，滿足條件：若E至少有n個(gè)元素，則E一定含有908個(gè)二元子集，其中每個(gè)二元子集中的兩條線段有公共端點(diǎn)，且任意兩個(gè)二元子集的交為空集.

Answer 1

【答案】最小的n是2795

【解析】

先證明一個(gè)引理：設(shè)G=(V，E)是一個(gè)簡(jiǎn)單圖，且G是連通的，則G含有個(gè)兩兩無(wú)公共邊的角.再利用引理和反證法，結(jié)合組合數(shù)的凸性即可求得結(jié)果.

為了敘述方便，稱一個(gè)圖中的兩條相鄰的邊構(gòu)成一個(gè)“角”，先證明一個(gè)引理：

設(shè)G=(V，E)是一個(gè)簡(jiǎn)單圖，且G是連通的，

則G含有個(gè)兩兩無(wú)公共邊的角(這里[a]表示實(shí)數(shù)a的整數(shù)部分).

引理的證明：對(duì)E的元素個(gè)數(shù)|E|歸納證明.

當(dāng)|E|=0，1，2，3時(shí)，結(jié)論顯然成立.

下面假設(shè)|E|≥4，并且結(jié)論在|E|較小時(shí)均成立.

只需證明，在G中可以選取兩條邊a、b構(gòu)成一個(gè)角，在G中刪去a、b這兩條邊后，剩下的圖含有一個(gè)連通分支包含|E|－2條邊.

對(duì)這個(gè)連通分支應(yīng)用歸納假設(shè)即得結(jié)論成立.

考慮G中的最長(zhǎng)路，其中是互不相同的頂點(diǎn).

因?yàn)?/span>G連通，故k≥3.

情形1：.

由于P是最長(zhǎng)路，v1的鄰點(diǎn)均在中，設(shè)，其中3≤i≤k.

則是一個(gè)角，在E中刪去這兩條邊.

若v1處還有第三條邊，則剩下的圖是連通的；

若v1處僅有被刪去的兩條邊，則v1成為孤立點(diǎn)，其余頂點(diǎn)仍互相連通.總之在剩下的圖中有一個(gè)連通分支含有|E|－2條邊.

情形2：，.

則是一個(gè)角，在G中刪去這兩條邊后，都成為孤立點(diǎn)，其余的點(diǎn)互相連通，

因此有一個(gè)連通分支含有條邊.

情形3：，且v2與中某個(gè)點(diǎn)相鄰.

則是一個(gè)角，在G中刪去這兩條邊后，v1成為孤立點(diǎn)，其余點(diǎn)互相連通，

因此有一個(gè)連通分支含有條邊.

情形4：，且v2與某個(gè)相鄰.

由于P是最長(zhǎng)路，故u的鄰點(diǎn)均在之中.

因是一個(gè)角，在G中刪去這兩條邊，則v1是孤立點(diǎn).

若處僅有邊uv2，則刪去所述邊后u也是孤立點(diǎn)，而其余點(diǎn)互相連通.

若u處還有其他邊uvi，3≤i≤k，則刪去所述邊后，除v1外其余點(diǎn)互相連通.

總之，剩下的圖中有一個(gè)連通分支含有條邊.

引理獲證.

回到原題，題中的V和E可看作一個(gè)圖G=(V，E)

首先證明n≥2795.

設(shè).

在中，首先兩兩連邊，再刪去其中15條邊(例如)，共連了條邊，則這61個(gè)點(diǎn)構(gòu)成的圖是連通圖.再將剩余的201－61=1958個(gè)點(diǎn)配成979對(duì)，每對(duì)兩點(diǎn)之間連一條邊，則圖G中一共連了1815+979=2794條線段.

由上述構(gòu)造可見(jiàn)，G中的任何一個(gè)角必須使用相連的邊，

因此至多有個(gè)兩兩無(wú)公共邊的角.

故滿足要求的n不小于2795.

另一方面，若|E|≥2795，可任意刪去若干條邊，只考慮的情形.

設(shè)G有k個(gè)連通分支，分別有個(gè)點(diǎn)，及條邊.

下面證明中至多有979個(gè)奇數(shù).

反證法，假設(shè)中有至少980個(gè)奇數(shù)由于是奇數(shù)，

故中至少有981個(gè)奇數(shù)，k≥981.

不妨設(shè)都是奇數(shù)，顯然.

令，則有，

故①

利用組合數(shù)的凸性，即對(duì)x≥y≥3，有，

可知當(dāng)m1，…，m980，m由980個(gè)2以及一個(gè)59構(gòu)成時(shí)，取得最大值.

于是，

這與①矛盾.從而中至多有979個(gè)奇數(shù).

對(duì)每個(gè)連通分支應(yīng)用引理，可知G中含有N個(gè)兩兩無(wú)公共邊的角，

其中.

綜上，所求最小的n是2795.