设 $n$ 和 $k$ 是正整数，$S$ 是平面上 $n$ 个点的集合．满足
（1）$S$ 任何三点都不共线；
（2）对 $S$ 中每一点 $P,S$ 中至少存在 $k$ 个点与 $P$ 距离相等．
求证：$k<\dfrac{1}{2}+\sqrt{2n}$．（荷兰）
（1）$S$ 任何三点都不共线；
（2）对 $S$ 中每一点 $P,S$ 中至少存在 $k$ 个点与 $P$ 距离相等．
求证：$k<\dfrac{1}{2}+\sqrt{2n}$．（荷兰）
【难度】
【出处】
1989年第30届IMO试题
【标注】
【答案】
略
【解析】
由条件（2）知，对 $S$ 中的每一点 $P$，至少有 $C_k^2$ 对由 $S$ 中两点 $(A,B)$ 组成的点对，使得点 $P$ 在线段 $AB$ 的中垂线上，因此，共有 $nC_k^2$ 对这样的点对．
另一方面，由（1）知，任何一个这样的点对至多被计算两次（否则就有三点共线了），而 $S$ 中由两点组成的点对有 $C_n^2$ 个，所以 $nC_k^2\leqslant 2C_n^2$，
即 $nk(k-1)\leqslant 2n(n-1)$
$k^2-k-2(n-1)\leqslant 0$
$k\leqslant \dfrac{1}{2}(1+\sqrt{8n-7})<\dfrac{1}{2}(1+\sqrt{8n})=\dfrac{1}{2}+\sqrt{2n}$
另一方面，由（1）知，任何一个这样的点对至多被计算两次（否则就有三点共线了），而 $S$ 中由两点组成的点对有 $C_n^2$ 个，所以 $nC_k^2\leqslant 2C_n^2$，
即 $nk(k-1)\leqslant 2n(n-1)$
$k^2-k-2(n-1)\leqslant 0$
$k\leqslant \dfrac{1}{2}(1+\sqrt{8n-7})<\dfrac{1}{2}(1+\sqrt{8n})=\dfrac{1}{2}+\sqrt{2n}$
答案
解析
备注
