1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Points in a plane

  1. Nov 19, 2007 #1
    1. The problem statement, all variables and given/known data

    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


    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. jcsd
  3. Nov 19, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

    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).
  4. Nov 19, 2007 #3
    Each of the line segments has one red endpoint and one blue endpoint. So your diagram is wrong.
  5. Nov 19, 2007 #4
    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?
  6. Nov 19, 2007 #5
    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.

    Last edited: Nov 19, 2007
  7. Nov 19, 2007 #6
    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.
  8. Nov 19, 2007 #7
    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.
  9. Nov 19, 2007 #8
    So you're saying that the line segments can be curves? That would make much more sense.
  10. Nov 19, 2007 #9
    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook