平面上n个点两两距离中有k个不同值,求证k>=√(n-1)-1

Question

平面上 n个点两两距离中有k个不同值,求证k>=√(n-1) -1

Answer 1

平面上 n个点两两距离中有k个不同值,设最小那个为N(k).
把最外围的点连起来,若至少有一个点在其内,如果在其内再添上一点,则N(k)至少会多2.
如果添在外围的边上,经过适当调整,则N(k)至多会多出1.
所以若N(k),则n个点都是凸多边形的顶点,且凸多边形为正n边形.
此时 N(k)=[n/2] ([x]为取整函数）
[n/2]>n/2-1=(n-1 -1)/2=[(√(n-1) -1)(√(n-1) +1)]/2
>=√(n-1) -1
因为 n>=2,(√(n-1) +1)/2>=1