[组合] $n^2$个点最大距离是1，求证存在两点距离不超过$\sqrt{2}/n$

abababa

平面上有$n^2$个点，任意两点间的最大距离是$1$，求证存在距离不超过$\frac{\sqrt{2}}{n}$的两点，其中$n \ge 2$

realnumber

由题意，平移任意距离为1的平行线，总可以使得这$n^2$个点在这组平行线之间，
再作与这组平行线垂直的一组平行线，距离还是1，通过平移可以使得$n^2$个点在边长为1的正方形内，分别添n-1条平行线这个正方形等分成$n^2$个格子，
转动（不一定凑巧绕固定点转动，而是连转带滑 ），使得某点在添加的某条线上，这样相当于$n^2+1$个点，在$n^2$个正方形内，由抽屉原理
某一小正方形内有2点，这2点符合题目所要求的.
显然这个距离不是下确界，当n较大时.

abababa

回复 2# realnumber
我没看懂这个证明，转动时会不会有点被转到正方形外部呢？

abababa

发一位网友的证明，他的$n=3$时的证明还没写完，先发$n \neq 3$时的证明

下载 (29.84 KB)

2015-8-1 19:56

abababa

下载 (44.67 KB)

2015-8-1 20:01

realnumber

回复 3# abababa


    转动平行线的方向，重新取正方形

abababa

回复 4# abababa
给这楼的证明配个图

下载 (9.56 KB)

2015-8-1 20:27

abababa

回复 6# realnumber
如果转动平行线的方向，而不转动大正方形的方向，最后就不能构成小的正方形了吧？我还是没理解。能请配个图详细说明一下吗？

realnumber

转动平行线方向，再构成大正方形，再形成小的正方形。

abababa

回复 9# realnumber
这样可以从一开始就选择正确的方向，构成大正方形，其实和没转动是一样的

realnumber

不转动不好说明为什么在添加的2(n-1)条平行线上存在点.
万一转过头的的话，转的角度太大了.

abababa

回复 11# realnumber
我还是不太明白，是指这样转动吗？使一些点在分割线上，但是这样就有点被转出正方形了。能请画个具体的图来说明吗？就以简单点的$3 \times 3$个点为例

下载 (4.41 KB)

2015-8-1 23:24

realnumber

哎，.......不是说先转平行线，再正方形吗？
你画的图，第2个不对；万一转过头的话，调整啊，就象根的存在定理，连续，有正有负，那么一定存在根，但说不出具体在哪.

abababa

回复 13# realnumber
我明白你的意思了，就是说通过这样的转动，使得内部有一条分割线上有一个点，这点同时属于两个小方格。
但必须要证明确实存在这样的转动，能使转动后再画出的大正方形仍然能包含所有点，这个还需要证明。

下载 (19.72 KB)

2015-8-2 10:51

realnumber

距离为1的任意方向的平行线条，总存在一组包含所有点吧，1楼都说明了.
还特别指出连转带滑.
你觉得哪些还要补充的，要不你来补完？

abababa

回复 15# realnumber
是存在一组没错，就像14楼图中那样，有一个点在角上，存在一组但并不能使分割线上一定存在点。
如果分割线上存在点的情况下，我觉得就要证明由这种方向构造的大正方形必定能包含所有点。可能是我还没理解这个证明吧。
其实我觉得如果说任意一组距离为$1$的平行线都能包含所有点，意思应该是一个直径为$1$的圆必能包含所有点吧。

realnumber

边上有没有点不重要，转动的目的是为了内部再次添加的平行线上有点.
又，直径为1的圆什么的，不对吧.比如边长为1的正三角形三顶点.

abababa

回复 17# realnumber

我试了，这是不成立的，为了方便我按比例放大了，四点坐标是$A(-4,4),B(-1.42,-3.08),C(2.86,-3.18),D(3.1,3.08)$，当其中某个点在内部的分割线上时，应该能用边长是$8$的大正方形全部包含。
如果内部的分割线上有点，不能保证一定能作出这样的大正方形包含所有的点。如下图，只有4个点$A,B,C,D$，现在穷举，先让$B$在内部的分割线上，调整$E$的位置，让这个分割线取所有的方向，不能让这四个点都在大正方形内部，之后我又试了点$A,C,D$，也是不能作出这样的大正方形。

下载 (10.64 KB)

2015-8-2 18:16

realnumber

确认下放大的比例系数？是8倍？看来是n=2吧，我也来验证下，最好附加个你画的几何画板文件.
楼上AC=9.9已经不是8了

abababa

回复 19# realnumber
是的，这个距离已经超过1了。但我仍然觉得这没能证明所有点都一定在正方形内部。
我现在想用反证法证明，过内部一点$A$作一组距离为$\frac{1}{n}$的$n+1$条平行线和与这组平行线垂直的另一组$n+1$条平行线，组成$n \times n$的网格，假设有一点$B$在网格外部，能不能导出什么矛盾。