MathLabs

第5题

给定平面上 n>4n>4 个点且任意三点不共线。证明:以这些点为顶点的凸四边形至少有 (n−32)\binom{n-3}{2} 个。
第 4/6 步：得到初步下界
上一步下一步
Q≥(n5)n−4=n(n−1)(n−2)(n−3)120Q\ge\frac{\binom n5}{n-4}=\frac{n(n-1)(n-2)(n-3)}{120}
详细分析

令 QQ 为凸四边形数。对(五点集,其中选出的四边形)作双重计数,得到上式。