16. In space, given 9 points, where no 4 points are coplanar, connect several line segments between the 9 points so that there is no tetrahedron in the graph. How many triangles can there be at most in the graph?
(1994 China National Team Test Question)
16. Divide 9 points into 3 groups $\left\{A_{1}, A_{2}, A_{3}\right\},\left\{A_{4}, A_{5}, A_{6}\right\},\left\{A_{7}, A_{8}, A_{9}\right\}$, and connect every two points from different groups. Then these lines do not form a tetrahedron but do form 27 triangles, showing that the maximum number of triangles is at least 27. The following proof shows that if the graph has 28 triangles, then there must be a tetrahedron. To do this, we first prove the following lemma: Given $n$ points in space, where no 4 points are coplanar, if several line segments are connected and the graph contains no triangles, then the maximum number of line segments is $\left[\frac{n^{2}}{4}\right]$. In fact, suppose that from $A_{1}$, $k$ line segments are drawn, which are $A_{1} B_{1}, A_{1} B_{2}, \cdots, A_{1} B_{k}$. Since there are no triangles, no two points among $B_{1}, B_{2}, \cdots, B_{k}$ are connected. The remaining $n-k-1$ points are $A_{2}, A_{3}, \cdots, A_{n-k}$. Therefore, from $B_{i}$, the number of line segments is at most $n-k$ $(i=1,2, \cdots, k)$, and from $A_{j}$, the number of line segments is at most $k$ $(j=1,2, \cdots, n-k)$. Hence, the number of line segments $t$ in the graph does not exceed $\frac{1}{2}[k \cdot (n-k)+(n-k) k]=(n-k) k=\frac{n^{2}}{4}-\left(\frac{n}{2}-k\right)^{2} \leqslant \frac{n^{2}}{4}$. Since $t$ is an integer, $t \leqslant\left[\frac{n^{2}}{4}\right]$, and thus the lemma is proved. Returning to the proof of the original problem, if there is no tetrahedron, let $A_{1}$ be the point with the most line segments drawn from it. Since 28 triangles have 84 vertices, by the pigeonhole principle, there must be a point $A_{2}$ that is a common vertex of at least $\left[\frac{84-1}{9}\right]+1=10$ triangles. If $A_{2}$ draws at most 6 line segments, then the other ends of these lines (at most 6 endpoints) must have at least 10 line segments, and by the lemma, these 10 line segments must form a triangle, which, together with $A_{2}$, forms a tetrahedron, a contradiction. Therefore, point $A_{2}$ must draw at least 7 line segments, and point $A_{1}$ must draw even more. (1) If point $A_{1}$ draws 8 line segments, since there is no tetrahedron, the graph formed by the remaining 8 points cannot have a triangle. Thus, by the lemma, the number of line segments among these 8 points does not exceed $\left[\frac{8^{2}}{4}\right]=16$, so the graph can have at most 16 triangles, a contradiction. (2) If point $A_{1}$ draws 7 line segments, then the subgraph formed by the other 7 endpoints cannot have a triangle. Thus, by the lemma, the number of line segments in this subgraph does not exceed $\left[\frac{7^{2}}{4}\right]=12$, so the number of triangles containing vertex $A_{1}$ is at most 12. Let the only point among the 9 points that is not connected to $A_{1}$ be $B$. Then, similarly, the number of triangles containing vertex $B$ is at most 12, so the graph can have at most 24 triangles, a contradiction. In summary, the graph can have at most 27 triangles.