How many triangles?

`I think there is a straightforward way to calculate the number of`
`triangles in the figure, or for that matter to come up with a general`
`formula for similar figures. Suppose that S is the length of a
side of`
`the figure; the figure as shown has S = 10.`

`There are six sets of parallel lines in the figure:`

`S lines A[1]..A[S] parallel to the base of the figure (indexed by`
`length).`
`S lines B[1]..B[S] parallel to the right side of the figure (indexed`
`similarly).`
`S lines C[1]..C[S] parallel to the left side of the figure (indexed`
`similarly).`
`2S-1 lines D[1]..D[2S-1] perpendicular to the A lines (indexed
from left`
`to right along the base).`
`2S-1 lines E[1]..E[2S-1] perpendicular to the B lines (indexed`
`similarly).`
`2S-1 lines F[1]..F[2S-1] perpendicular to the C lines (indexed`
`similarly).`

`The sides of any triangle must consist of one line from each of
three`
`distinct parallel sets, thus there are triangles ABC, ABD, etc.
If we`
`define #ABC as the number of ABC triangles, etc., then the total
number`
`of triangles will be #ABC + #ABD + ... + #DEF, a total of twenty
subsets`
`to be considered. The symmetries of the figure imply #ABF = #ACE
= #BCD,`
`#AEF = #BDF = #CDE, #ABD = #ABE = #ACD = #ACF = #BCD = #BCE, #ADE
= #BDE`
`= #ADF = #CDF = #BDE = #BEF, thus we can reduce the problem to
computing`

` #ABC + #DEF + 3*#ABF + 3*#BDF + 6*#ABD + 6*#ADF`

`Note that the triangles in #ABC and #DEF are equilateral, those
in #ABF`
`and #BDF are isosceles with angles 120-30-30, and those in #ABD
and #ADF`
`are right with angles 90-60-30.`

`To compute (for example) #ABC, we want to know how many of the sets
of`
`lines (A[a],B[b],C[c]) are such that the three line intersections
are`
`distinct and all lie within the figure. The constraints are`

` a+b >= S`
` a+c >= S`
` b+c >= S`
` a+b+c <> 2S`

`This can be solved by brute force algebra to give`

` #ABC = (2S^3+5S^2+2S-(S mod 2)) / 8`

`Here as usual, (S mod 2) is 1 if S is odd and 0 if S is even. For
S =`
`10, we get #ABC = 315.`

`Here follow the constraints and the derived formulas for the remaining`
`sets of triangles.`

`#DEF: (D[d],E[e],F[f])`

` d+2e >= 2S`
` 2d+e <= 4S`
` e-d <= S`
` e+2f >= 2S`
` 2e+f <= 4S`
` f-e <= S`
` f+2d >= 2S`
` 2f+d <= 4S`
` d-f <= S`
` d+e+f <> 3S`

` #DEF = (3S^3 - S - 2(S mod 3)) / 3`

` for S = 10, #DEF = 996`

`#ABF: (A[a],B[b],F[f])`

` a+b >= S`
` 2b+f >= 2S`
` b+f <= 2S`
` f-a >= 0`
` f-2a <= 0`
` -a+b+f <> S`

` #ABF = (2S^3 + 3S^2 - 2S - 3(S mod 2)) / 12`

` for S = 10, #ABF = 190`

`#BDF: (B[b],D[d],F[f])`

` d-b >= 0`
` d-2b <= 0`
` 2b+f >= 2S`
` b+f <= 2S`
` f+2d >= 2S`
` 2f+d <= 4S`
` d-f <= S`
` 3b-d+f <> 2S`

` #BDF = (14S^3 + 33S^2 + 4S - 6(S mod 4) + 3(S mod 2)) / 48`

` for S = 10, #BDF = 361`

`#ABD: (A[a],B[b],D[d])`

` a+b >= S`
` a+d >= S`
` d-a <= S`
` d-b >= 0`
` d-2b <= 0`
` a+2b-d <> S`

` #ABD = (5S^3 + 12S^2 + 3S - 2(S mod 3)) / 18`

` for S = 10, #ABD = 346`

`#ADF: (A[a],D[d],F[f])`

` a+d >= S`
` d-a <= S`
` f-a >= 0`
` f-2a <= 0`
` f+2d >= 2S`
` 2f+d <= 4S`
` d-f <= S`
` -3a+d+2f <> S`

` #ADF = (18S^3 + 37S^2 - 2S - 5(S mod 2) - 8(S^3-S^2+S mod
5)) / 40`

` for S = 10, #ADF = 542`

