Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Count the triples of points which do not give a triangle, and then subtract from the total. –  Mariano Suárez-Alvarez Nov 1 '10 at 19:20

1 Answer 1

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.]

share|improve this answer
    
+1. I believe "antidiagonal" is already standard terminology, though I've seen the more elaborate "northeast-southwest diagonal" being used. –  J. M. Nov 1 '10 at 23:53
    
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) :) –  Oposet Nov 2 '10 at 15:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.