Given any N number of points, what is the maximum number of triangles that can be formed, given N number of points, given that no segment is part of more than 1 triangle, and given that no more than 2 points are colinear? That is, what is the general formula/method to calculate the maximum number of triangles that can be formed with the aforementioned parameters?
For example: if the points are A, B, C, etc., one of the triangles would be ABC. As a result, AB, AC, and BC cannot be part of any other triangles formed (ABD would NOT be a valid triangle). However, points can be shared between triangles. So given this example, another triangle ADE is possible, because it does not contain the line segments AB, AC, or BC.
As an extension of this question, is there a way to know which number of points will give us triangles that use every line segment? That is to say, the maximum number of triangles is [MATH]{N \choose 2}/3[/MATH], given that N is the number of points?
Here is what I have come up with so far:
Given any N number of points, the number of edges/line segments that can be formed is [MATH]{N \choose 2}[/MATH]. If each of these edges was used only once to make a triangle, the theoretical maximum number of triangles that can be created is the number of edges, divided by three: [MATH]{N \choose 2}/3[/MATH]
For example, given 7 points, the number of edges would be [MATH]{7 \choose 2} = 21 [/MATH], and the theoretical maximum number of triangles would be [MATH]{N \choose 2}/3 = 7.[/MATH]
However, the theoretical maximum does not guarantee that that configuration of triangles is possible under our parameters (no line segment can be used more than once). For example, 4 points would give us 6 edges and theoretically 2 triangles. However, given that the points are ABCD, the first triangle would be ABC. That leaves the remaining segments to be AD, BD, and CD, which cannot form a triangle. Therefore, the maximum number of triangles formed with 4 points (under our parameters) would be 1.
It is apparent that the number of points that can possibly use all edges to make triangles are only the ones in which the number of edges is divisible by 3. So 4, 6, 7 points gives us 6, 15, 21 edges, respectively, which can use every edge to make triangles. However, 5 points give us 10 edges. Therefore, it is not possible to use every edge to make triangles; the theoretical maximum number of triangles is 3, with 1 edge unused. With this in mind, the set of number of points that is not possible to use every edge is [MATH]3\mathbb{Z}^+ + 2[/MATH], where [MATH]\mathbb{Z}^+ = {1, 2, 3, ...}[/MATH]
As far as my work, I've been able to come up with configurations for 7 and 9 points that use every edge. Assume that the points are A, B, C, etc. They are as follows:
7 points:
ABC, ADE, AFG, BDF, BEG, CDG, CEF
9 points:
ABC, ADG, AEI, AFH, BDI, BEH, BFG, CDH, CEG, CFI, DEF, GHI
I've confirmed that both of these configurations use every line segment (AB, AC, AD, etc.). They also line up with the predicted theoretical maximum number of triangles that can be formed (7 points = 7 triangles, 9 points = 12 triangles)
These 2 configurations were brute-forced, so I don't have any way to take how I came up with these two configurations and apply it to a general solution. On top of that, both configurations were solved using 2 different methods; neither of which can be applied to the other. (the method that I used for 7 doesn't work for 9, and vice versa).
Here is the method that I used to get 7 points.
Start with 3 points: ABC. This is the first triangle that we make, so we can add AB, BC, and AC to the banned list of edges.
For 4 points [ABC]+D, we’ve already tested all the sets with [ABC], so there’s no need to test them again. Any new triangles we create must contain D; however, none of the new triangles can contain AB, BC, or AC. This is not possible; therefore only 1 triangle is possible with 4 points.
For 5 points [ABCD]+E, given the banned list of edges, the first triangle we can make is ADE. This now adds AD, AE, and DE to the banned edges list. At this point, no new triangles can be made, because for B, AB and BC are gone, and for C, AC and BC are gone.
Working our way up, 6 points [ABCDE]+F, we can make BDF (adding BD, BF, and DF to the banned list) and CEF (adding CE, CF, and EF).
Getting to 7 points (+G), we can make AFG, BEG, CDG. This uses all the line segments.
However, this method doesn’t work for 9. Continuing up the points, 8 points (+H) adds no new triangles, and 9 points (AHI) only adds one. Using this method, we predict that 8 triangles are possible, when in fact 12 triangles can be done.
Here is the method for 9 points:
For 9 points I kind of got lucky. I arranged the letters in a grid:
ABC
DEF
GHI
I ran through the vertical set (ADG, BEH, CFI), the horizonal set (ABC, DEF, GHI), Rightward diagonals (AEI, BFG, CDH), and the leftward diagonals (CEG, AFH, BDI). The diagonals I allowed for wrap-around.
This gave me the 12 triangles that I was looking for. I got lucky; I don't see how this can be applied to any other number of points (certainly not 7).
Any help would be greatly appreciated.
For example: if the points are A, B, C, etc., one of the triangles would be ABC. As a result, AB, AC, and BC cannot be part of any other triangles formed (ABD would NOT be a valid triangle). However, points can be shared between triangles. So given this example, another triangle ADE is possible, because it does not contain the line segments AB, AC, or BC.
As an extension of this question, is there a way to know which number of points will give us triangles that use every line segment? That is to say, the maximum number of triangles is [MATH]{N \choose 2}/3[/MATH], given that N is the number of points?
Here is what I have come up with so far:
Given any N number of points, the number of edges/line segments that can be formed is [MATH]{N \choose 2}[/MATH]. If each of these edges was used only once to make a triangle, the theoretical maximum number of triangles that can be created is the number of edges, divided by three: [MATH]{N \choose 2}/3[/MATH]
For example, given 7 points, the number of edges would be [MATH]{7 \choose 2} = 21 [/MATH], and the theoretical maximum number of triangles would be [MATH]{N \choose 2}/3 = 7.[/MATH]
However, the theoretical maximum does not guarantee that that configuration of triangles is possible under our parameters (no line segment can be used more than once). For example, 4 points would give us 6 edges and theoretically 2 triangles. However, given that the points are ABCD, the first triangle would be ABC. That leaves the remaining segments to be AD, BD, and CD, which cannot form a triangle. Therefore, the maximum number of triangles formed with 4 points (under our parameters) would be 1.
It is apparent that the number of points that can possibly use all edges to make triangles are only the ones in which the number of edges is divisible by 3. So 4, 6, 7 points gives us 6, 15, 21 edges, respectively, which can use every edge to make triangles. However, 5 points give us 10 edges. Therefore, it is not possible to use every edge to make triangles; the theoretical maximum number of triangles is 3, with 1 edge unused. With this in mind, the set of number of points that is not possible to use every edge is [MATH]3\mathbb{Z}^+ + 2[/MATH], where [MATH]\mathbb{Z}^+ = {1, 2, 3, ...}[/MATH]
As far as my work, I've been able to come up with configurations for 7 and 9 points that use every edge. Assume that the points are A, B, C, etc. They are as follows:
7 points:
ABC, ADE, AFG, BDF, BEG, CDG, CEF
9 points:
ABC, ADG, AEI, AFH, BDI, BEH, BFG, CDH, CEG, CFI, DEF, GHI
I've confirmed that both of these configurations use every line segment (AB, AC, AD, etc.). They also line up with the predicted theoretical maximum number of triangles that can be formed (7 points = 7 triangles, 9 points = 12 triangles)
These 2 configurations were brute-forced, so I don't have any way to take how I came up with these two configurations and apply it to a general solution. On top of that, both configurations were solved using 2 different methods; neither of which can be applied to the other. (the method that I used for 7 doesn't work for 9, and vice versa).
Here is the method that I used to get 7 points.
Start with 3 points: ABC. This is the first triangle that we make, so we can add AB, BC, and AC to the banned list of edges.
For 4 points [ABC]+D, we’ve already tested all the sets with [ABC], so there’s no need to test them again. Any new triangles we create must contain D; however, none of the new triangles can contain AB, BC, or AC. This is not possible; therefore only 1 triangle is possible with 4 points.
For 5 points [ABCD]+E, given the banned list of edges, the first triangle we can make is ADE. This now adds AD, AE, and DE to the banned edges list. At this point, no new triangles can be made, because for B, AB and BC are gone, and for C, AC and BC are gone.
Working our way up, 6 points [ABCDE]+F, we can make BDF (adding BD, BF, and DF to the banned list) and CEF (adding CE, CF, and EF).
Getting to 7 points (+G), we can make AFG, BEG, CDG. This uses all the line segments.
However, this method doesn’t work for 9. Continuing up the points, 8 points (+H) adds no new triangles, and 9 points (AHI) only adds one. Using this method, we predict that 8 triangles are possible, when in fact 12 triangles can be done.
Here is the method for 9 points:
For 9 points I kind of got lucky. I arranged the letters in a grid:
ABC
DEF
GHI
I ran through the vertical set (ADG, BEH, CFI), the horizonal set (ABC, DEF, GHI), Rightward diagonals (AEI, BFG, CDH), and the leftward diagonals (CEG, AFH, BDI). The diagonals I allowed for wrap-around.
This gave me the 12 triangles that I was looking for. I got lucky; I don't see how this can be applied to any other number of points (certainly not 7).
Any help would be greatly appreciated.
