There are eight points, connection between each other. See figure [1]
In addition to the red dot, any three line segments do not intersect at one point.
- How many triangles are there in the picture?
- If you remove three segments, maximum number of triangles left?
Thanks a lot!
Best Answer
Summary
For the first part of question, the answer is $$\binom{8}{3} + 4\binom{8}{4} + 5\binom{8}{5} + \binom{8}{6} = 644$$ The number pointed out by bof in one of hir comments.
For the second part, if we interpret the term "segment" as one of the $\binom{8}{2} = 28$ edges among the $8$ vertices, the answer will be $583$. This is achieved by removing 3 consecutive edges from the perimeter of the circle. For example, removing edges $12$, $23$ and $34$ will left us with $583$ triangles.
Part I - number of triangles.
Let us switch to how to derive the answer for the first part of question analytically.
Instead of $8$, consider the generalization of placing $n$ red dots on a circle, form a complete graph from them and then count the number of triangles formed by these lines. We further assume the red dots are in general position so that no three lines intersect at the same point (except at the red dots). As we can see below, this assumption is crucial.
WOLOG, we will label the $n$ red dots by $1, \ldots, n$ and they are placed on the circle in counterclockwise manner.
A triangle consists of 3 sides and each side is lying on a line formed by two red dots. Since it is possible some lines are sharing red dots, a triangle may involve $m$ red dots where $3 \le m \le 6$.
$\hspace0.5in$
Case 1. $m = 3$
There are $\binom{n}{3}$ ways to pick $3$ red dots $\{ a, b, c \}$ out of $n$ red dots. WOLOG, we can assume $1 \le a < b < c \le n $. Given $a, b, c$, it is clear every red dot is shared by $2$ lines and there is only one way to form a triangle with the three lines $\{ ab, bc, ac \}$ (fig $1a$).
This means there area $\binom{n}{3}$ triangles for $m = 3$.
Case 2. $m = 4$,
There are $\binom{n}{4}$ ways to pick $4$ red dots $\{ a, b, c, d \}$ out of $n$ red dots. WOLOG, we can assume $1 \le a < b < c < d \le n$. Given $a, b, c, d$, there are two possibilities, either one of them connects to all three lines (fig $2a$), this leads us nowhere or two of the red dots are shared by two lines. Consider the case $a$ is one of these two red dots and let's enumerate the possibilities:
$c$ is the other red dot, there are two possible line arrangements $\{ ac, cd, ab \}$ or $\{ ac, bc, ad \}$ (fig. $2b)$. However neither of them forms a triangle inside the circle.
$b$ is the other red dot, there are two possible line arrangements again $\{ ab, bc, ad \}$ (fig $2c$) and $\{ ab, bd, ac \}$ (fig $2d$). Only the second configuration forms a triangle inside the circle.
$d$ is the other red dot, this is similar to the above sub case with $d, a, b, c$ taking the roles of $a, b, c, d$. Among the two possible ine arrangements , only one of them forms a triangle inside the circle. If you loop over other possibilities of the two red dots which share lines. We find there are totally $4$ configuration for each choice of $(a, b, c, d)$.
This means there are $4 \binom{n}{4}$ triangles for the $m = 3$ case.
Case 3. $m = 5$
There are $\binom{n}{5}$ ways to pick $5$ red dots $\{ a, b, c, d, e \}$ out of $n$ red dots. WOLOG, we can assume $1 \le a < b < c < d < e\le n$. Given $a, b, c, d, e $, it is clear one any only one of the red dots are shared by two lines. Consider the case $a$ is that distinguished red dots. There are six possible line arrangements $$ \{ ab, ac, de \} (\text{fig } 3a),\quad \{ ab, ad, ce \} (\text{fig } 3b),\quad \{ ab, ae, cd \} (\text{fig } 3c),\\ \{ ac, ad, be \} (\text{fig } 3d),\quad \{ ac, ae, bd \} (\text{fig } 3e),\quad \{ ad, ae, bc \} (\text{fig } 3f) $$ and only of them $\{ ac, ad, be \}$ forms a triangle inside the circle.
Since there are 5 possible ways to pick the distinguished red dots, there are $5\binom{n}{5}$ ways for the $m = 5$ case.
Case 4. $m = 6$
There are $\binom{n}{6}$ ways to pick $6$ red dots $\{ a, b, c, d, e, f \}$ out of $n$ red dots. WOLOG, we can assume $1 \le a < b < c < d < e < f\le n$. Given $a, b, c, d, e, f$, there are $15$ ways of grouping them into pairs and form $3$ lines. It is easy to see any line arrangement that contains neighboring pair $ab, bc, cd, de, ef, af$ does not form a triangle inside a circle (e.g. fig $4a$). This eliminate $11$ of them and we are left with $4$ line arrangements. $$\{ ac, be, df \},\quad \{ ad, be, cf \},\quad \{ ad, bf, ce \},\quad \{ ae, bd, cf \}$$ If you draw these $4$ arrangements on a piece of paper, you will notice the $1^{st}$, $3^{rd}$ and $4^{th}$ arrangement all looks like fig $4b$. They also won't produce any triangle inside the circle. This leaves us with the $2^{nd}$ line arrangement $\{ ad, be, cf \}$. There are two possibilities. The 3 lines either form a triangle inside the circle (e.g. fig $4c$) or intersect at a single point. Since we have assumed the last case will not happen. This means for each choice of $\{ a, b, c, d, e, f \}$, there is one and only one way to join them to get a triangle.
As a consequence, there are $\binom{n}{6}$ ways for the $m = 6$ case.
Combine these four cases, we can conclude the number of triangle for general $N$ is given by
$$\binom{n}{3} + 4\binom{n}{4} + 5\binom{n}{5} + \binom{n}{6}$$
Part II - maximum number of triangles remain after one remove 3 segments.
This is done by brute force. I write a program to locate all $644$ triangles and proceed to check the effect on removing any one of the $28$ edges. Let $N_{ab}$ be the number of triangles destroyed when we remove the edge $ab$, we have
$$\begin{array}{r:l} N_{ab} & ab\\ \hline 21 & 12, 23, 34, 45, 56, 67, 78, 18\\ 66 & 13, 24, 35, 46, 57, 68, 17, 28\\ 99 & 14, 25, 36, 47, 58, 16, 27, 38\\ 111 & 15, 26, 37, 48 \end{array}$$
Since $3 \times 21 < \min(66,99,111)$, the configuration which maximize the number of triangles remain is formed by removing three consecutive edges on the perimeter of the circle (i.e those from the first row of above table).
Using rotational symmetry, we can assume $18$ is one of the three edges to go. We only need to go through $\binom{7}{2} = 21$ pairs of edges from the set $\{ 12, 23, 34, 45, 56, 67, 78 \}$ to identify the optimal configurations.