第3题

设

n

和

k

为正整数,

S

是平面上的

n

个点集,且

S

中任意三点不共线。假设对每个

P\in S

,至少有

k

个

S

中的点与

P

等距。证明

k<\frac12+\sqrt{2n}

第 5/5 步：与三点不共线条件矛盾

通俗地说

矛盾完成了双计数:过多的等距对称性必然强迫出现禁忌的共线。

\text{Contradiction: }P_1,P_2,P_3\text{ are collinear, so }k<\frac12+\sqrt{2n}

详细分析

同一垂直平分线上的三个见证点共线,这与 $S$ 中任意三点不共线的假设矛盾。因此反设不可能,所以 $k<\frac12+\sqrt{2n}$ .