3
$\begingroup$

There is a 5 by 5 matrix of points on a plane. How many triangles can be formed using points on this matrix?

  • 1
    Count the triples of points which do not give a triangle, and then subtract from the total.2010-11-01

1 Answers 1

5

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
  • 0
    Thanks 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