094. 几乎等边三角形(Almost equilateral triangles)

很容易证明不存在边长与面积都为整数的等边三角形,然而几乎等边的三角形如\((5,5,6)\)的面积为\(12\)是一个整数。我们可以把几乎等边的三角形定义为两条边相等,而另一边最多和它们相差一个单位的三角形。

求所有的边长和面积都为整数,且周长不超过十亿的几乎等边三角形的周长之和。

分析:题目把几乎等边三角形定义为两边相等,而另一边最多和它们相差一个单位的三角形。显然这种三角形是一个等腰三角形,而另一边要不比这两边大一、要不比这两边小一。假设我们设相等的两条边的长度为\(a\),则第三边的长度\(b=a\pm1\)。如下图所示:

img

过点\(A\)\(BC\)的垂线\(AD\),因为是一个等腰三角形,所以\(AD\)也是边\(BC\)的中垂线,\(D\)\(BC\)的中点。则根据勾股定理易知:

$$ y^2=a^2-\left( \frac{a\pm 1}{2} \right) ^2=\frac{3}{4}a^2\pm \frac{a}{2}-\frac{1}{4} $$

因为三角形的面积\(S_{\bigtriangleup ABC}=by/2\),所以要让三角形面积为整数,\(y\)也必须为整数。因此我们的问题转化为求上述方程的正整数解。每找到一组正整数解,就对应一个几乎等边三角形,从而可以求出他们的周长并求和。为了解这个不定方程,我们需要对其进行一些变换,首先在左右两侧同时乘以十二:

$$ 9a^2\pm 6a-3=12y^2 $$

再在方程两边同时加上四:

$$ 9a^2\pm6a+1=12y^2+4\Rightarrow (3a\pm1)^2-12y^2=4 $$

再在方程两边同时除以四:

$$ \left( \frac{3a\pm 1}{2} \right) ^2-3y^2=1 $$

我们令\(x=(3a\pm1)/2\),则原方程转化为:

$$ x^2-3y^2=1 $$

显然这是我们在第六十六题中讨论过的佩尔方程。只要我们找到方程的一组正整数解\((x,y)\),就可以反向推出三角形边长\(a=(2x\pm1)/3\),面积\(S=(a\pm1)\cdot y/2\)。只要\(a\)\(S\)都为整数,我们就找到了一个符合要求的几乎等边三角形,易知其周长\(p=3a\pm1\)

易知上述佩尔方程的最小正整数解为\((x=2,y=1)\),从而可以推出\(a=1\)(另一个解不是整数),则三条边分别是\((1,1,2)\),不符合三角形两边之和必然大于第三边的要求,所以这不是一个符合要求的解。我们知道对于佩尔方程,如果我们找到了它的最小正整数解\((x_1,y_1)\),则该方程其它的解满足以下递推关系:

$$ \left( x_n+y_n\sqrt{d} \right) =\left( x_{n-1}+y_{n-1}\sqrt{d} \right) \left( x_1+y_1\sqrt{d} \right) $$

则对于上述佩尔方程有:

$$ \begin{align*} \left( x_n+y_n\sqrt{3} \right) &=\left( x_{n-1}+y_{n-1}\sqrt{3} \right) \left( 2+\sqrt{3} \right) \\ &=2x_{n-1}+x_{n-1}\sqrt{3}+2y_{n-1}\sqrt{3}+3y_{n-1} \\ &=\left( 2x_{n-1}+3y_{n-1} \right) +\left( x_{n-1}+2y_{n-1} \right) \sqrt{3} \end{align*} $$

因此我们可以得到递推关系:

$$ x_n=2x_{n-1}+3y_{n-1},y_n=x_{n-1}+2y_{n-1} $$

根据上述递推关系,我们可以找到这个佩尔方程的无穷多组正整数解,如将\((x_1=2,y_1=1)\)代入,可以得到\((x_2=7,y_2=4)\),从而可以找到一个整数解\(a=(2\times7+1)/3=5\),正是题目中给出的例子。我们从这组解开始根据递推关系向上寻找正整数解,再计算出相应的边长和面积,判断两者是否为整数,如果均为整数则计算出相应周长并累加起来。当周长超过十亿时停止计算,得到的符合要求的几乎等边三角形的周长之和了。代码如下:

# time cost = 25.1 µs ± 56.2 ns

def main(U=10**9):
    x,y = 7,4
    p_sum = 0
    while True:
        a1,a2 = (2*x+1)/3,(2*x-1)/3
        s1,s2 = (a1+1)*y/2,(a2-1)*y/2
        p1,p2 = (3*a1+1),(3*a2-1)
        if (p1<=U) and (a1%1==0) and (s1%1==0):
            p_sum += p1
        if (p2<=U) and (a2%1==0) and (s2%1==0):
            p_sum += p2
        if (p1>U) and (p2>U):
            return p_sum
        else:
            x,y = 2*x+3*y,x+2*y