143. 三角形托里拆利点的研究(Investigating the Torricelli point of a triangle)

三角形\(ABC\)的内角均小于\(120\)度,取三角形内的任意一点\(X\)满足\(XA = p,XC = q\)\(XB = r\)。费马曾经向托里拆利提出挑战,找到点\(X\)的位置,使得\(p + q + r\)最小。

托里拆利证明了,如果对三角形\(ABC\)的三边分别构造等边三角形\(AOB,BNC\)\(AMC\),这三个三角形的外接圆将会交于三角形内一点\(T\)\(T\)点也被称为托里拆利点或费马点,就是使得\(p + q + r\)最小的点。更神奇的是,此时\(AN = BM = CO = p + q + r\),且\(AN\)\(BM\)\(CO\)相交于点\(T\)

p143_torricelli

如果当\(p,q,r\)之和最小时有\(a,b,c,p,q,r\)均为正整数,我们称这个三角形\(ABC\)为托里拆利三角形。例如,\(a = 399,b = 455,c = 511\)就是一个托里拆利三角形,此时\(p + q + r = 784\)。求对于所有满足\(p + q + r ≤ 120000\)的托里拆利三角形,所有不同的\(p + q + r\)的值之和。

分析:这是一道结合与几何与数论知识的题目,需要一定的前置知识才能比较顺利的解决:一是要了解费马点的几何性质,最重要的是知道以费马点为顶点,与三角形各顶点连线形成的三个角度都为\(120^\circ\)。二是基于上述几何性质,根据余弦定理,推导出\(p,q,r\)以及三角形三边需要满足的方程,我们要求解这个方程的正整数解。三是与勾股数组的生成公式类似,我们可以找到上述方程的基本解的生成公式,利用生成公式,我们可以生成满足条件的\(p,q,r\)并求它们的和。下面分别来介绍这些内容:

一、费马点的几何性质

题目中给出了一种构造费马点的方法,但没有说明为什么这样构造出来的点就是使得\(p,q,r\)之和最小的点。实际上费马点是平面几何中讨论得比较多的问题,有很多不同的构建与证明思路,既有传统几何的方式,也有向量法或者微积分的方式(可参见维基)。我这里使用一种我在youtube上看到构建思路,我觉得是我目前看到的思路中最容易理解的。考虑到有些同学上不了外网,我下面把这种思路简单介绍一下,如果可以上外网,可以直接去看那个视频。

对于三个内角均小于\(120^\circ\)的三角形\(\triangle ABC\),设其内部有一点\(P\),我们想使得\(PA+PB+PC\)最小。则我们可以把\(\triangle APB\)绕着\(A\)点逆时针旋转\(60^\circ\),形成三角形\(AP'B'\)

Snipaste_2021-04-23_11-17-00

由于\(AP'=AP\)\(\angle P'AP=60^\circ\),则易知\(\triangle PAP'\)是一个等边三角形,所以有\(PA=PP'\)。又因为\(PB=P'B'\),所以有\(PA+PB+PC=PP'+P'B'+PC\),求\(PA+PB+PC\)的最小值,也就是求\(PP'+P'B'+PC\)的最小值,这个性质对任何三角形内部的\(P\)都是成立的:

微信截图_20210423112235

显然\(PP'+P'B'+PC\)就是一条从\(B'\)点到\(C\)点的路径,要使得这条路径最短,当且仅当\(P'\)\(P\)点都落在\(B'C\)这条直线上成立,此时\(B',P',P,C\)四点共线:

微信截图_20210423113111

上述条件满足时,因为\(\triangle APP'\)是一个等边三角形,有\(\angle APP'=60^\circ\),因此\(\angle APC=120^\circ\)

微信截图_20210423113234

