There is a 5 by 5 matrix of points on a plane. How many triangles can be formed using points on this matrix?
There is a 5 by 5 matrix of points on a plane. How many triangles can be formed using points on this matrix?
-
1Count the triples of points which do not give a triangle, and then subtract from the total. – 2010-11-01
1 Answers
This is the obvious approach (to me, at least), and is mostly a matter of bookkeeping. To begin with, there are ${{5^2} \choose 3}$ sets of three points. However, some of these are colinear, which we don't want to count.
There are $2 \times 5 \times {5 \choose 3}$ horizontal or vertical sets of three colinear points. E.g.
.xxx. .....
..... ...x.
..... ...x.
..... .....
..... ...x.
There are $3+3+3+3$ sets of three colinear points with rise/run $\in {\pm 2, \pm 1/2}$.
x.... ..x..
..x.. .....
....x ...x.
..... .....
..... ....x
...x. .....
..... ....x
..x.. ..x..
..... x....
.x... .....
There are $2 \times {5 \choose 3}$ sets of three colinear points with rise/run $\in {\pm 1}$ along the main diagonal or main anti-diagonal.
x.... .....
.x... ...x.
..x.. ..x..
..... .....
..... x....
There are $4 \times {4 \choose 3}$ sets of three colinear points along the "shunted" main diagonal and main anti-diagonal (is there a better name for these diagonals?).
.x... ...x. ..... .....
..... ..x.. x.... .....
...x. ..... .x... ...x.
....x x.... ..x.. ..x..
..... ..... ..... .x...
Finally, there are these $4$ remaining:
..x.. ..x.. ..... .....
.x... ...x. ..... .....
x.... ....x x.... ....x
..... ..... .x... ...x.
..... ..... ..x.. ..x..
So there are \[{{5^2} \choose 3}-2 \times 5 \times {5 \choose 3}-(3+3+3+3)-2{5 \choose 3}-4{4 \choose 3}-4=2148\] triangles that can be formed. I also checked this answer with some code in GAP.
[Here, I have assumed that you want to count congruent triangles separately.]
-
0+1. I believe "antidiagonal" is already standard terminology, though I've seen the more elaborate "northeast-southwest diagonal" being used. – 2010-11-01
-
0Thanks for the answer. Beautifully explained.The question now indeed appears fairly simple but I am not a mathematician (or even a math student anymore) :) – 2010-11-02