Using your Head is Permitted

April 2009 solution

Consider the following: there is a one-to-one correspondence between integer-sided right-angle triangles with side lengths {a,b,c} and triplets of naturals (k,x,y) with x and y odd and co-prime and y>x, which can be described explicitly by the mapping

a=k(y2-x2)/2
b=kxy
c=k(y2+x2)/2

To demonstrate this, let us show that we can calculate k, x and y uniquely from a, b and c in such a way that they meet the requirements of them.

First, the gcd of a, b and c is simply k. Proof: If it is not, then there must be a prime, p that divides both xy and y2+x2. Because x and y are co-prime, p must divide exactly one of the two. Let us suppose w.l.o.g that it divides x. Then, it divides x2 but not y2, so also not their sum. A contradiction.

Let us therefore divide everything by k and work with {a,b,c} that have a gcd of 1. Consider these values modulo 4 and let c be the hypotenuse length. An even number squared is 0 (mod 4). An odd number squared is 1 (mod 4). It cannot be that both a and b are even, for this would mean that c is also even, and therefore their gcd would not have been 1. However, a and b cannot both be odd, either, for then c2 would be 2 (mod 4), which is impossible. This means that exactly one of a and b is even. This defines a specific order over the triplet (and therefore eliminates ambiguity): c is the largest, and of the remaining two a is chosen to be the even one and b the odd one.

Consider now that b2 = c2-a2 = (c+a)(c-a). b2 is therefore to be represented as the multiplication of two factors, m=c+a and n=c-a (Note: m>n). As b is odd, so must m and n be. Furthermore, consider that a=(m-n)/2 and c=(m+n)/2. If m and n had any common odd factors, these common factors would have also been factors of a, b and c, so the gcd of the sides of the triangle would not have been 1, contrary to the assumption. This means that m and n must be co-prime. As the product of m and n is a perfect square, these two co-prime factors must be squares themselves. We denote m=y2 and n=x2. This solves y and x uniquely as the odd, co-prime values sqrt((c+a)/k) and sqrt((c-a)/k), respectively, proving the correspondence.

Now, let us rephrase the question in terms of (k,x,y) triplets. The perimeter, in these variables, is ky(x+y). Let us define z=x+y. Note that due to the conditions on x, z is constrained to be even, co-prime with y and in the range y<z<2y.

We want to find the number of triplets where kyz=10n. This is equivalent to finding the number of (y,z) pairs where yz is a divisor of 10n.

Because y is odd, it cannot have a factor of 2, therefore it must be a power of 5. Because y<z<2y, we know that y>1, so y divides by 5. z must be co-prime with y, so z cannot divide by 5, so it is a power of 2.

Note that even though any positive power of 5 can be used as y, each choice defines a legal range of z values wherein exactly one value is a power of two. This means that the total number of triangles equals the total number of positive powers of five that yield yz≤10n.

If y=5v and z=2w, it is clear that v<w for z to be within its legal range. This indicates that the limiting factor in determining the largest possible yz is wn.

Putting everything together, we get 51y=5v < z=2w ≤ 2n. This indicates that v is in the range 1≤v<log5 2n. The total number of such values for v is floor(log52n)=floor(log52 n), which is the final answer.

This riddle was inspired by one of the problems on the Project Euler website. Thanks, Project Euler!

Back to riddle

Back to main page