Maths Olympiad Prep

Library / /305 of 520

Combinatorics Difficulty 5.4 AIME, harder Find the answer

Example 4 Given ten points in space, where no four points lie on the same plane. Connect some of the points with line segments. If the resulting figure contains no triangles and no spatial quadrilaterals, determine the maximum number of line segments that can be drawn.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let the ten points be A1,A2,,A10A_{1}, A_{2}, \cdots, A_{10}. Using these ten points as vertices and the line segments connecting them as edges, we obtain a simple graph GG of order 10. Let the degree of point Ai(i=1,2,,10)A_{i} (i=1,2, \cdots, 10) be did_{i}. Then the total number of edges in graph GG is 12i=110di\frac{1}{2} \sum_{i=1}^{10} d_{i}.

In graph GG, we call the figure formed by two line segments sharing a common endpoint an angle. Thus, there are i=110Cdi2\sum_{i=1}^{10} \mathrm{C}_{d_{i}}^{2} different angles.

By the given condition, for any angle AiAjAk\angle A_{i} A_{j} A_{k} in graph GG, AiA_{i} and AkA_{k} are not adjacent. For any two angles Ai1Aj1Ak1\angle A_{i_{1}} A_{j_{1}} A_{k_{1}} and Ai2Aj2Ak2\angle A_{i_{2}} A_{j_{2}} A_{k_{2}}, we have
{Ai1,Ak1}{Ai2,Ak2}\left\{A_{i_{1}}, A_{k_{1}}\right\} \neq\left\{A_{i_{2}}, A_{k_{2}}\right\}.
Thus, the complement graph of GG has at least i=110Cdi2\sum_{i=1}^{10} \mathrm{C}_{d_{i}}^{2} edges.
Therefore, the total number of edges SS satisfies
i=110Cdi2=SC10212i=110di \sum_{i=1}^{10} \mathrm{C}_{d_{i}}^{2}=S \leqslant \mathrm{C}_{10}^{2}-\frac{1}{2} \sum_{i=1}^{10} d_{i} \text {, }

which implies C102i=110Cdi2+12i=110di=12i=110di2\mathrm{C}_{10}^{2} \geqslant \sum_{i=1}^{10} \mathrm{C}_{d_{i}}^{2}+\frac{1}{2} \sum_{i=1}^{10} d_{i}=\frac{1}{2} \sum_{i=1}^{10} d_{i}^{2}.
Also, 12i=110di212×110(i=110di)2\frac{1}{2} \sum_{i=1}^{10} d_{i}^{2} \geqslant \frac{1}{2} \times \frac{1}{10}\left(\sum_{i=1}^{10} d_{i}\right)^{2}, so
C10212×110(i=110di)212i=110di15 \mathrm{C}_{10}^{2} \geqslant \frac{1}{2} \times \frac{1}{10}\left(\sum_{i=1}^{10} d_{i}\right)^{2} \Rightarrow \frac{1}{2} \sum_{i=1}^{10} d_{i} \leqslant 15 \text {. }

A specific construction is shown in Figure 1.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.