# Points in a plane

1. Nov 19, 2007

### ehrenfest

1. The problem statement, all variables and given/known data
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?

2. Relevant equations

3. The attempt at a solution

Last edited: Nov 19, 2007
2. Nov 19, 2007

### 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).

3. Nov 19, 2007

### ehrenfest

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

4. Nov 19, 2007

### 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?

5. Nov 19, 2007

### 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?

Last edited: Nov 19, 2007
6. Nov 19, 2007

### e(ho0n3

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.

7. Nov 19, 2007

### 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.

8. Nov 19, 2007

### e(ho0n3

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

9. Nov 19, 2007

### ehrenfest

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

Last edited: Nov 19, 2007