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

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

-
If you include "degenerate" triangles, in which the three vertices are on a straight line, then, since there are $25$ points in the grid, it would be just $\dbinom{25}{3}=2300$, the number of ways to choose three points out of $25$. So maybe the "hard" part of this problem is figuring out how many degenerate triangles must be subtracted from $2300$. –  Michael Hardy Jan 10 at 18:46
I should have been more specific. I want to know how to determine the number of non degenerate triangles that make up this grid. –  user2081893 Jan 10 at 18:47
Why not try a 2x2 grid, and then a 3x3, etc.? –  Matthew Conroy Jan 10 at 20:59
According to the answer given at the math completion I attended, the answer is 2148. So far no answer has given that number –  user2081893 Jan 13 at 1:10

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 we 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 any 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 check the details above closely since I haven't.

-
$2\binom 1 3 + 2\binom 2 3 + 2\binom 3 3 + 2\binom 4 3 + 2\binom 5 3 = 30$ not 58 –  Nate Jan 10 at 21:39
@Nate : Thank you. I've fixed that issue. Maybe there are others. –  Michael Hardy Jan 10 at 23:39

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.

-
I think you missed some. –  Michael Hardy Jan 10 at 21:14
Ahh you are right, I missed the 4 lines of slope 1 or -1 with three points on them so it should be 2148 by my count now. –  Nate Jan 10 at 21:36
. . . and also those of slope $\pm1/2$ and $\pm2$. –  Michael Hardy Jan 10 at 23:40