IMO long list spatial Combinatorial problem

Question

Can anyone send a solution or hint to these problem? I tried a greedy algorithm but couldn’t make it work

Answer 1

Of the finitely many possible pairings, choose one for which the sum of the lengths of the line segments is least.

Claim:$\;$For such a pairing, no two line segments intersect.

Suppose for such a pairing the line segments $AC$ and $BD$ intersect at $P$.

Then $ABCD$ is a convex quadrilateral with diagonals intersecting at $P$.

But then if we replace the pairs $A,C$ and $B,D$ by $A,B$ and $C,D$ we would have $$ \left\lbrace \begin{align*} |AB| &< |AP|+|PB|\\[4pt] |CD| &< |CP|+|PD|\\[4pt] \end{align*} \qquad\qquad\;\;\;\;\; \right. $$ hence \begin{align*} |AB| + |CD| &< (|AP|+|PB|)+(|CP|+|PD|)\\[4pt] &= (|AP|+|CP|)+(|PB|+|PD|)\\[4pt] &= (|AP|+|PC|)+(|BP|+|PD|)\\[4pt] &= |AC|+|BD|\\[4pt] \end{align*} so the new pairing would have a smaller sum of segment lengths, contradiction.

Answer 2

Form the convex hull of the $2n$ points, and let $x$ and $y$ be adjacent extreme points. Then you can join $x$ with $y$, and pair up the remaining $2n-2$ points by induction.