12.20*. (SFRY, 75). On a plane, $n+4$ points are marked, four of which are located at the vertices of a square, and the remaining $n$ lie inside this square. Any of the marked points are allowed to be connected by segments, provided that no constructed segment contains marked points other than its endpoints, and no two of the constructed segments have common points other than, possibly, their endpoints. Find the maximum number of segments that can be constructed in this way.

## § 13. Geometric Inequalities

(see Appendix G: definitions $1,35,38$; theorems $1,6,64,69,70,74,75,77,80$ )
12.20. Suppose that for $n+4$ points, a certain network of segments has already been constructed, satisfying the condition of the problem, and no more segments can be drawn (such networks, called maximal in the future, necessarily exist, since the number of all possible segments is limited by the number $C_{n+4}^{2}$). A polygon, whose vertices are the given points, and each side is either a segment of the network or a union of several segments of the network lying on the same straight line, will be called a network polygon. The sides of the square $K$ with vertices at the 4 marked points, inside which the other $n$ points lie, always belong to the maximal network, so this square is a network polygon.

![](https://cdn.mathpix.com/cropped/2024_05_21_03a501298610b72904feg-227.jpg?height=646&width=426&top_left_y=653&top_left_x=47)

Fig. 74

We will prove that the maximal network divides the square $K$ into network triangles, each of which contains exactly three given points, namely its vertices. Consider an arbitrary point $O$ of the square. Among all network polygons containing this point (the set of such polygons is not empty, as it contains the square $K$), choose an $m$-sided polygon $M$ of the smallest area. Since the sum of the angles of the polygon $M$ is $180^{\circ}(m-2)$, there will be a vertex $A$ among its vertices such that the angle at this vertex is less than $180^{\circ}$. On each of the two sides of this angle, choose the nearest given point to the vertex $A$, thus obtaining points $B$ and $C$ (Fig. 74). Note that the triangle $A B C$ contains given points different from $A$ and $B$, for example, point $C$. Take one of them — point $D$, for which the angle $A B D$ is minimal (if there are several such points, then choose the one closest to point $B$). Then in the triangle $A B D$ there are no given points different from the vertices $A, B, D$, which means that no segment of the network has common points with the sides $A D$ and $B D$ other than, possibly, these vertices. Due to the maximality of the network, the segments $A D$ and $B D$ belong to it. Thus, the triangle $A B D$ is a network triangle. If it does not coincide with the polygon $M$, then the latter is divided into two parts, each of which is also a network polygon, which contradicts the choice of the polygon $M$. Therefore, the triangle $A B D$ is the polygon $M$. Thus, the point $O$ lies in the network triangle $A B D$, which does not contain given points different from its vertices. Now let's count the number $k$ of segments in the maximal network. To do this, find the sum of all angles of all triangles into which the square $K$ is divided by this network. On the one hand, it is equal to $180^{\circ} \cdot l$, where $l$ is the number of triangles. On the other hand, it is composed of the sum of the angles at the vertices of the square and all full angles with vertices at the given points inside the square, i.e., it is equal to $360^{\circ}(n+1)$. Therefore, we have

$$
180^{\circ} \cdot l = 360^{\circ} \cdot (n+1)
$$

from which $l = 2(n+1)$. Finally, each side of the square $K$ is one side of one triangle, and each segment of the network, different from the sides of this square, is a common side of two triangles. Consequently, we get the equation $4 + 2(k-4) = 3l$, from which

$$
k = \frac{3}{2} l + 2 = 3n + 5
$$

## § 13. Geometric Inequalities