分成三个小正方形,若最小距离大于sqrt2,则每个小正方形各自最多放一个,抽屉原理易证放不了四个,故sqrt2就是最优
P19 · L 形内的散点分离 · 讨论
关于此题n=4已达最优的证明
同理直角三角形那题的n=4也可证
n=4还有一个最优解,也是sqrt(2),这里的方法也通用,也可以用这里的抽屉原理证明。 把4个点分别放在(0,1),(1,0),(1,2),(2,1)的位置,也可得到最优,这是满足的另一个构型。
分成三个小正方形,若最小距离大于sqrt2,则每个小正方形各自最多放一个,抽屉原理易证放不了四个,故sqrt2就是最优
同理直角三角形那题的n=4也可证
n=4还有一个最优解,也是sqrt(2),这里的方法也通用,也可以用这里的抽屉原理证明。 把4个点分别放在(0,1),(1,0),(1,2),(2,1)的位置,也可得到最优,这是满足的另一个构型。