Let $ A$ be a set of $ 2n$ points on the plane such that no three points are collinear. Prove that for any distinct two points $ a,b\in A$ there exists a line that partitions $ A$ into two subsets each containing $ n$ points and such that $ a,b$ lie on different sides of the line.
Problem
Source: IZO 1 Junior Problem 3
Tags: rotation, combinatorics proposed, combinatorics
JBL
18.12.2008 05:49
Pick a point on segment $ ab$ that is not on the line joining any two of the other points. Now choose a line through this point and rotate it slowly, keeping track of the number of points to its "left." If this value is initially $ k$, after rotating 180 degrees it becomes $ 2n - k$. Since this value changes by at most 1 at a time, at some intermediate stage it must be equal to exactly $ n$. Also, any such line separates $ a$ from $ b$.
jgnr
25.12.2008 11:45
Lemma. Given points A, B, C, D, no three are collinear. If there exist a line between A and B such that C and D are on the same side, there is a line such that C and D are on the different side.
Proof: Consider the triangle ACD. Firstly, the line intersects side AC. We move the line such that it intersects CD, but does not go too far s.t. A and B are on the same side. Since A, C, D are not collinear, this can always be done.
Now, assume we have an arbitrary line between A and B, there is $ n+k$ points on the right side and $ n-k$ points on the left side, where $ k\in\mathbb{N}$. By our lemma, we can move the line such that the number of points on the left increases to $ n-k+1$, while the number of points on the right reduces to $ n+k-1$. If we repeat this process, we will have $ n$ points on each side.
UzbekMathematician
17.12.2017 14:43
JBL wrote: Pick a point on segment $ ab$ that is not on the line joining any two of the other points. Now choose a line through this point and rotate it slowly, keeping track of the number of points to its "left." If this value is initially $ k$, after rotating 180 degrees it becomes $ 2n - k$. Since this value changes by at most 1 at a time, at some intermediate stage it must be equal to exactly $ n$. Also, any such line separates $ a$ from $ b$. nice solution to a beautiful problem