Undergrad Find the Number of Triangles

[bob012345]

TL;DR

Find the number of triangles in this busy figure.

The game is to find the number of triangles in this complicated figure by other than brute force counting and explain your method.

 

[Hill]

I'd start with marking the vertices, e.g.,

Then, I'd make a 25x25 matrix with 1s for each pair of vertices connected by straight line, e.g., (1,2), (1,5), (1,13), ..., (2,5), (2,13), ... .
Then, I'd run a counting algorithm like this:
for i=1 to 25
.......for j=1 to 25
..............if M(i,j)=1 then
.......................for k=j+1 to 25
..................................if M(i,k)=1 then
...........................................if M(j,k)=1 then count+1
At the end, I'd divide the count by 6.

There should be a better way, because I didn't use any symmetries of this specific figure.

 

[FactChecker]

I would consider that to be automating a "brute force counting" method. IMO, although it is not what the OP asked for, it is still an essential step to verify the answer from an analytical method.

 

[Hill]

It can be approached as a combinatorics problem.
Mark the lines, e.g.,

Every three lines that intersect, make a triangle.
There are 12 lines. Line 1 intersects 10 other lines (not 11 other lines because there is one line parallel to it.) After the second line is selected, there are 9 or 8 possible third lines (all but the lines 3, 6, 8, and 10 have parallel lines). These combinations give the number of triangles with one of the sides being line 1. We can remove line 1 now.
There are 11 lines now to pick from, 2 to 12. And so on.

 

[Lnewqban]

Using symmetry:
8 triangles per half-quadrant times 8?

 

[Hill]

Using symmetry:
8 triangles per half-quadrant times 8?

