Problem 1177

Connect the points with a closed broken line in some order, and then, if there are self-intersections, replace the pair of intersecting segments with a pair of non-intersecting segments.

## Solution

Let the points be denoted as $\mathrm{A}_{1}, \mathrm{~A}_{2}, \ldots, \mathrm{A}_{n}$ in some arbitrary order. If the closed broken line $\mathrm{A}_{1} \mathrm{~A}_{2} \ldots \mathrm{A}_{\mathrm{n}}$ has no self-intersections, then the condition of the problem is satisfied. Suppose there are two intersecting segments, for definiteness, let these be the segments $A_{1} A_{2}$ and $A_{k} A_{k+1}$. Replace this pair of segments with the segments $A_{1} A_{k}$ and $A_{2} A_{k+1}$. Thus, we obtain a new closed broken line $\mathrm{A}_{1} \mathrm{~A}_{k} \mathrm{~A}_{k-1} \ldots \mathrm{A}_{2} \mathrm{~A}_{k+1} \mathrm{~A}_{\mathrm{k}+2} \ldots \mathrm{A}_{n}$, connecting the given $n$ points in a different order. Since the segments $\mathrm{A}_{1} \mathrm{~A}_{2}$ and $\mathrm{A}_{\mathrm{k}} \mathrm{A}_{\mathrm{k}+1}$ intersect, the points $\mathrm{A}_{1}, \mathrm{~A}_{\mathrm{k}}, \mathrm{A}_{2}, \mathrm{~A}_{\mathrm{k}+1}$ form a convex quadrilateral. In a convex quadrilateral, the sum of the lengths of the diagonals is greater than the sum of the lengths of a pair of opposite sides, so $A_{1} A_{2} + A_{k} A_{k+1} > A_{1} A_{k} + A_{2} A_{k+1}$. This means that the perimeter of the closed broken line decreases when the described replacement of segments is performed. We perform similar segment replacements in the broken line until it is no longer possible, during which the perimeter of the broken line decreases. This process cannot continue indefinitely, as the number of ways to order $n$ points is finite. In the end, we will
arrive at a closed broken line without self-intersections (otherwise, we could make another segment replacement and further reduce the perimeter of the broken line).