Solving Sample 2 of Points in a Plane Homework

[ehrenfest]

Homework Statement

http://math.stanford.edu/~vakil/putnam07/07putnam5.pdf

I am having trouble with Sample 2.

I am trying a proof by induction (the case n = 1,2 are easy). So if it is true for n=k and you have k+1 of each colors, you can take out any red-blue pair and get the desired line segments for the remaining ones.

So somehow I need to show that we can find a pair to take out that will not intersect the line segments drawn between any of the other ones.

So, can we just take the red point with the largest y coordinate and the blue point with the largest y coordinates?

Hmmm...that seems like it would work.

EDIT: on second thought, I do not think that will work because you could have something like this

red
red
blue
blue

EDIT 2: It isn't showing the spaces. Does anyone know why?

Homework Equations

The Attempt at a Solution

 

[EnumaElish]

What is the definition of non-intersecting?

What if red --- red --- blue --- blue? Then one intersects the other at half of all points (at least).

 

[ehrenfest]

Each of the line segments has one red endpoint and one blue endpoint. So your diagram is wrong.

 

[e(ho0n3]

Suppose all the points lie on the x-axis: the red points are located on the right side of the origin and the blue points on the left. How do you go about drawing line segments between the red points and the blue points without having them intersect?

 

[ehrenfest]

Connect all of the adjacent red and blue points. Then pretend all the red and blue points you just connected are not there, and again connect the adjacent red and blue points. This is always possible because the arc you use to connect adjacent red and blue points does not "block" any unconnected points.

So, if all of the points are not on the x-axis, you would want to connect the points in such a way that the sum of the lengths of the n line segments is minimized. No two line segments could intersect or else you could use the triangle inequality to show that switching the blue or red endpoints of those line segments would get you two shorter line segments.

Right?

 

[e(ho0n3]

Connect all of the adjacent red and blue points. Then pretend all the red and blue points you just connected are not there, and again connect the adjacent red and blue points. This is always possible because the arc you use to connect adjacent red and blue points does not "block" any unconnected points.

But it does block them when they're connected. If you can pretend that a red-blue segment isn't there, then why not pretend that intersecting segments don't intersect.

 

[ehrenfest]

That just means determine which of the unconnected red and blue points are adjacent. When you draw a line between these points you can always draw an arc over the connected points between them. Does that make sense.

 

[e(ho0n3]

So you're saying that the line segments can be curves? That would make much more sense.

 

[ehrenfest]

Oh. That's true. So, I guess the author of the problem should have stated that no three of the points are collinear.