Let $n \geq 2$ be an integer. Find the smallest positive integer $m$ for which the following holds: given $n$ points in the plane, no three on a line, there are $m$ lines such that no line passes through any of the given points, and for all points $X \neq Y$ there is a line with respect to which $X$ and $Y$ lie on opposite sides
Problem
Source: Netherlands TST for IMO 2017 day 3 problem 4
Tags: combinatorics, geometry
01.02.2018 18:18
I feel like there is too less information for some reason...
01.02.2018 20:45
Its pretty easy show that $ m \geq \left \lceil \frac{n}{2} \right \rceil $ But it seems not obvious how to prove that $ m = \frac{n}{2} $ ( probably its not even true ) Any ideas?
01.02.2018 21:06
The lower bound $m\ge\left\lceil\frac{n}{2}\right\rceil$ follows by putting all points on a circle. The upper bound $m\le\left\lceil\frac{n}{2}\right\rceil$ follows constructively. Assume without loss of generality that $n=2p$ is even and that exactly $p$ points lie above the $x$-axis and exactly $p$ points lie below the $x$-axis. We construct an arrangement of $p$ lines. Use the $x$-axis as your first line. The line generates two faces, both of which contain $p$ points. In the later steps, pick two points $A$ and $B$ above the $x$-axis that are not yet separated and two points $C$ and $D$ below the $x$-axis that are not yet separated. Pick a point $P_1$ on the segment $\overline{AB}$ and a point $P_2$ on the segment $\overline{CD}$, and introduce the line $\ell$ through $P_1$ and $P_2$; make sure that $\ell$ does not contain any of $A,B,C,D$; there is ample space for that. Now every new line subdivides one face with at least two points above the $x$-axis and one face with at least two points below the $x$-axis, and the resulting four smaller faces each contain at least one point. Since every new line increases the number of faces containing at least one point by at least $2$, the procedure terminates after $p-1$ steps.