how to solve triangles count puzzle

Question

Below is a puzzle of counting triangles.How to solve such puzzle ?

source: http://gpuzzles.com/mind-teasers/how-many-triangles-challenge/?source=stackmath

Answer 1

Be systematic. Label all your points. Choose a unique label for each triangle, e.g. by listing point labels in alphabetic order. Enumerate triangles in some order so you can check for them one at a time. I'd suggest lexicographic order.

Exploit symmetry. Many triangles will occur four times, or even eight times, throughout the figure in rotated and posibly reflected versions of one another. So you can keep the work down if you find only one representative of each such group, as long as you make sure to get the associated count right.

Combining these ideas, I'd label the figure like this:

Then you can enumerate triangles like this:

• Axy: $4ABB, 0ABC, 8ABE, 8ABF, 0ACC, 0ACD, 0ACE,$
  $\qquad 8ACF, 0ADD, 0ADE, 8ADF, 0AEE, 0AEF, 4AFF$
• Bxy: $4BBB,0BBC,0BBD,0BBE,4BBF,0BCC,0BCD,0BCE,$
  $\qquad 8BCF,0BDD,0BDE,8BDF,0BEE,8BEF,4BFF$
• Cxy: $0CC*, 0CDD, 0CDE, 8CDF, 0CE*, 4CFF$
• Dxy: $0DD*, 0DE*, 0DFF$
• Exy: $0EE*, 0EFF$
• Fxy: $4FFF$

So you get a total of

$$(4+8+8+8+8+4)+(4+4+8+8+8+4)+(8+4)+4=92$$

unless I (still) made a mistake. But since this solution now agrees with the $92$ stated on the original problem statement question, I trust it might (finally) be correct now. Thanks to TonyK for spotting the one I had missed! My first attempt was way lower, so you really have to be very systematic to get this even close to correct.

Originally I had a higher count, namely $104$ (would be $108$ by now with my other fixes), but that's because I'd assumed $BCF$ to be collinear so I had $8ABC$ and $8BBC$. Jyrki pointed out in a comment that it doesn't look like that in your original post, even though it's close.

The same approach can be applied to other, similar tasks, as demonstrated in this post.

Answer 2

Here’s a solution that only requires specifying the sets of collinear points of the diagram as input to a computer program. It’s similar to triangle counting with an adjacency matrix (using the trace of the cube of the adjacency matrix), but it uses an edge adjacency matrix, not a vertex adjacency matrix, and it accounts for the fact that collinear edges cannot be part of the same triangle.

Let $V$ be the set of vertices in the diagram $D$. Define the set of edges of $D$ as the ordered pairs of vertices that are connected, just as usual for a directed graph. For an undirected graph, let both $(v,w)$ and $(w,v)$ be edges if $v$ and $w$ are adjacent.

Now for the new part. (The code below will do this, given as input just the “lines” of $D$, which are much easier to list by hand than the edges.)

Define an adjacency matrix $M$ for the edges of $D$. Consider the edge $(v,w)$ to be adjacent to $(v',w')$ if $w=v'$ and the edges are not collinear. In other words, the edges, if followed one after the other, form a “bent angle” in $D$. Note that an edge is not adjacent to itself by this definition.

Now consider $M^3$. Its $(i,j)$ entry equals the number of 4-edge sequences $e_i, e_2, e_3, e_j$ where a non-straight angle is formed from $e_i$ and $e_2$, from $e_2$ and $e_3$, and from $e_3$ and $e_j$. If $j=i$, this is a non-degenerate triangle.

Each non-degenerate triangle will be counted six times: once for each starting edge and once for each orientation (clockwise or counter-clockwise). So the number of triangles is $\dfrac{tr(M)}{6}$.

Here is Mathematica code for this example. I’ve used MvG’s labeling of the vertices. There are 204 edges in the diagram, but only 28 lines, so the data entry and manual requirements aren’t bad. To find the number of triangles in any diagram, all that needs to be modified is the list of lines.

lines={
{"A1","B2","B4","C2","C4","D2","D4"},{"A1","B1","B3","C1","C3","D1","D3"},
{"A1","E2","E4","F2","F4"},{"A1","E1","E3","F1","F3"},
{"D3","F2","F3"},{"D4","F3","F4"},{"B3","B4","E3"},{"B2","B3","E2"},
{"D2","F1","F2"},{"D1","F1","F4"},{"B1","B4","E4"},{"B1","B2","E1"},
{"C4","F3"},{"B3","F3"},{"C3","F3"},{"B4","F3"},
{"B3","F2"},{"C2","F2"},{"C3","F2"},{"B2","F2"},
{"B4","F4"},{"C1","F4"},{"B2","F1"},{"C1","F1"},
{"C4","F4"},{"B1","F4"},{"C2","F1"},{"B1","F1"}
};

isedge[p_]:=Max[Map[Length,Map[Intersection[p,#]&,lines]]]==2;

edgeset= Select[Tuples[{Union[Flatten[lines]],Union[Flatten[lines]]}],isedge[#]&];

makesangle[e1_,e2_]:=
Length[Intersection[e1,e2]]==1&&
isedge[e1]&&isedge[e2]&&e1[[2]]==e2[[1]]&&
Max[Map[Length,Map[Intersection[Union[e1,e2],#]&,lines]]]<=2;

adjacentEdgePairs=Select[Tuples[{edgeset,edgeset}],makesangle[#[[1]],#[[2]]]&];

edgeadjacencymatrix=
Map[{Position[edgeset,#[[1]]][[1]][[1]],
Position[edgeset,#[[2]]][[1]][[1]]}->1& ,adjacentEdgePairs];

m=SparseArray[edgeadjacencymatrix,{Length[edgeset],Length[edgeset]}];
Tr[m.m.m]/6

The result is 92, as expected.