0%

Problem 557


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.

p557-triangle.gif

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).


切割三角形

一个三角形可以被两条由顶点引向对边的直线切割成四块,其中包括三个较小的三角形和一个四边形。如果原三角形的面积是整数,通常能够找到一种切割方式,使得切割后的四小块的面积仍然保持整数。例如,下图展示了一个被切割的面积为55的三角形:

p557-triangle.gif

将上图中切割后四小块的面积记为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)为所有满足a+b+c+d ≤ n的四元组所表示的原三角形的面积和。
例如,S(20) = 259。

求S(10000)。