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.