MathDB
Problems
Contests
National and Regional Contests
Korea Contests
Korea Summer Program Practice Test
2016 Korea Summer Program Practice Test
8
8
Part of
2016 Korea Summer Program Practice Test
Problems
(1)
Nonintersecting perfect matching with reasonable length
Source: Korean Summer Program Practice Test 2016 8
8/17/2016
There are distinct points
A
1
,
A
2
,
…
,
A
2
n
A_1, A_2, \dots, A_{2n}
A
1
,
A
2
,
…
,
A
2
n
with no three collinear. Prove that one can relabel the points with the labels
B
1
,
…
,
B
2
n
B_1, \dots, B_{2n}
B
1
,
…
,
B
2
n
so that for each
1
≤
i
<
j
≤
n
1 \le i < j \le n
1
≤
i
<
j
≤
n
the segments
B
2
i
−
1
B
2
i
B_{2i-1} B_{2i}
B
2
i
−
1
B
2
i
and
B
2
j
−
1
B
2
j
B_{2j-1} B_{2j}
B
2
j
−
1
B
2
j
do not intersect and the following inequality holds.
B
1
B
2
+
B
3
B
4
+
⋯
+
B
2
n
−
1
B
2
n
≥
2
π
(
A
1
A
2
+
A
3
A
4
+
⋯
+
A
2
n
−
1
A
2
n
)
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})
B
1
B
2
+
B
3
B
4
+
⋯
+
B
2
n
−
1
B
2
n
≥
π
2
(
A
1
A
2
+
A
3
A
4
+
⋯
+
A
2
n
−
1
A
2
n
)
combinatorial geometry