题目

Problem 557. Cutting triangles

A triangle is cut into four pieces by two straight lines, each starting at one vertex and ending on the opposite edge. This results in forming three smaller triangular pieces, and one quadrilateral. If the original triangle has an integral area, it is often possible to choose cuts such that all of the four pieces also have integral area. For example, the diagram below shows a triangle of area 55 that has been cut in this way.

Triangle

Representing the areas as a, b, c and d, in the example above, the individual areas are a = 22, b = 8, c = 11 and d = 14. It is also possible to cut a triangle of area 55 such that a = 20, b = 2, c = 24, d = 9.

Define a triangle cutting quadruple (a, b, c, d) as a valid integral division of a triangle, where a is the area of the triangle between the two cut vertices, d is the area of the quadrilateral and b and c are the areas of the two other triangles, with the restriction that b ≤ c. The two solutions described above are (22,8,11,14) and (20,2,24,9). These are the only two possible quadruples that have a total area of 55.

Define S(n) as the sum of the area of the uncut triangles represented by all valid quadruples with a+b+c+d ≤ n.
For example, S(20) = 259.

Find S(10000).

题解

第557题:划分三角形

一个三角形可以被两条直线划分为四个部分,每条直线始于三角形的顶点而终于对边。得到三个更小的三角形以及一个四边形。如果原始的三角形的面积为整数,通常可以使得这四个部分的面积也是整数。例如,下图中的三角形的面积是 55。

Triangle

在这个例子中,各部分的面积是 a, b, c 和 d,分别为 a = 22, b = 8, c = 11 和 d = 14。面积为 55 的三角形也可以划分为 a = 20, b = 2, c = 24 和 d = 9。

定义四元组 (a, b, c, d) 为三角形的整数划分,a 是两条划分直线之间的面积,d 是四边形的面积,b 和 c 是其他两个三角形的面积,满足 b ≤ c。上面描述的两个解是 (22,8,11,14) 和 (20,2,24,9)。这是面积为 55 的三角形的仅有的两个整数划分。

定义 S(n) 为所有面积不超过 n 的三角形的所有整数划分的不同四元组的 a+b+c+d 的和。
例如,S(20) = 259。

求 S(10000)。

分析

Triangle

如上图,,令 ,则:

其中 。由梅涅劳斯定理,我们有:

根据相似三角形的性质,我们有:

最终得到:

由于这些变量都是正整数,我们可以枚举 s, a, d,尝试解出 b, c 。

解答

根据以上分析,我们有以下 Haskell 程序:

import Math.NumberTheory.Powers.Squares ( isSquare )

main = let n = 10^4 in print $ sum [s | s <- [4..n], a <- [1..s-3],
  let e=a*a; f=s+a; t = div f $ gcd e f, d <- [t,t+t..s-a-2],
  let g = s-a-d, isSquare $ g*g - 4 * (div (d*e) f)]

简要说明:

  • 第1层循环:量 s4 递增到 n
  • 第2层循环:量 a1 递增到 s-3
  • 第3层循环:量 dt 递增到 s-a-2,步长为 t
  • t 等于
  • g 等于
  • div (d*e) f 等于
  • g*g - 4 * (div (d*e) f) 等于

这个程序的运行时间是 86 秒,不符合欧拉计划的一分钟原则。

优化

上述程序的最内层的 d 循环不必进行到底:

557a.hs

简要说明:

  • 第5行的 takeWhile 函数用于提前终止最内层的 d 循环。
  • isSquare' 函数不检查自变量是否小于零,从而稍微加快速度。

这个程序的运行时间是 41 秒。

进阶

面积为 s 的三角形的所有整数划分的不同四元组的个数是有限的,例如,当 s = 20 时,共有以下五个不同四元组:

  • (4,1,6,9)
  • (5,1,7,7)
  • (5,3,3,9)
  • (10,2,5,3)
  • (12,3,3,2)

但是,每个四元组对应的三角形是无限的,例如,四元组 (4,1,6,9) 对应:

参考资料

  1. Wikipedia: Menelaus' theorem
  2. Wikipedia: Similarity (geometry)