I think that misses a triangle 1-24-20, for example, IIUC (see image in #2 above.)

 

[bob012345]

It can be approached as a combinatorics problem.
Mark the lines, e.g.,
View attachment 368465
Every three lines that intersect, make a triangle.
There are 12 lines. Line 1 intersects 10 other lines (not 11 other lines because there is one line parallel to it.) After the second line is selected, there are 9 or 8 possible third lines (all but the lines 3, 6, 8, and 10 have parallel lines). These combinations give the number of triangles with one of the sides being line 1. We can remove line 1 now.
There are 11 lines now to pick from, 2 to 12. And so on.

Ok. You can figure the upper bound of total possible triangles and go down from there.

 

[Lnewqban]

I think that misses a triangle 1-24-20, for example, IIUC (see image in #2 above.)

And 1-7-24 as well.

 

[Hill]

Ok. You can figure the upper bound of total possible triangles and go down from there.

We need to subtract the "singular" triangles, i.e., "triangles" with their three vertices overlapping. This happens in the vertices 7, 12, 19, 18, 17, 13, 5, 3, and 6 (I refer to the image in the #2 above.)

 

[bob012345]

We need to subtract the "singular" triangles, i.e., "triangles" with their three vertices overlapping. This happens in the vertices 7, 12, 19, 18, 17, 13, 5, 3, and 6 (I refer to the image in the #2 above.)

You have caused me to see there are 8 less than I thought. Thanks!

 

[FactChecker]

I think that even brute force counting would be challenging. And being confident that a mathematical method works would be very hard unless the correct answer is known (probably from some trusted brute force counting.)

 

[Hill]

There are 12 ordered pairs of "internal" lines like these:

For each, there are 10 possible choices of a third line. Total: 12*10 triangles.
There are 48 ordered pairs of non-parallel "external" lines like these:

For each, there are 8 possible choices of a non-parallel third line. Total: 48*8 triangles.
There are 32 "mixed" pairs like these:

For each, there are 9 possible choices of a non-parallel third line. Total: 32*9 triangles.
Add up, divide by 6, subtract as per post #9.

 

[Gavran]

The game is to find the number of triangles in this complicated figure by other than brute force counting and explain your method.

I can solve the problem by using a combination of brute force counting and symmetry.

Spoiler

There are 17 different triangles, which I have calculated by using brute force counting. (See Figures 1 and 2.)

Figure 1

Figure 2

Among them, 15 triangles repeat 8 times and 2 triangles repeat 4 times because of symmetry. The final result is 15×8+2×4=128.

 

[bob012345]

I can solve the problem by using a combination of brute force counting and symmetry.

Spoiler

There are 17 different triangles, which I have calculated by using brute force counting. (See Figures 1 and 2.)
View attachment 368478
Figure 1

View attachment 368479
Figure 2

Among them, 15 triangles repeat 8 times and 2 triangles repeat 4 times because of symmetry. The final result is 15×8+2×4=128.

Don’t forget these;

 

[bob012345]

Here are my results;

Spoiler

Assuming I haven’t made a mistake which is entirely possible..

Take the 12 lines by groups of three which give 220 theoretical triples which are contenders for triangles. There are four groups of parallel lines which when combined with the other lines yield 40 triplets to remove since a triangle cannot have two parallel sides. There are 8 cases internal to the figure where three lines cross at one point which cannot form a triangle. There are 8 points which also have three lines meeting at a point. Lastly, the center vertex has four lines crossing which taken 3 at a time eliminate another 4 triples. So we have 220-40-16-4=160.

I also count 18 with eight-fold symmetry and 4 with four-fold symmetry yielding a total of 160 triangles.

 

[FactChecker]

Here are my results;

Spoiler

Assuming I haven’t made a mistake which is entirely possible..

Take the 12 lines by groups of three which give 220 theoretical triples which are contenders for triangles. There are four groups of parallel lines which when combined with the other lines yield 40 triplets to remove since a triangle cannot have two parallel sides. There are 8 cases internal to the figure where three lines cross at one point which cannot form a triangle. There are 8 points which also have three lines meeting at a point. Lastly, the center vertex has four lines crossing which taken 3 at a time eliminate another 4 triples. So we have 220-40-16-4=160.

I also count 18 with eight-fold symmetry and 4 with four-fold symmetry yielding a total of 160 triangles.

That seems logical. This is a treacherous problem. I would feel more confident of your logic if there was a simple, brute-force, counting that gave the same answer, but everything I think of quickly gets complicated.

 

[FactChecker]

I wrote a program to do brute force counting and its answer matches that of @bob012345 in post #15.
I have not thoroughly examined the results, but I have some realistic hope that my program is correct.

Here is the program and results. Each triangle is identified by three vertices numbered as in @Hill Post #2.

Spoiler: Here is the program and results

# for brute force counting of triangles in the diagram here:
#   https://www.physicsforums.com/threads/find-the-number-of-triangles.1083666/

# Define each line by the vertices on it. Starting at top, first line and proceeding clockwise. Use the vertex numbers in post #2.
# Define labels to match the diagram in post #2 because some lines going clockwise are skipped and it's hard to keep track of.
# The top-center vertex is 9 and its lines are 9A, 9B, 9C. Other lines are identified similarly

$l[0]= " 9 4 3 5 14 15 ";  $id[0]="9A";
$l[1]= " 9 7 6 17 24 ";  $id[1]="9B";
$l[2]= " 9 10 12 19 22 25 ";  $id[2]="9C";
$l[3] = " 11 10 7 3 2 8 ";  $id[3]="11A";
$l[4]= " 11 12 6 13 15 ";  $id[4]="11B";
$l[5]= " 11 20 19 18 23 24 ";  $id[5]="11C";
$l[6]= " 21 20 12 7 4 1 ";  $id[6]="21A";
$l[7]= " 21 19 6 5 8 ";  $id[7]="21B";
$l[8]= " 21 22 18 17 16 15 ";  $id[8]="21C";
# skip first line out of 25. already done.
$l[9]= " 25 18 6 3 1 ";  $id[9]="25B";
$l[10]= " 25 23 17 13 14 8 ";  $id[10]="25C";
# skip first 2 lines out of 24. already done.
$l[11]= " 24 16 13 5 2 1 ";  $id[11]="24C";
# all the rest are done

# **********  Begin main algorithm  *******************
# loop through all combinations of 3 distince lines and look for intersections
foreach $i (0..9){
   foreach $j (($i+1)..10){
 
# ******  Define a subroutine to check for vertex intersection between two lines  ***************
sub findIntersection {
      my( $firstLine )= shift @_;
      my( $secondLine )= shift @_;

      # Each vertex in the local string, $li, will be deleted as it is looked for in the other line
      my( $li ) = $l[$firstLine];
      while( $li =~ s/(\d+)// && ! $Intersection ){
         $Vertex = $1;
         if( $l[$secondLine] =~ / $Vertex / ){
            return $Vertex; # return the vertex of the intersection
         }
      }
   return 0;  # Return 0 indicating no intersection vertex
}

# *******  Continue with main program  **********************
      $ijIntersection = &findIntersection($i, $j);
      # If the first two lines don't intersect, skip to next pair
      if( $ijIntersection == 0 ){next}
      # Get intersections of first i&j lines with k line
      foreach $k (($j+1)..11){
         $ikIntersection = &findIntersection($i, $k);
         $jkIntersection = &findIntersection( $j, $k);
         # If any intersection is zero, no triangle with those 3 lines
         if( $ikIntersection == 0 || $jkIntersection == 0 ){next}
         # If all 3 intersections are different and nonzero, it is a triangle
         if(
             $ijIntersection != $ikIntersection
             && $ijIntersection != $jkIntersection
             && $ikIntersection != $jkIntersection
         ){
            # Triangle found. Store in array @triangles
            $numTriangles++;
            push( @triangles, "$ijIntersection, $ikIntersection, $jkIntersection");
         }
      }
   }
}
print "There are $numTriangles triangles:\n";

# Sort triangles and print
foreach $triangle (sort @triangles) {
   print "$triangle\n";
}

Here are the results:
There are 160 triangles:
10, 12, 11
10, 12, 7
10, 19, 11
10, 19, 8
10, 25, 3
10, 25, 8
11, 12, 20
11, 13, 23
11, 13, 24
11, 15, 18
11, 2, 13
11, 2, 24
11, 3, 18
11, 3, 6
11, 6, 18
11, 6, 19
11, 7, 12
11, 7, 20
11, 8, 13
11, 8, 19
11, 8, 23
11, 8, 6
12, 13, 1
12, 15, 21
12, 19, 11
12, 19, 21
12, 19, 6
12, 22, 15
12, 22, 21
12, 25, 1
12, 25, 13
12, 25, 6
12, 6, 1
12, 6, 21
14, 5, 13
15, 13, 16
15, 13, 17
15, 14, 13
15, 14, 17
15, 3, 18
15, 3, 6
15, 4, 12
15, 5, 13
15, 5, 16
15, 5, 6
15, 6, 18
17, 16, 13
17, 24, 13
17, 24, 16
17, 6, 18
18, 16, 1
18, 17, 25
18, 23, 17
18, 23, 25
18, 24, 1
18, 24, 16
19, 12, 20
19, 18, 21
19, 18, 6
19, 22, 18
19, 22, 21
19, 23, 8
19, 24, 5
19, 25, 18
19, 25, 23
19, 25, 6
19, 25, 8
20, 18, 1
20, 18, 21
20, 19, 21
20, 24, 1
21, 1, 16
21, 1, 18
21, 1, 5
21, 1, 6
21, 5, 16
21, 6, 18
21, 8, 17
22, 25, 17
22, 25, 18
23, 24, 13
24, 17, 18
24, 17, 23
24, 6, 18
24, 6, 19
24, 7, 20
25, 1, 13
3, 14, 25
3, 14, 8
3, 15, 11
3, 2, 1
3, 4, 7
3, 5, 1
3, 5, 2
3, 5, 8
3, 8, 25
4, 15, 21
4, 3, 1
4, 5, 1
4, 5, 21
5, 14, 8
5, 15, 21
5, 3, 6
6, 13, 1
6, 13, 25
6, 13, 5
6, 13, 8
6, 15, 21
6, 17, 13
6, 17, 15
6, 17, 21
6, 17, 25
6, 17, 8
6, 24, 1
6, 24, 11
6, 24, 13
6, 24, 5
6, 5, 1
6, 7, 12
6, 8, 25
7, 17, 21
7, 17, 8
7, 2, 1
7, 24, 1
7, 24, 11
7, 24, 2
7, 3, 1
7, 6, 1
7, 6, 11
7, 6, 21
7, 6, 3
7, 6, 8
7, 8, 21
8, 2, 13
8, 2, 5
8, 3, 6
8, 5, 13
9, 14, 17
9, 14, 25
9, 15, 12
9, 15, 17
9, 15, 22
9, 15, 6
9, 17, 22
9, 17, 25
9, 24, 19
9, 3, 10
9, 3, 25
9, 3, 6
9, 3, 7
9, 4, 12
9, 4, 7
9, 5, 19
9, 5, 24
9, 5, 6
9, 6, 12
9, 6, 19
9, 6, 25
9, 7, 10
9, 7, 12

 

[FactChecker]

IMHO, the desire for a non-"brute force counting" method is misguided here. The logic is so specialized and convoluted that it required several erroneous tries to create a "Rube Goldberg" logic that might work. The "brute force" method still requires some tricks, but the result is much more flexible and easy to follow.

 

[Hill]

IMHO, the desire for a non-"brute force counting" method is misguided here. The logic is so specialized and convoluted that it required several erroneous tries to create a "Rube Goldberg" logic that might work. The "brute force" method still requires some tricks, but the result is much more flexible and easy to follow.

I enjoyed thinking about it. Just for fun of finding an alternative approach.