I wrote the Euclid contest this year two days ago, on tuesday. There were 10 problems, and the tenth problem was a nice geometry problem. Three subproblems with a nice neat triangle on the right, with the subproblems getting progressively harder and harder. As I proceeded with the problem, I couldn’t help but imagine it as a Project Euler problem — instead of finding one such integer triangle, it would ask you to find the sum of the perimeters of all such integer triangles with perimeter less than 10^12 or some large number.
A modified problem
In the above diagram, and . Let , , , , and . Write an algorithm to find triangles satisfying these conditions where a, b, c are all integers.
It is difficult to try to find integer triangles with such strange requirements as these. It seems that the line is completely unnecessary, but if we take it out, there doesn’t seem to be any way to relate the angle ratios to integer side lengths.
We can prove that is similar to . Being an exterior angle, , and also . Both of the triangles have an angle of measure and another angle of measure , thus they are similar.
From the similar triangles ratio
We can write d in terms of the three sides of the triangle:
Similarly, the side can be written as . Then we have the ratio
Solving for x allows us to express it in terms of the three sides of the triangle, again:
Constructing another similar triangle
Our goal here is to relate the lengths a, b, c with a simple equation, which then the problem turns into a number theory problem. Since we can write the lengths d and x in terms of a, b, and c, we can also relate any of a, b, c, d, x in an equation.
Again, there doesn’t seem to be a way to relate all of the variables together, in a way that any solution implies the original angle ratio required — unless we make a construction.
Here we extend AB to F, so that and is an isosceles triangle.
Again, since the exterior angle here is , both . Also with this construction, , and is also isosceles, hence .
With this construction, we can write the ratio
Perfect! Cross multiplying and then substituting in the original sides of the triangles gives
Simplifying this gives
Number theory magic
Now that we have an equation relating the three side lengths — it’s easy to verify that any three integers satisfying the triangle inequality gives a triangle with the required conditions — we can use number theory to try to generate integers that fit the equation.
If we expand the equation, we get
It makes sense to solve for c, which can be done using just the quadratic formula:
We need the discriminant D — the expression inside the square root — to be a perfect square, where we are allowed to have integer values for a and b. If we can get D to be a perfect square, then c will turn out to be a rational number. Then multiplying all three variables by a constant gives integer values for all three.
So we defined D:
Expanding this gives
Fortunately, this expression has an interesting factorization:
Or we can also write
We’ve simplified this problem to finding values where is a perfect square, that is:
This is just finding Pythagorean triples where one of the two sides are even! For instance, in the triple (3,4,5), we have a=3 and b=2. However, substituting a=3, b=2 into the quadratic formula gives c=5. This is almost a solution, only that the sides have to satisfy the triangle inequality (two sides have to add up to more than the third side).
The next Pythagorean triple (5,12,13) gives a=5 and b=6. Substituting this in gives c=11/9, which does satisfy the triangle inequality. Multiplying everything by 9 gives a=45, b=54, c=11 as the smallest working combination.
With this method, it is possible to quickly find arbitrarily many such triples, using Pythagorean triples as a starting point (which can be generated quickly with known methods).