免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 组合几何

平面上有n个点,从中任取三个点,其中必有两个点距离为1.求n的最大值
猜了几个小时,貌似是6,不过不会证明,也不知道对不对.想用图论做,奈何水平不佳操作不了.请各位赐教
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
= =

有大师解决吗...

TOP

本帖最后由 realnumber 于 2019-6-6 09:15 编辑

QQ截图20190605232352xxxx.png
2019-6-6 08:45

2楼有些刺眼,先来做炮灰,下面没解决,只是尝试
考虑直线上的点,看来最多n=4点,
比如依次5点ABCDE,距离都为1,那么ACE三点之间距离都不是1了,若有1点和相邻点距离不是1,取这个点和这个相邻的点,最多只能再取1点了,4点都达不到了.

考虑2平行线的,最多n=6点;同上的穷举,考虑3平行线的,分散在3直线上,也是n=6

大概的感受是,这些点要“凑在一起,不能空洞”,记f(k,D)为这个区域D内,能使“取k点必有2点距离为1”成立的n的最大值.三个图,k=3时,依次是4,6,6.
显然有若P是Q的子集,则f(3,P)≤f(3,Q),更一般有f(k,P)≤f(k,Q),(k≥2,k∈N).若m≥n,f(m,P)≥f(n,P).
要解决1楼问题,还需要说明为什么7点不可以.

TOP

回复 3# realnumber


    谢谢,这几天我也想了很多,还是没什么思路.似乎点数太大时,会产生一个点,使得它和另外三个点两两距离为一,这就是矛盾所在

TOP

返回列表 回复 发帖