Some of the vertices of a convex $n$-gon are connected by segments, such that any two of them have no common interior point. Prove that, for any $n$ points in general position, there exists a one-to-one correspondence between the points and the vertices of the $n$ gon, such that any two segments between the points, corresponding to the respective segments from the $n$ gon, have no common interior point.
Problem
Source: Bulgaria TST 2003 P3
Tags: induction, combinatorial geometry, combinatorics proposed, combinatorics
jaydoubleuel
03.02.2015 21:54
I will just write down a sketch. It is enough to prove that when the convex n-gon is triangulated. We prove a stronger statement. Given a side $ab$ of the convex n-gon, and two points $p,q$ such that $pq$ is a side of the convex hull of given n points, we can find a bijection satisfying the problem and sending $a$ to $p$, $b$ to $q$. We induct on $n$. The base case is trivial, and assume the induction hypothesis. Since the convex n-gon is triangulated, let the triangle be $abc$. Then the triangle divides the convex $n$-gon into two parts each having sides $ac,bc$, respectively. Now we try to divide the set of $n$ points. If the convex hull of $n$ points is $...rpqs...$, then the convex hull of $n-2$ points excluding $p,q$ is something like $rp_1p_2...p_ls$. Choose an appropriate $p_i$ for the point that will correspond with $c$. The case where you need to be careful is when one of the two convex $n$-gons made previously is small. Now apply the induction hypothesis.
Pathological
16.11.2019 03:58
Pick some arbitrary point $O$ in the plane which is not collinear with any two points out of the $n$. Label the points $P_1, P_2, P_3, \cdots, P_n$ in clockwise order w.r.t. $O$, where we pick $P_1$ arbitrarily and simply go clockwise from there. Now, label the convex $n-$gon $A_1 A_2 \cdots A_n$. The one-to-one correspondence which takes $P_i$ to $A_i$ for each $1 \le i \le n$ works. $\square$
dgrozev
17.11.2019 15:03
@Pathological: Unfortunately, it cannot be made in that trivial way! See the attached picture.
Attachments:
dgrozev
17.11.2019 15:08
The official solution is attached below. There are many other variants. That trick, taking $A_1,A_2$ and then the unique point $A_i$ that's connected with both of them, only serves to apply the induction for only two components. Otherwise one may just take some $A_i$ that has segment (segments) incident to it and let they be $A_iA_{i_1},\dots,A_i A_{i_k}$. Then we take some $B_i$ on the convex hull of the points $B$'s and clockwise choose $B_{i_j},j=1,2,\dots,k$ such that between $B_i B_{i_j}$ and $B_i B_{i_{j+1}}$ lie the same number of points as between $A_i A_{i_j}$ and $A_i A_{i_{j+1}}$. And then we apply the induction.
Attachments:
