Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
For reference, this is the discrete ham-sandwich theorem. –  Mitch Jul 15 '11 at 19:33

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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. :) –  Beni Bogosel Jul 15 '11 at 19:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.