$6$ given points on a circle are joined by line segments of which no three are concurrent. Find number of triangles formed inside the circle.

algebra-precalculuscombinationscombinatoricspermutations

There are $6$ given points on a circle and each of the two points are connected by a line segment. Suppose that any three segments are not concurrent so that any three intersecting segments form a triangle inside the circle. Find the number of triangles formed inside the circle.

My Attempt

$\binom{6}{4}=15$ are the number of points of intersection inside the circle.

So the number of triangles formed inside the circle is the number of ways to choose three points out of $21$ points ($15$(inside the triangle) + the number of points on the circle($6$)).

The number of triangles=$\binom{15}{3}+\binom{15}{2}\times \binom{6}{1}+\binom{15}{1}\times \binom{6}{2}+\binom{6}{3}=\binom{21}{3}=1330$

But I can see that there are many instances of counting of triangles which do not exist. For e.g. a chord has a point of intersection on it. $\binom{21}{3}$ also counts the triangle formed by end-points of this chord and this point of intersection.

How should I avoid these cases.

Instead of choosing points if try to choose intersecting line segments how should I go about it.

The answer given is $111$.

Best Answer

let $N_3$ be the number of triangles that can be formed for which all 3 vertices are on the circle $$N_3 = \binom 63 = 20$$ let $N_2$ be the number of triangles that can be formed for which 2 out of 3 vertices are on the circle.

  • all 15 interior points are each connected to 4 points on the circle, being part of $\binom 42 -2=4$ triangles $$N_2 = 15 \left (\binom 42 -2 \right )=60$$

let $N_1$ be the number of triangles that can be formed for which 1 out of 3 vertices are on the circle.

  • all 6 points on the circle each have 3 interior lines emanating from them
  • let the six points on the circle be $P_1 ... P_6$, numbered consecutively
  • consider the point $P_1$...
    • the 3 internal lines will cross the line $P_2 \to P_6$ in 3 places, creating 3 triangles
    • the 3 internal lines will cross the line$P_3 \to P_6$ in 2 places, creating 1 triangle
    • the 3 internal lines will cross the line $P_2 \to P_5$ in 2 places, creating 1 triangle
    • the 3 internal lines will not cross any other lines more than once so no other triangles involving $P_1$ and 2 internal points can be formed.
  • all 6 points will contribute the same number of triangles to $N_1$ as does $P_1$ $$N_1 = 6(3+1+1) = 30$$

let $N_0$ be the number of triangles for which all 3 vertices are internal points. There is only 1 of these, formed by the lines $(P_1 \to P_4) (P_2 \to P_5) (P_3 \to P_6)$

$$N_{TOT} = N_3 + N_2 + N_1 + N_0 = 20+60+30+1=111$$

Related Question