Let $n \geq 2$ be an integer. Determine the smallest positive integer $m$ such that: given $n$ points in the plane, no three on a line, there are $m$ lines to be found, such that no line passes through any of the given points and such that for each pair of given points $X \neq Y$ there is a line such that $X$ and $Y$ lie on opposite sides of the line.
We prove that the smallest $m$ is equal to $\frac{n}{2}$ if $n$ is even and $\frac{n+1}{2}$ if $n$ is odd. Choose the $n$ points all on the same circle and call them $P_{1}, P_{2}, \ldots, P_{n}$ in the order in which they lie on the circle. The $n$ line segments $P_{1} P_{2}, P_{2} P_{3}, \ldots, P_{n} P_{1}$ must all be intersected by at least one line. Each line can intersect at most two such line segments, since each line intersects the circle at most twice. Therefore, the number of lines is at least $\frac{n}{2}$ and thus for odd $n$ at least $\frac{n+1}{2}$.
Now we prove that this is sufficient. First, we show that given four distinct points $P_{1}, P_{2}$ and $Q_{1}, Q_{2}$, there always exists a line such that $P_{1}$ and $P_{2}$ lie on opposite sides of the line and $Q_{1}$ and $Q_{2}$ also. For this, take the line through the midpoint of $P_{1} P_{2}$ and through the midpoint of $Q_{1} Q_{2}$. Suppose this line passes through $P_{1}$. Then it also passes through $P_{2}$, but not through $Q_{1}$ or $Q_{2}$, because no three points lie on a line. Shift it slightly so that it no longer passes through the midpoint of $Q_{1} Q_{2}$, but still through the midpoint of $P_{1} P_{2}$, then it no longer passes through any of these four points. Similarly, if the line passes through one of the other three points. If the now chosen line passes through one of the other given points in the plane, shift it (even) a little bit so that it no longer does. Since there are only finitely many points, this is always possible. This line now has $P_{1}$ and $P_{2}$ on opposite sides and $Q_{1}$ and $Q_{2}$ also.
Now assume that $n$ is even; if $n$ is odd, add an arbitrary point (not on a line with two of the other points). The lines we then construct also work if you remove the extra point. We now need to construct $\frac{n}{2}$ lines. Choose a random line in a direction such that no line through two of the given points is parallel to this line (this is possible because there are only finitely many points and thus also finitely many pairs, while there are infinitely many directions to choose from). Now shift the chosen line. In doing so, it encounters the given points one by one. There is thus a moment when there are no points on the line and there are exactly $\frac{n}{2}$ points on either side of the line. We fix this first line at that moment.
The plane is now divided into two regions, let's say the left and right regions. We will now add lines so that each line creates a new subregion in both the left and right regions. (We only count subregions in which at least one point lies.) For this, we always take two points in the left region that are not yet separated by a line and two points in the right region that are not yet separated by a line. We now choose a line such that the two points on the left lie on opposite sides of this line and the two points on the right also; we have shown earlier that this is possible. There is now at least one additional subregion on both the left and right sides, because the subregion with the two points in it is split into two. If at some point there are no two points left on one of the two sides that are not yet separated by a line, we only use points on the other side. Eventually, after adding $\frac{n}{2}-1$ lines, there are at least $\frac{n}{2}$ subregions with at least one point in each on both the left and right sides; there must therefore be exactly one point in each subregion. Each point thus lies in its own subregion, so the condition is satisfied. In total, we have used $\frac{n}{2}$ lines. So with $\frac{n}{2}$ lines, it is always possible to satisfy the condition.