Question

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

Answer 1

【答案】最小的n是2795

【解析】

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

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

設G=(V，E)是一個簡單圖，且G是連通的，

則G含有個兩兩無公共邊的角(這里[a]表示實數a的整數部分).

引理的證明：對E的元素個數|E|歸納證明.

當|E|=0，1，2，3時，結論顯然成立.

下面假設|E|≥4，并且結論在|E|較小時均成立.

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

對這個連通分支應用歸納假設即得結論成立.

考慮G中的最長路，其中是互不相同的頂點.

因為G連通，故k≥3.

情形1：.

由于P是最長路，v1的鄰點均在中，設，其中3≤i≤k.

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

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

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

情形2：，.

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

因此有一個連通分支含有條邊.

情形3：，且v2與中某個點相鄰.

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

因此有一個連通分支含有條邊.

情形4：，且v2與某個相鄰.

由于P是最長路，故u的鄰點均在之中.

因是一個角，在G中刪去這兩條邊，則v1是孤立點.

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

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

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

引理獲證.

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

首先證明n≥2795.

設.

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

由上述構造可見，G中的任何一個角必須使用相連的邊，

因此至多有個兩兩無公共邊的角.

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

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

設G有k個連通分支，分別有個點，及條邊.

下面證明中至多有979個奇數.

反證法，假設中有至少980個奇數由于是奇數，

故中至少有981個奇數，k≥981.

不妨設都是奇數，顯然.

令，則有，

故①

利用組合數的凸性，即對x≥y≥3，有，

可知當m1，…，m980，m由980個2以及一個59構成時，取得最大值.

于是，

這與①矛盾.從而中至多有979個奇數.

對每個連通分支應用引理，可知G中含有N個兩兩無公共邊的角，

其中.

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