Let's classify all the possible equilateral triangles of interest. As there are more equilateral triangles in the proof, let's call those we want to count the counting triangles.
For each of the counting triangle asked, define its enclosing triangle be the minimal upright equilateral triangle that goes alone the network. Here, upright means the triangle has one side being horizontal, and the third vertex is above the horizontal side. Later in the text, the term upside-down will appear, meaning the opposite of upright, ie. one side being horizontal but the third vertex is below the horizontal side.
For example, here are some counting triangles (red) and their enclosing triangle (blue). The second counting triangle is upside-down.
We classify counting triangles by the side length of its enclosing triangle, as this directly related to how many these triangles are there in the original network. If the network has side N, we can find the number of ways an enclosing triangle has side p can fit into the network: it is the (N-p+1)-th triangle number, ie. (N-p+1)*(N-p+2)/2.
Now let's tackle the side length of these counting triangle. For a counting triangle that's neither upright nor upside-down, we can cut out the three corners of its enclosing triangle, forming a equiangular hexagon (green):
The side of this counting triangle can be calculated by the two side length of the equiangular hexagon. Let h and k represent these length as above. Since the angle between them is 120 degrees, the length x can be derived from law of cosines:
Note that, although we excludes upright and upside-down counting triangles above, they can really be viewed as degenerated cases of these hexagon: upright counting triangles have k=0, while upside-down counting triangles have h=0. This is important in the actual counting later.
Also seen in the above image, the side of enclosing triangle, p, is equal to h+2k. Substitute h=p-2k into h^2+hk+k^2, we got 3k^2-3pk+p^2. We want this value be between A^2 and B^2.
Now here's a tricky part. 3k^2-3pk+p^2 is a quadratic polynomial of k with a positive leading coefficient, so it has a minimum value. It's easy to find the minimum value is at k=p/2; but since h=p-2k>=0, k is always <=p/2, which means our quadratic polynomial is decreasing in our range of interest.
Let's find the range of k to let the value of it between A^2 and B^2. Solve 3k^2-3pk+p^2=Z^2 gives
and because k<=p/2, we can only choose minus. The range of k is thus
But here are two catches:
- The lower bound can be less than zero. This happends when
p<B. In this case, the lower bound is simply zero, askcannot be negative. - The upper bound can be "non-existing". This is because the minimum value of the quadratic formula is bigger than
A^2, so nokcan satisfy equality. This happens when the number inside square root is negative, ie.p>2A. In this case, the upper bound is the place of extreme minimum of the quadratic formula,k=p/2.
Now we have a range of k. Each integer in this range corresponds to a (possibly degenerated) equiangle hexagon. If k=0 or k=p/2, this hexagon is degenerated, and there can only be one kind of counting triangle (the upright and upside-down ones); otherwise, there can be two kinds of counting triangle, one is the reflection of the other. So for a given enclosing triangle, we can count how many counting triangles having the required side length has this enclosing triangle, by counting the integers in the aforementioned range of k, multiply by 2, then subtract 1 for both k=0 and k=p/2 cases if any.
Finally, we need to find the range of possible enclosing triangle. Still from the quadratic formula, a counting triangle of side x can have enclosing triangle of side x to 2x. This can be derived by substitute k=0 and k=p/2 into that quadratic formula, let it equals to x^2 and solve for p. This can also be observed by rotating a fixed sized counting triangle, and note that the enclosing triangle is the smallest when the counting triangle is upright, and the largest when the counting triangle is upside-down. Anyway, to search for A<=x<=B, we need to search A<=p<=2B.
Combining all above, we can now write down the algorithm:
For p in [A,2B]:
Calculate the bound of k as above
Count the possible counting triangles in the bound (Two for each non-degenerated, one for each degenerated)
Multiply that by the # of ways to put into network ((N-p+1)-th Triangle number)
Sum up the amount above
This directly corresponds to my program.
And, before you ask, the formula picture in this documents uses this Online LaTeX Equation Editor and export it as image links. The triangle pictures are "hand drawn" using Mathematica (ie. manually type in all details like what should drawn where using which color).
Wow, nice!!