使用同样的方法,对\(\triangle BPC\)\(\triangle APC\)旋转并构建等边三角形,可以证明\(P\)也落在\(AC'\)\(BA'\)上,从而\(B'C,AC',BA'\)三条直线相交于一点,这个点便是费马点。同样\(\triangle P'CP\)\(\triangle BPP'\)也是等边三角形,则有\(\angle BPP'=\angle P'PC=60^\circ\),因而\(\angle APC=\angle BPC=\angle APB=120^\circ\),也就是以\(P\)为顶点的三个角都为\(120^\circ\)

微信截图_20210423113315

通过上面旋转三角形的方法易知,\(AB'=AB\)\(\angle B'AB=60^\circ\),所以\(\triangle ABB'\)是一个等边三角形,同理可以证明\(\triangle BC'C\)\(\triangle ACA'\)也是等边三角形。因此当我们构建费马点时,只需要以三角形的三边分别做三个等边三角形,再将这些等边三角形相对顶点连线,这三条连线将交于一点,这个点就是三角形的费马点。

微信截图_20210424091148

需要注意的是,只要当三角形的三内解均小于\(120^\circ\)时,费马点才位于三角形内部,否则费马点将退化为三角形的一个顶点。

二、有一内角为\(120^\circ\)的整数三角形

上面简要说明了费马点的几何性质,其中对解答本题最重要的一个几何性质是就是以费马点为顶点,以费马点到三角形三顶点连线为边的三个角度相等且都为\(120^\circ\)。因此根据余弦定理,采用题目中的记法,当我们已知\(p,q,r\)时,可以求出三角形的三边:

$$ \begin{cases} p^{2} +r^{2} -2prcos( 120) =p^{2} +r^{2} +pr=c^{2}\\ p^{2} +q^{2} -2pqcos( 120) =p^{2} +q^{2} +pq=b^{2}\\ r^{2} +q^{2} -2qrcos( 120) =r^{2} +q^{2} +qr=a^{2} \end{cases} $$

对于上述方程组,我们要求\(a,b,c,p,q,r\)均为正整数,这是一类丢番图方程问题。可以看到上述三个方程的结构都是一样的,所以我们只需要研究任意一个方程就可以了。

为避免混淆,我们把我们想要研究的方程重新表述为求方程\(a^2+b^2+ab=c^2\)的正整数解。可以看到,这个方程与勾股定理\(a^2+b^2=c^2\)非常相似,只是多了一个\(ab\)项。我们知道对于勾股定理的方程,我们可以找到一些正整数解,它们也叫勾股数或者毕达哥拉斯三元组。我们可以使用欧几里得公式来生成这些勾股数。对于正整数\(m,n\)\(m>n>0\),有:

$$ a=m^2-n^2,b=2mn,c=m^2+n^2 $$

如果这些勾股数之间两两互质,因此不能从其它勾股数生成,这样的勾股数组我们可以称之为本原勾股数组,或者称其为基本解,常见的本原勾股数组有\((3,4,5),(5,12,13)\)等等。这时我们还需要对上面的公式加上两个条件,即\(m,n\)互质且不能都为奇数,或者表述为\(gcd(m,n=1)\)\((m-n)∤2\)

对于形如\(a^2+b^2+ab=c^2\)的方程,我们也可以推导出它的基本解的公式,推导的方法有很多,我这里使用一种与几何相结合的方法,相对直观易懂一些。首先可以注意到,对于上述方程,我们可以在方程左右两侧同时除以\(c^2\),则有:

$$ \left(\frac{a}{c}\right)^{2} +\left(\frac{b}{c}\right)^{2} +\left(\frac{a}{c}\right)\left(\frac{b}{c}\right) =1 $$

求原方程的正整数解,就等同于求上式的正有理数解,令\(x=a/c,y=b/c\),则上式变为:

$$ x^2+y^2+xy=1 $$

可以发现上式实际上表示一个椭圆,如下图:

geogebra-export

为了找到上述方程的有理解,就等价于找到上述椭圆上的有理点,也即横纵坐标都为有理数的点。为此我们可以过点\(A(-1,0)\)做一条斜率为\(t\)的直线(\(t\)为有理数),与纵轴相交于\(B(0,t)\),因为\(A\)\(B\)均为有理点,则这条直线上的点均为有理点,因此其与椭圆的交点\(C\)也是一个有理点,其坐标为\(\left(\frac{1-t^{2}}{t^{2} +t+1} ,\frac{2t+t^{2}}{t^{2} +t+1}\right)\)

通过上述方式,我们可以通过改变\(t\)的值,找到椭圆上的全部有理点。由于\(t\)是一个有理数,我们可以将其表示为\(t=n/m\),则代入\(C\)点坐标有:

$$ C\left(\frac{m^{2} -n^{2}}{m^{2} +mn+n^{2}} ,\frac{2mn+n^{2}}{m^{2} +mn+n^{2}}\right) $$

因为我们定义了\(x=a/c,y=b/c\),所以我们可以得到一组正整数解为:

$$ a=m^{2} -n^{2} ,b=2mn+n^{2} ,c=m^{2} +mn+n^{2} $$

但是上述公式并不能保证生成的三元组是一个基本解,如果\(m,n\)存在一个公因子,则根据上述公式\(a,b,c\)也会存在一个公因子,因此可以由其它解来生成,从而不是基本解,所以为了保证上述公式生成基本解,\(m,n\)必须互质。

此外\((m-n)\)必须不能整除\(3\),否则\(a=(m+n)(m-n)\)会整除\(3\)\(b=n(m-n+3m)\)也会整除\(3\),同时\(c=(m-n)^2+3mn\)也会整除\(3\)。因此我们有:

\(m,n\)为正整数,\(m>n,gcd(m,n)=1,(m-n)\nmid3\)时,

$$ a=m^{2} -n^{2} ,b=2mn+n^{2} ,c=m^{2} +mn+n^{2} $$
构成方程\(a^2+b^2+ab=c^2\)的一组基本解。

使用上述公式生成基本解后,我们只需要把\(a,b,c\)乘以一个相同倍数,就可以得到原方程的另外一组解。

三、算法实现

使用上述公式我们可以找到特定范围内符合条件的三元组,将在三元组中乘以相同倍数得到更多的解,假设其中的两组解是\((a,b,c)\)\((a,e,f)\),则两个三元组共享一个元素\(a\),这时候我们只需要检查另外两个元素\(b\)\(e\)是否也满足方程,即\(b^2+e^2+be=g^2\)是一个完全平方数。如果上述条件满足,且\(a+e+b\le120000\),则我们找到了一组符合题目要求的解。其中\(c,f,g\)为三角形的三边,\(a,e,b\)为费马点到三角形三个顶点的连线,六条线段的长度均为正整数。

在实际实现时,我们并不关心三角形的三边\(c,f,g\),而只关心连线\(a,e,b\),由于\(a,e,b\)三者之和必须小于\(12000\),则其中任意两者之和也必须小于\(12000\),则有:

$$ 120000 >a+b=m^{2} -n^{2} +2mn+n^{2} =m^{2} +2mn >m^{2} +2m\Rightarrow m< 346 $$

则我们可以在这个范围内生成所有符合条件的数对,如果这些数对存在公共元素,我们再除公共元素外的另外两个元素是否也能构成一个内角为\(120^\circ\)的三角形,如果可以则是一个符合题目要求的解。最后,对于所有符合要求的\(p+q+r\),我们求它们的和,即为题目所求。代码如下:

# time cost = 253 ms ± 5.44 ms

from math import gcd
from collections import defaultdict

def generate_pairs(N=120000):
    pairs = defaultdict(set)
    for i in range(2,346):
        for j in range(1,i):
            if gcd(i,j) == 1 and (i-j)%3 != 0:
                q,r = 2*i*j+j**2,i**2-j**2
                q,r = max(q,r),min(q,r)
            for k in range(1,N//q+1):
                pairs[k*q].add(k*r)
    return pairs

def main(N=120000):
    res = set()
    pairs = generate_pairs()
    for k,v in pairs.items():
        for q in v:
            if q in pairs:
                for r in (v & pairs[q]):
                    res.add(k+q+r)
    return sum({x for x in res if x<=N})