平面点集问题

ftg1029

平面上任给200个不同的点，证明其中距离为单位长的点的对数小于2050。

本因坊算帐

刚看到这个论坛，挺有意思的。大家好！ 我是新人，请多关照

这个题目……  我想了一下，并没有解决，但给出了一个粗略的上下界，写出来抛砖引玉吧

设 f（n）为平面上n个不同点所能包含的单位长的点对数的最大值。例如 f（2）=1，f（3）=3，f（4）=5 等等
原题目要证明： f（200） 不超过 2050

我的思路是：

引理1）对于任一点A，设距离A为单位长的点为：A1，A2，A3…… Ap，共p个点；对于另一点B，距离B为单位长的点为：B1，B2，B3……Bq，共q个点。任取A1……Ap中三点｛Ai1，Ai2，Ai3｝和B1……Bq中三点｛Bj1，Bj2，Bj3｝，则该两个三点集不可能完全相同。
证：否则，Ai1 Ai2 Ai3构成的圆即为Bj1，Bj2，Bj3构成的圆，前者圆心为A，后者圆心为B，推出AB重合，不符合题意。引理1证毕

设平面n个不同点，其中有f（n）个距离为单位长的点对。

定义1）考虑全部n个点中，满足三点所在的圆半径为单位长的所有三点集的个数 M。

设n个点为 P1，P2……Pn，设与Pk距离为单位长的点的个数为 Nk，容易证明

Nk对k=1……n求和等于 2f（n）          （1）

而在与Pk距离为单位长的Nk个点中，每一个三点集都是符合定义1）要求的点集。并且根据引理1，当k对1……n遍历的时候，所有的三点集不会重复。
因此，有

M 大于等于  C（Nk，3） 对k=1……n 求和，
即    Nk（Nk-1）（Nk-2）/6 对k=1……n求和                  （2）
根据等式（1），不难看出，当所有Nk都平均取值的时候，即 Nk = 2f（n）/n 时，（2）可以取到最小值，
即：

M 大于等于  n*（2f（n）/n） * （2f（n）/n - 1 ）*（2f（n）/n - 2 ）/6                （3）

另一方面，显然有 M 不超过 C（n，2） = n*（n-1）*（n-2）/6            （4）

（3）（4）联立，可以解得：
f（n） 不超过  n/2 * （1+ ((n-1)*(n-1))的1/3次方）
将n=200代入上式，可以得到f（200）不超过 3600. 这个结果距离题目的 2050 还稍微大了一点，不太准确…… 还得再琢磨琢磨

另外，从构造的角度，可以证明 f（200）大于 1000，构造的方法比较繁琐，就不罗列了

winxos

2# 本因坊算帐
本论坛支持使用LaTeX直接排版，语法请参考：http://bbs.emath.ac.cn/viewthread.php?tid=212