Count number of triangles given a set of points

209 Views Asked by At

Gievn, $$A = \{(a,b)\ |\ a,b \in \mathbb Z\ \text{ and }\ |a|+|b|\ \le\ 2\}$$ Find
(a) Number of straight lines which pass through at least 2 points in $A$;
(b) Number of triangles whose vertices are points in $A$;


(a) I have exhaustively counted it's answer and it turns out to be 40. But it there any general approach to solve it?
(b) Same exhaustive approach: First choosing one point on a line then choosing other two points from remaining points. Second choosing 2 points on a line and one point that is not on the line. Sum these two cases for every line. Is there any general approach for this as well?

1

There are 1 best solutions below

0
On

Drawing a figure we see $10$ lines with $3$ points and $2$ lines with $5$ points. All other lines in the plane contain at most $2$ of the given $13$ points.

(a) "Formally" there are ${13\choose2}=78$ lines connecting two points in $A$. Lines containing $3$ points of $A$ are thereby counted ${3\choose2}=3$ times, and lines containing $5$ points of $A$ are counted ${5\choose2}=10$ times. It follows that the number of different lines is given by $$N_{\rm lines}=78-10(3-1)-2(10-1)=40\ .$$ (b) There are ${13\choose3}=286$ triples of points from $A$. Triples lying on a line do not give rise to a nondegenerate triangle. It follows that the number of nondegenerate triangles in this figure is given by $$N_{\rm triangles}=286-10{3\choose3}-2{5\choose3}=256\ .$$