How many triangles?
A generalized formula for this famous math problem:
How many triangles can be formed by connecting the dots in figure 1?
Hold on. You definitely don’t want to draw every one of the 76 possible triangles: I’m not even sure if that’s achievable. Let’s try out something smarter, math ^_^
The solution to the problem
It’s always important to rephrase the problem in a way that tells you exactly what you need to do. The problem is asking us how many triangles we can draw with the dots in figure 1 so that no three sets of dots are used to draw more than one triangle. This means, each triangle has to be formed by three different sets of dots.
The next thing to do is define what a triangle is, making sure the definition is relevant to the problem. A triangle is a polygon formed by connecting any three non-collinear points. By that definition, if we want to form a triangle, then we will have to connect three non-collinear dots.
The solution to the problem now becomes finding the number of ways that we can connect any three non-collinear dots in figure 1. We can do this by finding how many different sets of three dots can be formed from nine dots and then subtracting the number of those sets that contain collinear dots. 9 combination 3 gives us number of different sets of three dots, which is 84. Out of those sets, only 8 contain collinear dots (three vertical, three horizontal and 2 diagonal). Thus, we can draw 76(84–8) triangles by connecting the dots in figure 1.
The Generalization
We just found how many triangles we can draw on 3 by 3 dot grid. What if we’re given a 4 by 4 dot grid? Doesn’t sound difficult, does it? Ok, what about a 10 by 10 grid or even a 50 by 50 grid? We can all agree it gets super complicated at some point and so it’s always nice when there is a general formula floating somewhere on the internet. Let’s make that formula. So now we’re going to find the number of triangles that can be drawn on a n by n dot grid.
To do that, we need to keep finding the number of triangles than be drawn on a number of dot grids until we’re able to see a trend (some sort of progression). We’ll do this for 0 < n < 7.
Please keep in mind this formula we developed at the beginning: number of triangles = number of different sets of three dots - number of those sets that contain collinear dots.
We’ve already discussed n=3 and n=1,2 are just the number of different sets of three dots that can be formed from the number of dots in the grid. For n=4, there are sixteen dots and so 16 combination 3 different sets of three dots. There are also ten sets of four collinear dots (for vertical, four horizontal and two diagonal). But the four collinear dots can give us 4 combination 3 sets of three dots each and so we subtract 10×(4 combination 3). Looking at the dot grid carefully, one can see that there are other diagonals ranging from 1 to 3 collinear points and there are 4 of each of those. But we’re only concerned about the collinear dots that are 3 or more long and so subtract 4×(3 combination 3). The same analysis is done for n=5,6.
Now let’s fish out the trends in figure 2 and discuss them. For any n by n grid, there are n² dots and so there will always be n² combination 3 sets of three dots. The longest collinear points are n dots long and there are always 2(n+1) of them. We can therefore subtract 2(n+1)×(n combination 3). Apart front the longest diagonals which are n dots long, there are four each of diagonals which are n-1 to 1 long. And so we subtract those as well. Putting all this in math language, gives us the general formula:
From figure 3 it can be seem that the k=1,2 terms are both zero and so for n>3, the summation can begin from k=3.
Now we can find the number of triangles on any square(that is, n by n) dot grid. Neat!
What happens though when n approaches infinity? I believe the number of triangles will also approach some infinity. It would be nice to see a convergence test or some sort of similar analysis in the comments. Ask questions too I’ll answer, I promise.
Don’t forget to leave a clap :)
Edit: As pointed out by a reader in the comments section, the formula fails to account for the total sets of 3 dots that contain collinear dots (in other words, some collinear dots are not accounted for in the formula) in dot grids of side lengths greater than 4 units. Because of this a new post has been made to discuss an algorithm I devised to do the counting of the newly found collinear dots. Check out “How many triangles? Part 2” to read about that.
