4
$\begingroup$

I am working through an interesting combinatorial geometry problem book (in my free time, now that it is the summer holiday), and found the following problem which seems easy, but the I can't see the proof of it. It says like this:

Consider $A,B$ two sets of points in plane, with $|A|=2n,|B|=2m,\ m,n \geq 1$ ($|X|$ is the cardinal of the set $X$), such that no three points from $A\cup B$ are collinear. Prove that there is a line which splits the plane in half such that each half contains $n$ points from $A$ and $m$ points from $B$.

When there is only one set, the problem is quite simple. I choose a line which is not parallel with neither of the line formed by the points, put it such that all points are on one side of it and "slide" it across the plane knowing, that only one point at a time can be on the given line, until half of the points are on either side.

This argument doesn't seem to work in this case. Thank you for your help.

  • 1
    For reference, this is the discrete ham-sandwich theorem.2011-07-15

1 Answers 1

4

The Wikipedia article on the ham sandwich theorem contains a general proof, but there's a simpler argument in this special case.

Start out as you did to bisect set $A$, and then start turning the line you found. If you hit a point of $A$, pivot the line around it until you hit another point of $A$. Then cross both points simultaneously so that $A$ remains bisected. (You can do this since there are no other points of $A$ or $B$ on the line between those two points.) Continue turning the line in this way until you've turned it by $\pi$, and move it so that it coincides with the original, unturned line. You've continuously moved the line while swapping the two halves. $A$ has remained bisected all along, but the two halves of $B$ have changed sides. Thus at some point you must have gone through a state where both $A$ and $B$ were bisected.

  • 0
    Very nice argument. I was thinking of something like that, but didn't have the idea to skip two points in $A$ at once. Thank you. :)2011-07-15