MathDB
Nonintersecting perfect matching with reasonable length

Source: Korean Summer Program Practice Test 2016 8

August 17, 2016
combinatorial geometry

Problem Statement

There are distinct points A1,A2,,A2nA_1, A_2, \dots, A_{2n} with no three collinear. Prove that one can relabel the points with the labels B1,,B2nB_1, \dots, B_{2n} so that for each 1i<jn1 \le i < j \le n the segments B2i1B2iB_{2i-1} B_{2i} and B2j1B2jB_{2j-1} B_{2j} do not intersect and the following inequality holds. B1B2+B3B4++B2n1B2n2π(A1A2+A3A4++A2n1A2n) B_1 B_2 + B_3 B_4 + \dots + B_{2n-1} B_{2n} \ge \frac{2}{\pi} (A_1 A_2 + A_3 A_4 + \dots + A_{2n-1} A_{2n})