[Math] How many maximum triangles can be made

combinatoricscontest-mathdiscrete mathematicsgraph theoryproof-verification

There are $8$ points on a plane no three are colinear how many maximum triangles can be made s.t no two triangles have more than one point in common.

Now I can choose $3$ points from $8$ points in $^8C_3$ ways and two triangles can have two points in common if I choose $5$ points make $2$ triangles out of it and that can be made in $^8C_6 \times ^6C_3 \times \frac 12$ ways. So the answer should be $^8C_3-(^8C_5 \times ^5C_3\times \frac 12)$.

Am I double counting anything?

After seeing one comment and thinking a bit I feel that method of complementation will be harder here and I am thinking about how many ways to draw a triangle instead of maximum how many triangles,

So another approach: I can choose three points from $8$ points and draw the 1st triangle then the second triangle can be drawn taking one point from the first(because we are maximizing) and $2$ others from the remaining $5$ points. So we have used $5$ points and drew $2$ triangles. Then we can draw atmost one more triangle. So $3$ is the answer.

Best Answer

I have only a partial answer to your question: the maximum number of triangles is either $8$ or $9$.

You can't have more than $9$ triangles, because there are only $^8C_2=28$ edges determined by the $8$ points, each triangle needs $3$ edges, and no edge may be used by more than one triangle. So the number of triangles is at most $\lfloor28/3\rfloor=9$.

I don't see how to construct a set of $9$ triangles satisfying your conditions, but I can get $8$. Namely, if we label the points $A,B,C,D,E,F,G,H$, the following $8$ triangles work: $$ABC,\ ADG,\ AFH,\ BEH,\ BFG,\ CDH,\ CEG,\ DEH$$

P.S. In fact, $8$ is the maximum. Let $p$ be the number of points (so $p=8$), let $t$ be the number of triangles, and let $n$ be the number of pairs $(P,T)$ where $T$ is a triangle and $P$ is a vertex of $T$. Then $n=3t$ (since each triangle has $3$ vertices), and $n\le3p$ (since at most $3$ triangles can contain a given point), so $t\le p=8$.

P.P.S. In case you're wondering how I found that set of $8$ triangles, I started with the well-known example of $12$ triangles on $9$ points (Steiner triple system) and deleted one point. Namely, I wrote the letters A to I in a $3\times3$ square array, took the $6$ rows and columns and the $6$ "diagonals", and then deleted the ones containing the letter I.