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