`We can now calculate the total number of triangles for S = 10:`

` #ABC + #DEF + 3*#ABF + 3*#BDF + 6*#ABD + 6*#ADF =`
` 315 + 996 + 3*190 + 3*361 + 6*346 + 6*542 =`
` 8292`

`The formula for general S is`

` (1678*S^3 + 3117*S^2 + 88*S - 345*(S mod 2) - 320*(S mod
3) - 90*(S`
`mod 4)`
` - 288*((S^3-S^2+S) mod 5)) / 240`

`This can probably be simplified.`

`Solution by James Boyce`

`I will attempt to count the triangles.`

`As a warm-up. I will count the points in the diagram. There
are 55`
`little right-side-up equilateral triangles, each of which has a
topost`
`vertex, 3 midpoints of sides, and a centroid. That accounts
for 275`
`points. In addition, there are 45 upside-down triangles of
that same`
`size, each of which has a centroid. Finally, there are 11
points`
`along the bottom edge that I have not already counts. That
gives a`
`total of 331 points.`

`The diagram has lines in 6 different directions. I will name
the`
`directions parallel to the side of the diagram A, B, and C, and
denote`
`their corresponding normals a, b, and c. A triangle in the
diagram`
`will have sides in three of those directions. There are 20
triples of`
`directions, and each triple defines triangles of two orientations.`
`There are many symmetries in the diagram, which reduces the number
of`
`different cases I need to count carefully.`

`The cases to considers are these:`
`ABC: triangles with 2 edges parallel to the edges of the diagram.`
`AaB: triangles with 2 edges parallel to the edges of the diagram,
and`
`1 edge normal to one of those edges. (There are 6 cases like
this,`
`all the same.)`
`ABc: triangles with 2 edges parallel to the edges of the diagram
and 1`
`edge normal to the other edge of the diagram. (There are
3 cases like`
`this.)`
`Abc: triangles with 1 edge parallel to an edge of the diagram and
with`
`2 edges normal to the other 2 edges of the diagram. (There
are 3`
`cases like this.)`
`Aab: right triangles with 1 edge parallel to and edge of the diagram`
`and with 2 edges normal to edges of the diagram. (There are
6 cases`
`like this.)`
`abc: triangles with edges normal to all three sides of the diagram.`

`Remember that there are two orientations for each of those cases,
so I`
`might have as many as 12 counting problems. I will add up
the answers`
`to those problems (with suitable multipliers) to get the actual`
`answer.`

`case ABC: Each right-side-up ABC triangle has a topmost point.
Each`
`'topmost-point' may be the topmost point of more than one triangle.`
`There are 55 topmost points in the diagram. 10 of them have
only 1`
`triangle. 9 of them have 2, ... and 1 of them has 10.
That is a`
`total of 220.`

`Each upside-down ABC triangle has a bottom-most point. There
are 45`
`bottom-most points in the diagram. 17 of them have only one
triangle;`
`13 have 2; 9 have 3; 5 have 4; and 1 has 5. That is a total
of 95.`

`case AaB: The smallest AaB triangle is composed of 3 of the little`
`triangles in the diagram. An AaB triangle is half of an equilateral`
`triangle. For right-side-up equilateral triangles, all of
the`
`eqilater triangle is presents, so the answer is the same as the
ABC`
`case: 220 triangles.`

`The upside-down case requires more counting. Each AaB triangle
has a`
`60 degree angle, with wlog is its bottom-most point. There
are still`
`45 bottom-most points to consider. There are 9 with only
1 triangle;`
`15 have 2; 6 have 3; 9 have 4; 3 have 5; and 3 have 6. This
total is`
`126.`

`case ABc: The smallest ABc triangle is composed of 6 of the little`
`triangles in the diagram. It is 1/4 of an equilateral triangle.
In`
`the case of right-side-up equilateral triangles, the entire triangle`
`will be there. So we need to count right-side up equilateral`
`triangles with even edge length. There are 45 triangles of
side 2; 28`
`of side 4; 15 of side 6; 4 of side 8; and 1 of side 10. That
makes 95.`

`The upside-down case is also easy. These are the same in number
as`
`the upside-down equilateral triangles. The bottom-most point
of the`
`equilateral triangle is the obtuse vertex of the ABc triangle.
So`
`there are 95 of these, too.`

`case Abc: The smallest Abc triangle is composed of 2 of the little`
`triangles in the diagram. It is 1/3 of an equilateral triangle.
In`
`the case of right-side-up equilateral triangles, the entire`
`equilateral triangle is in the diagram, so the answer is the same
as`
`the ABD case: 220.`

