superprismatic Posted July 13, 2009 Report Share Posted July 13, 2009 Suppose we have 2N points in the plane. N of the points are Red and N of them are Blue. Furthermore, no subset of 3 of these 2N points lie along a line. Prove or disprove: It is always possible to pair up the Red and Blue points into N pairs, one Red and one Blue in each pair connected by a line segment, in such a way that no line segment crosses another line segment. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted July 13, 2009 Report Share Posted July 13, 2009 I say it's true... no idea how to prove it. Any time you add a a new blue and a new red, you can re line all the other points to allow the new points to work. And this is because... there is always a secondary pre-existing arrangement that would work if it wasn't for one problem, and that problem is solved by the new points. With 2 points, no problem. Add 2 points on either side of the line from the first 2, and you can re line them to make it work. Add 2 more points, and if they're problematic, you revert back to step 1 position, and the second 2 points added link up to the third 2 points. And so on... I wonder if I'm totally off =P Quote Link to comment Share on other sites More sharing options...
0 Guest Posted July 13, 2009 Report Share Posted July 13, 2009 (edited) Just to clarify, is every pair connected to every other pair by a line. Like so.untitled.bmp Edited July 13, 2009 by jjcanny1 Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted July 13, 2009 Report Share Posted July 13, 2009 Take all the possible pairings of the red and blue points. For one of the pairings of all the points, the total length of the connecting line segments will be smallest. Call this the minimal-length pairing [MLP]. This pairing has no crossings. Proof: assume the MLP has a crossing. Specifically, suppose that in the MLP, the segment connecting a to b crosses the segment connecting c to d. Since no 3 points are collinear, adbc is a quadrilateral with [crossing] diagonals ab and cd. By the triangle inequality we can reduce the total length by pairing a with d and c with b. Thus the MLP was not the MLP; that is, the assumption is disproved. More discussion Quote Link to comment Share on other sites More sharing options...
0 Guest Posted July 13, 2009 Report Share Posted July 13, 2009 For each N, the resulting shape of 2N points is a 2N polygon. Example, if N is 2, 2N points are arranged as a quadrilateral as shown by bonanova, if N is 3, the 2N points are arranged as a hexagon and so on... To prove (or disprove) consider N is infinte then the 2N points can be arranged in a circle. Now in this circle there is always possible to find chords connecting blue and red points that do not intersect. Try it with alternating blue and red points or alternating sets of 2 or 3 or more. It can always be done. Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted July 13, 2009 Author Report Share Posted July 13, 2009 Take all the possible pairings of the red and blue points. For one of the pairings of all the points, the total length of the connecting line segments will be smallest. Call this the minimal-length pairing [MLP]. This pairing has no crossings. Proof: assume the MLP has a crossing. Specifically, suppose that in the MLP, the segment connecting a to b crosses the segment connecting c to d. Since no 3 points are collinear, adbc is a quadrilateral with [crossing] diagonals ab and cd. By the triangle inequality we can reduce the total length by pairing a with d and c with b. Thus the MLP was not the MLP; that is, the assumption is disproved. More discussion Oops! I even searched to see if I could find this puzzle here. I guess that shows how poor a searcher I really am! Sorry to have duplicated a puzzle. Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted July 14, 2009 Report Share Posted July 14, 2009 Oops! I even searched to see if I could find this puzzle here. I guess that shows how poor a searcher I really am! Sorry to have duplicated a puzzle. Not to worry; you made the effort, and finding the right search words is not simple. This is a nice puzzle, that has a glaringly correct but difficult to find solution. Quote Link to comment Share on other sites More sharing options...
Question
superprismatic
Suppose we have 2N points in the plane. N of the points
are Red and N of them are Blue. Furthermore, no subset of
3 of these 2N points lie along a line.
Prove or disprove:
It is always possible to pair up the Red and Blue
points into N pairs, one Red and one Blue in each pair
connected by a line segment, in such a way that no line
segment crosses another line segment.
Link to comment
Share on other sites
6 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.