平面点集问题
平面上任给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，构造的方法比较繁琐，就不罗列了 2# 本因坊算帐
本论坛支持使用LaTeX直接排版，语法请参考：http://bbs.emath.ac.cn/viewthread.php?tid=212
页:
[1]