Yesterday’s post on taxation generated a whole lot of comments that deserve responses; unfortunately I’m too swamped right now to respond. Worse yet, I’ll be out of town — and probably not blogging — for the next few days. Sometime next week, I’ll try to craft a new blogpost addressing much of what was said in those comments.
Meanwhile, here, courtesy of our frequent and invariably interesting commenter Mike H, is a puzzle to keep you busy while I’m gone:
Your enemy places, say, 8 red points and 8 blue points in the plane. Your job is to connect each red point to some blue point with a straight line segment, so that none of the line segments cross.
1) Can your enemy place the points in such a way that you are guaranteed to fail?
2) What if we make your job harder by requiring each blue point to be used exactly once?
3) What if we change 8 to 17 or 26 or 43 or …. ?
Edited to add: Question 2) is the interesting one. Also, to keep it interesting, your enemy is not allowed to put any three points on the same line.
Easily. Place all 16 in a single line–with 8 at one end being all one color.
Ok, make it harder – your enemy is not allowed to put even three points in a straight line, let alone 16.
POSSIBLE SOLUTION SPOILER
The first variant (where each red point can be connected to *any* blue point) seems pretty trivial — just pick one arbitrary blue point, and draw lines from each red point, to that blue point. If no three points are colinear, then the lines don’t intersect. (Since any pair of straight line segments must meet at the blue point, they can’t intersect anywhere else.) Am I missing something?
@Bennett : You’re missing nothing. The second variant, where each red point must join exactly one blue point, is the real puzzle.
POSSIBLE COMPLETE SOLUTION SPOILER
I think it can be done for any number of pairs of red and blue points.
Prove by induction on n, the number of pairs. Trivial for n=1.
Now for larger n, take a rubber band and loop it taut around all the points in the plane. The “outermost” points form a convex polygon containing the inner ones. If any two of those “outermost” points are of different colors, then join those with a line segment, which since it lies on the outermost polygon, can’t interfere with any segments drawn between other points. So by the induction hypothesis the remaining points can be joined as well.
On the other hand, suppose all the outermost points are the same color, say red. So now take a line drawn at a given gradient, and “slide” it across the entire set of points, keep the gradient constant. (Choose the gradient so that it’s not parallel to any line segment joining any two points — so that the moving line only ever crosses one point at a time.) As you slide the line, keep track of the number of red points that have been crossed, and the number of blue points that have been crossed.
Since all the “outermost” points are red, the first point you cross must be red, and the last point you cross must be red. So there must be a moment somewhere in between, where the line has crossed the same number of red and blue points. Freeze the line at that point, and divide your set into red/blue pairs on one side of the line, and red/blue pairs on the other side. By the induction hypothesis, the sets on either side of the line can be paired off without crossing.
(If this is correct, there’s probably a shorter proof involving a simpler way of reducing your set to a smaller set where the induction hypothesis holds.)
Yes. Here is a way to construct the pairing:
1) pick a random blue point; let’s have a line that intersects this point and divides the plane to 2 subplanes; rotate the line, until number of red points equals number of blue points on each subplane; connect the blue point with the red one the line intersects
2) repeat for every sublplane
ad 1) does such a line exist? Yes: pick a random angle of the line. The number of red points above the line is R, number of blue points is B. Suppose R > B. Rotate the line 180 degress. Now R < B. When you rotate the line, the R and B change in +/-1 steps. Therefore, there must exist a situation when R=B.
SPOILER ALERT
For n blue and n red points.
Match each red point with a unique blue point. Draw a line segement between these 2 points. If you have no line segments crossing you are done. Ifsome line segements cross pick any pair of crossing line segements. Uncross them by changing the pairs. i.e. if the line segements connects R1 and B1 and R2 to B2 pair R1 with B2 and R2 with B1. Repeat this procedure.
Of course it’s not obvious that this process will terminate as sometimes this uncrossing will lead to new crossings. The rick is to notice that the total length of all line segements decreases at each uncrossing step. So this process must terminate.
@Jonathan Kariv: Very nice, the shortened length bit.
I got that wrong…so once again and better:
– Pick a point on a convex hull (let’s say it’s Blue). Draw a line through this point in such a way, that all remaining points are on one subplane and zero points are on the other. Slowly rotate the plane; when the line intersects a red point, count blue and red points on the subplanes; when you have Red=Blue on each subplane, draw a line; repeat for each subplane.
– Does such a point always exist? Assign -1 to Blue and +1 to Red. All the points except the selected Blue sum up to +1. As you rotate the plane, you are slowly adding points to the empty subplane. When the added points add to 1 and last added point is ‘+1(Red)’, you’ve got it. There will be at least one such point; as you get from 0(empty plane) to +1(all points added), you will eventually go through ‘0 + (+1) = 1’ step.
Andy, thanks, much more elegant than mine :) The following is basically your idea, but simpler: Pick a point in the plane that is not one of your red/blue points, and is not colinear with any pair of those points, but is inside the convex polygon containing all those points. Then draw your line and rotate 180 degrees. If R>B at the beginning, then R<B at the end, therefore R=B at some point in between, and the sets on either side of the line are nonempty — so just use the induction hypothesis to pair of all the points in those sets.