`The upside-down case requires more counting. The designated
point in`
`these triangles is the Ab intersection. There are 45 such
points in`
`the diagram. There are 9 points with just 1 triangle each;
8 have 2,`
`13 have 3; 5 have 4; 4 have 5; 5 have 6; and 1 has 7. This
total is`
`141.`

`case Aab: The smallest Abc triangle is just 1 of the little
triangles`
`in the diagram. It is 1/6 of an equilateral triangle.
First, I count`
`the ones that are easily contained
in right-side up equilteral`
`triangles. Note that the entire right-side-up
equilateral triangle`
`need not be in the diagram, so there is
something to count. The`
`designated point is the Ab intersection. There
are 55 such points.`
`There are 10 points with just 1 triangle; 9 have 3;
8 have 4; 7 have`
`6; 6 have 7; 5 have 9; 4 have 10; 3 have 12; 2 have 13; and
1 has 15.`
`The total is 315. (This is 220 +
95, the number of equilateral`
`triangles oriented with the edges of the diagram, but
I don't see an`
`obvious relationship that would predict this.)`

`The Ab intersection is the designated point for the upside-down
case,`
`too. There are 45 relevant vertices. There are 9 points
with just 2`
`triangles; 8 have 3; 7 have 4; 11 have 6; 4 have 8; 3 have 9; 2
have`
`10; and 1 has 12. That is a total of 227.`

`case abc: The smallest abc triangle is composed of just 2 of the`
`little triangles in the diagram. An abc triangle has a vertical
edge`
`either on the left or on the right. By symmetry, the counts
are the`
`same for both cases. The topmost point in an abc triangle
can be in 3`
`types of places: the centroid of a right-side-up triangle, the`
`centroid of an upside-down triangle, or at the vertex of a 6-triangle`
`equilateral triangle. There are 45 places to count in each
of the 3`
`cases. Let's start with upside-down centroids. There
are 9 along the`
`bottom with just 1 (oriented) abc triangle; 15 have 2; 6 have 4;
9`
`have 5; 3 have 7; and 3 have 8. That is a total of 153.`

`Now let's count for the centoids of the right-side-up triangles.`
`There are 9 with just 1 triangle each; 8 have 2; 7 have 3; 6 have
4; 5`
`have 5; 4 have 6; 3 have 7; 2 have 8; and 1 has 9. That is
a total of`
`165.`

`Finally, let's count the ones with topmost point a vertex of the`
`obvious equilateral triangles. There are 45 interesting vertices.`
`There are 9 points with just 1 triangle each; 15 have 3; 6 have
4; 9`
`have 6; 3 have 7; and 3 have 9. That is a total of 180.
That make a`
`total of 498 triangles for a particular orientation of abc.`

`Now let's add everything up.`
`ABC: 1 * (220 + 95) = 315`
`AaB: 6 * (220 + 126) = 2076`
`ABc: 3 * ( 95 + 95) = 570`
`Abc: 3 * (220 + 141) = 1083`
`Aab: 6 * (315 + 227) = 3252`
`acb: 1 * (498 + 498) = 996`
`total =
8292`

`I have also written a program to count the triangles. I was
gratified`
`to see that it got the same answer. It is possible that I
should have`
`counted triangles of a particular shape and size, rather than`
`triangles of a particular shape with a given vertex. That
amounts to`
`interchanging the order of a summation, but it might have made
some`
`things clearer.`

`-----`

`When I wrote my program, I used the following technique for`
`identifying co-linear points. I embedded the diagram in the
plane`
`x+y+z=10. I identified the extreme points of the diagram
with`
`(10,0,0), (0,10,0), and (0,0,10).`

`The points of intersection are`
`(i,j,k) i,j,k are integers in [0,10] and i+j+k=10`

`(i+1/2, j+1/2, k) i,j,k are integers in [0,9] and i+j+k=9`
`(i+1/2, j, k+1/2)`
`(i, j+1/2, k+1/2)`
`(i+1/3, j+1/3, k+1/3)`

`(i+2/3, j+2/3, k+2/3) i,j,k are integers in [0-8] and i+j+k=8.`

`The lines in the diagram are`
`x=integer`
`y=integer`
`z=integer`
`x-y=integer`
`x-z=integer`
`y-z=integer`

`Solution by Wei-Hwa Huang``
`

`here is his PDF file.`

Torsten Sillke also solved this problem... and was also asked by Singmaster! http://www.mathematik.uni-bielefeld.de/~sillke/SEQUENCES/grid-triangles