The discussion focuses on calculating the number of triangles in a complex geometric figure using combinatorial methods rather than brute force counting. Participants suggest creating a 25x25 matrix to represent connections between vertices and employing a counting algorithm to identify triangles formed by intersecting lines. The conversation highlights the importance of considering symmetries and the need to account for singular triangles, which have overlapping vertices. Ultimately, the method involves calculating combinations of intersecting lines and adjusting for duplicates to arrive at an accurate count.
PREREQUISITESMathematicians, educators, and students interested in advanced geometry, combinatorial analysis, and algorithm design will benefit from this discussion.
I think that misses a triangle 1-24-20, for example, IIUC (see image in #2 above.)Lnewqban said:
Ok. You can figure the upper bound of total possible triangles and go down from there.Hill said:
And 1-7-24 as well.Hill said:
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 said:
You have caused me to see there are 8 less than I thought. Thanks!Hill said:
I can solve the problem by using a combination of brute force counting and symmetry.bob012345 said:
Don’t forget these;Gavran said:
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.bob012345 said:
# 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";
}I enjoyed thinking about it. Just for fun of finding an alternative approach.FactChecker said:
I'm not sure what you mean here.Hill said:
I think that’s correct. I was thinking along those lines too as I tried to apply the logical method to this figure;Hill said:
I think the intent is that it would not count. Only vertices in the original figure count.FactChecker said:
2) The solution based on counting triads of intersecting lines.FactChecker said:
It certainly complicates symmetry arguments.Hill said:
The first statement answered the question,FactChecker said:
---------------------------------------FactChecker said:
Sure, but not every three non-parallel lines necessarily make a triangle in a given figure.FactChecker said:
Perhaps so. I have yet to make a simple regular hexagon work but one can see the answer by inspection!FactChecker said:
I see. The solutions that depend on counting combinations of 3 lines don't work. That and the need for symmetry is key to most of the ideas here. The solutions are not very "robust". I have a general preference for robust approaches, but they are often not elegant.Hill said:
brute force counting and then work backwardsbob012345 said:
The answer is 160. I'm also looking for a way backwards.OmCheeto said: