技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 趣题:两两间的距离都是整数的点集

趣题:两两间的距离都是整数的点集

浏览:1407次  出处信息

     最多能在平面上找出多少个点,使得它们两两之间的距离都是整数?当然,我们忽略最平凡的解――所有点都在一条直线上。

     三个点的解显然是存在的,只需要构造一个边长为 1 的等边三角形即可。事实上,满足任意两数之和大于第三数的一组整数都可以成为一个三角形的三条边。寻找含有四个点的解也并不困难,一个长为 4 宽为 3 的矩形就能满足要求。不过,我们还有更小一些的解。最小的解貌似是下面这个等腰梯形:上底、下底分别是 3 和 4 ,两腰都是 2 ,两条对角线都是 4 ,正好也都是整数。

    

     那么,能否找到平面上的五个不共线的点,使得两两之间的距离都是整数呢?最多能找到多少个这样的点呢?

     想到这个问题之后,我在网上简单地搜索了一下。出人意料的是,我们能在平面上找出任意多个不共线的点,使得它们两两之间的距离都是整数。构造方法有很多,这里提到的是我最喜欢的构造方法之一。

     为了得到所有距离都是整数的点集,我们只需要构造出所有距离都是有理数的点集,再乘以所有分母的公倍数即可。现在,作一个直径为 1 的圆,任意作一条直径 AB 。取两组勾股数,比如 (3, 4, 5) 和 (5, 12, 13) 吧。在圆上找一点 C ,使得 ABC 组成一个边长分别为 (3/5, 4/5, 1) 的直角三角形;在圆上找一点 D ,使得 ABD 组成一个边长分别为 (5/13, 12/13, 1) 的直角三角形。这样一来, AB 、 AC 、 BC 、 AD 、 BD 的长度就都是有理数了。有趣的是,根据 Ptolmey 定理,这个圆内接四边形满足 AB ・ CD + AC ・ BD = AD ・ BC ,由此可知 CD 的长度也一定是一个有理数。

    

     由于本质上不同的勾股数组有无穷多个,因此圆弧上像 C 和 D 这样的点也有无穷多个。也就是说,我们能在圆上找到任意多的点,使得它们之间的距离都是有理数。乘以这些有理数的公分母后,便能得到任意多个两两距离都是整数的点了。

     寻找满足各种条件的“整距离图形”是一个非常有趣的话题。这类问题叫做 Rational Distances ,搜索一下可以找到很多有趣的结论。

QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1