设在平面上有 $n$ 个给定的点，求证：其中距离为 $1$ 的点的对数不超过 $\dfrac{n}{4}+\dfrac{\sqrt{2}}{2}n^{\frac{3}{2}}$．
【难度】
【出处】
无
【标注】
【答案】
略
【解析】
把 $n$ 个点视为图 $G$ 的顶点，记 $V={v_1,v_2,\cdots,v_n}$ 为图 $G$ 的顶点集，在距离为 $1$ 的两点之间连一边，则 $2e=d(v_1)+d(v_2)+\cdots+d(v_n)$．
用 $C_i$ 表示以 $v_i$ 为圆心，半径为 $1$ 的圆，这 $n$ 个圆两两交点总数不超过 $2C_n^{2}=n(n-1)$ 个．
另一方面，若 $v_k,v_j$ 与 $v_i$ 相邻，则 $v_i\in C_k\cap C_j$，因此 $v_i$ 作为 $C_1,C_2,\cdots,C_n$ 中两圆的交点恰好被计数了 $C_{d(v_i)}^{2}$ 次，故 $C_{d(v_1)}^2+C_{d(v_2)}^2+\cdots+C_{d(v_n)}^2\leqslant 2C_n^2=n(n-1)$．
由Cauchy不等式，有 $C_{d(v_1)}^2+C_{d(v_2)}^2+\cdots+C_{d(v_n)}^2\geqslant dfrac{2}{n}e^2-e$．
由上面两个式子得 $dfrac{2}{n}e^2-e\leqslant n(n-1)$，即 $2e^2-ne-n^2(n-1)\leqslant 0$．
解得 $e\leqslant \dfrac{n}{4}+\dfrac{\sqrt{2}}{2}n^{\frac{3}{2}}$．
用 $C_i$ 表示以 $v_i$ 为圆心，半径为 $1$ 的圆，这 $n$ 个圆两两交点总数不超过 $2C_n^{2}=n(n-1)$ 个．
另一方面，若 $v_k,v_j$ 与 $v_i$ 相邻，则 $v_i\in C_k\cap C_j$，因此 $v_i$ 作为 $C_1,C_2,\cdots,C_n$ 中两圆的交点恰好被计数了 $C_{d(v_i)}^{2}$ 次，故 $C_{d(v_1)}^2+C_{d(v_2)}^2+\cdots+C_{d(v_n)}^2\leqslant 2C_n^2=n(n-1)$．
由Cauchy不等式，有 $C_{d(v_1)}^2+C_{d(v_2)}^2+\cdots+C_{d(v_n)}^2\geqslant dfrac{2}{n}e^2-e$．
由上面两个式子得 $dfrac{2}{n}e^2-e\leqslant n(n-1)$，即 $2e^2-ne-n^2(n-1)\leqslant 0$．
解得 $e\leqslant \dfrac{n}{4}+\dfrac{\sqrt{2}}{2}n^{\frac{3}{2}}$．
答案
解析
备注
