Prove any even number of points has a cyclic ordering that allows one line to cross through evey segment between points.

31 Views Asked by At

Given $2n$ points in a plane ($n\in \Bbb N$) such that no three of the points are co-linear.

Prove that there is some ordering of labels on these points $P_1,P_2,P_3\ldots P_{2n}$ and some line $\ell$ such that for all $0 <i < 2n$, $\ell$ intersects line segment $\overline{P_iP_{i+1}}$ (in its interior, between $P_i$ and $P_{i+1}$) and $\ell$ also intersects line segment $\overline{P_{2n}P_{1}}$ in its interior.

For example, if the points are the four corners of a square, then taken in order around the sides of the square, you cannot find a line $\ell$ going through all four sides of the square. But you can rearrange the order to form a "figure 8" with two opposite sides of the square and two diagonals, and now it is easy to find an $\ell$ (going perpendicular to one of the side line segments) that crosses all four lines.

2

There are 2 best solutions below

0
On BEST ANSWER

Pick a line $\ell^\perp$ that is not perpendicular to any line determined by the two given points (only finitely many directions are prohibited). The points project onto $2n$ distinct points on $\ell^\perp$. Pick a point on $\ell^\perp$ in the "middle", i.e., with $n$ projected points each to its left and to its right. Let $\ell$ be perpendicular to $\ell^\perp$ at $A$, label the "left" points with odd indices, the "right" point with even indices. Each line segment then has a left and a right end point, hence must traverse $\ell$.

0
On

Just take a line such that $n$ of the points are on one side of the line and $n$ on the other, and relabel so the odd-numbered points are those on one side.