已知一平面内有 $n$ 个点 $(n>4)$，其中任三点都不共线．求证：至少可以找到 $C_{n-3}^{2}$ 个以上述点为顶点的凸四边形．（蒙古）
【难度】
【出处】
1969年第11届IMO试题
【标注】
【答案】
略
【解析】
证法一
当 $n=5$ 时，考虑这 $5$ 个点的凸包．
若这 $5$ 个点的凸包是凸五边形，或是凸四边形，则这 $5$ 个点中可以找到 $1$ 个以上述点为顶点的凸四边形．
若这 $5$ 个点的凸包是三角形，不妨设 $\triangle ABC$，另外两点 $D,E$ 在 $\triangle ABC$ 内部，且不妨设直线 $DE$ 与边 $AB$ 不想交，如图，则 $ABDC$ 就是一个凸四边形．
所以，$n=5$ 时命题成立．
当 $n\geqslant 5$ 时，$n$ 个点中有 $C_n^5$ 个 $5$ 点组，每组中至少有一个以此组中的点为顶点的凸四边形，而每一个四边形至多被重复计算 $n-4$ 次，于是不同的凸四边形个数至少有 $\dfrac{C_n^5}{n-4}=\dfrac{n(n-1)(n-2)(n-3)}{5!}$．下面证明 $\dfrac{n(n-1)(n-2)(n-3)}{120}\geqslant C_{n-3}^2$，即 $n(n-1)(n-2)\geqslant 60(n-4)$．①
当 $n=6,7,8$ 时，分别有 $6\times 5\times 4\geqslant 60\times 2,7\times 6\times 5\geqslant 60\times 3,8\times 7\times 6\geqslant 60\times 4$，① 式成立．当 $n\geqslant 9$ 时，有 $n(n-1)(n-2)\geqslant 9\times 8\times (n-4)>60(n-4)$，故 ① 式成立．
从而命题得证．
证法二
由于这 $n$ 个点中任三点都不共线，故有 $C_n^3$ 个三角形，其中面积最大的一个三角形记为 $\triangle ABC$（若面积最大的三角形不止一个，则任取一个记为 $\triangle ABC$），分别过点 $A,B,C$ 作对边的平行线，得 $\triangle A^\prime B^\prime C^\prime $，如图所示．则此 $n$ 个点均在 $\triangle A^\prime B^\prime C^\prime$ 的内部或边界上．若不然，设点 $P$ 在 $\triangle A^\prime B^\prime C^\prime$ 外，不妨设点 $P$ 与 $AB$ 在 $A^\prime B^\prime$ 的两侧，则 $S_{\triangle PAB}>S_{\triangle CAB}$，这与 $S_{\triangle ABC}$ 最大矛盾．
从 $n-3$ 个点（除 $A,B,C$ 外）中任取两点 $D,E$，它们必在 $\triangle A^\prime B^\prime C^\prime$ 内或边界上，线段 $DE$ 与边 $AB,BC,CA$，三者中至少有一条不相交，不妨设与 $AB$ 不相交，则 $ABDE$ 是一凸四边形．
所以，至少有 $C_{n-3}^2$ 个凸四边形．
当 $n=5$ 时，考虑这 $5$ 个点的凸包．
若这 $5$ 个点的凸包是凸五边形，或是凸四边形，则这 $5$ 个点中可以找到 $1$ 个以上述点为顶点的凸四边形．
若这 $5$ 个点的凸包是三角形，不妨设 $\triangle ABC$，另外两点 $D,E$ 在 $\triangle ABC$ 内部，且不妨设直线 $DE$ 与边 $AB$ 不想交，如图，则 $ABDC$ 就是一个凸四边形．
所以，$n=5$ 时命题成立．当 $n\geqslant 5$ 时，$n$ 个点中有 $C_n^5$ 个 $5$ 点组，每组中至少有一个以此组中的点为顶点的凸四边形，而每一个四边形至多被重复计算 $n-4$ 次，于是不同的凸四边形个数至少有 $\dfrac{C_n^5}{n-4}=\dfrac{n(n-1)(n-2)(n-3)}{5!}$．下面证明 $\dfrac{n(n-1)(n-2)(n-3)}{120}\geqslant C_{n-3}^2$，即 $n(n-1)(n-2)\geqslant 60(n-4)$．①
当 $n=6,7,8$ 时，分别有 $6\times 5\times 4\geqslant 60\times 2,7\times 6\times 5\geqslant 60\times 3,8\times 7\times 6\geqslant 60\times 4$，① 式成立．当 $n\geqslant 9$ 时，有 $n(n-1)(n-2)\geqslant 9\times 8\times (n-4)>60(n-4)$，故 ① 式成立．
从而命题得证．
证法二
由于这 $n$ 个点中任三点都不共线，故有 $C_n^3$ 个三角形，其中面积最大的一个三角形记为 $\triangle ABC$（若面积最大的三角形不止一个，则任取一个记为 $\triangle ABC$），分别过点 $A,B,C$ 作对边的平行线，得 $\triangle A^\prime B^\prime C^\prime $，如图所示．则此 $n$ 个点均在 $\triangle A^\prime B^\prime C^\prime$ 的内部或边界上．若不然，设点 $P$ 在 $\triangle A^\prime B^\prime C^\prime$ 外，不妨设点 $P$ 与 $AB$ 在 $A^\prime B^\prime$ 的两侧，则 $S_{\triangle PAB}>S_{\triangle CAB}$，这与 $S_{\triangle ABC}$ 最大矛盾．
从 $n-3$ 个点（除 $A,B,C$ 外）中任取两点 $D,E$，它们必在 $\triangle A^\prime B^\prime C^\prime$ 内或边界上，线段 $DE$ 与边 $AB,BC,CA$，三者中至少有一条不相交，不妨设与 $AB$ 不相交，则 $ABDE$ 是一凸四边形．所以，至少有 $C_{n-3}^2$ 个凸四边形．
答案
解析
备注
