How many triangles can be created from a grid of certain dimensions?

Question

How would you determine how many non-degenerate triangles can be drawn by connecting points in a $5 \times 5$ grid?

Answer 1

First choose 3 points arbitrarily this gives $\dbinom{25}{3}=2300$ possibly degenerate triangles.

Now we need to subtract off triples that all lie in a line:

There are 12 lines (5 vertical, 5 horizontal, and the main diagonals) containing 5 points these contribute $12\cdot\dbinom{5}{3}=120$ degenerate triangles.

There are 4 lines (off diagonals) containing 4 points. These contribute $4\cdot\dbinom{4}{3}=16$ degenerate triangles.

Finally, there are 12 lines with exactly 3 points (3 of each with slopes 2,-2, 1/2 , -1/2) which contribute 12 total degenerate triangles.

So 2300 total triangles minus 120+16+12 degenerate triangles gives 2152 nondegenerate triangles.

Answer 2

Maybe the quickest way to do this is to take the number of triangles including degenerate ones, and subtract the number of degenerate triangles.

The number of ways to choose three points out of 25 is $$ \binom{25}{3} = 2300. $$

Now consider how to count the number of degenerate triangles, i.e. those in which the three vertices are collinear. The possible slopes of the lines are $0,\infty,\pm1,\pm2,\pm\frac12$. The quickest way to see that is just staring at the grid. For example, with slope $1/3$, only two points on the grid can be found on the line.

With slope $0$, there are five possible lines and from one of those we must choose three points, so we get $$ 5\cdot\binom 5 3 = 50 $$ degenerate triangles. And the same with slope $\infty$.

With slope $1$, we have two lines of length $1$, two of length $2$, two of length $3$, two of length $4$, and just one of length $5$. Hence, the number of degenerate triangles is $$ 2\binom 1 3 + 2\binom 2 3 + 2\binom 3 3 + 2\binom 4 3 + 2\binom 5 3 = 30. $$ And the same with slope $-1$.

Now on to slope $1/2$. There are only three degenerate triangles with slope $1/2$. Call them $$ \{(1,1),(3,2),(5,3)\} + (1,k) \text{ for }k=0,1,2. $$ Look at the grid and you'll see this. Similarly, there are three with slope $-1/2$ and three with each of the slopes $\pm2$.

Now add them up: $$ 50+50+30+30+3+3+3+3 = 172. $$

Hence, $$ 2300 - 172 = 2128. $$ non-degenerate triangles.

But you should closely check the details above since I haven't.

Answer 3

It is as easy as it seems to be. This problem can be solved by combination and permutation techniques. What you need is that create as many as triangles as can be without creating a line (three collinear points will make a line out of a triangle). A triangle is formed with three noncollinear points. But there can be two collinear (here by collinear I mean being in the same row, column or diagonal) points. Just as combination you have 25 points (5x5 grid gives 25 slots) so 1st point could be from any of these i.e. 1st point can be placed in any of these 25 points. For the 2nd point there is no condition of any point being collinear or noncollinear (but let this pt be collinear with the 1st one although two pts are always collinear) so the second point has 24 points excluding the 1st one. So 2nd point can take any of these 24 points. For the third one, this point cannot be collinear to 1st and 2nd (if 1st and 2nd are collinear and if they are not then this can be collinear to either 1st or second and then consider this point to be the second one and the second point to be third point so that the three pts be non collinear) points both. So this must deduce some points from the remaining 23 slots. This deduce 3 points from the grid so the remaining slots are 20. This formula can be devised as for n*n grid Total no. of triangles are (n*n)*((n*n)-1)*(((n*n)-2)-(n-2)) = (n*n)*((n*n)-1)*((n*n)-n) . This formula can be used to calculate no. of triangles for n*n no. of grid.

So with the above formula and as said above the no. of triangles in a 5*5 grid becomes (5*5)*((5*5)-1)*((5*5)-5) = 25*24*20 just as the no. of slots I deduced above which comes out to be 12000 no. of triangles.

Also the number of triangles that comes out with this formula consists of too many repeated (by repeated I mean the triangles formed by the same points so the congruent triangles are excluded in this type) triangles. So how to remove these triangles which have repeated and also how many times have they be repeated. This is a simple trick which can be solved by factorialisation. We know that how many points a triangles consists of, obviously only 3 points (vertices). On a grid these three points will repeat themselves 3! (3 factorial) no. of times to form one triangle (6 triangles in all but all are same). So with this we can deduce that in every 6 triangles there are 5 fake ones and 1 real one. So the real : fake ratio becomes 1:5 . So the total no. of triangles omitting the fake ones becomes 1/6th the no. of triangles we got by above formula. So for a 5*5 grid total no. of triangles becomes 12000/6 = 2000. Yes 2000 different triangles but there can be and there are many congruent triangles.

This formula can be applied to other polygons to (with some modifications) and can be used. Also if someone fails to understand this answer I can post images here (although I don't know how as there is no image posting symbol like in SU).