Pairing the points

[bonanova]

2n distinct points in the plane, no three of which are collinear, are colored red or blue in equal numbers. Is there a red-blue paring of the points that permits the pairs to be joined by n line segments with no crossings?

[plasmid]

Spoiler

Draw a convex perimeter around the set of points (the shape of a taut rubber band with all the points inside). Unless every point on the perimeter is the same color, you will be able to find a segment on the perimeter with alternating colors at its vertices. Draw a line connecting those points, and you can remove them from the puzzle and be left with a smaller set of points where the line you just drew is outside of its convex perimeter and therefore won’t prevent you from drawing any more lines, so you can just repeat until you’ve joined all the points with lines.

But what if you reach a state where every point on the convex perimeter is the same color? Find a line that can divide the set of points into two separate sets of points that each have the same number of red and blue points, and then apply that algorithm to each of those two subsets. If the subsets also have monochromatic perimeters, divide those subsets into subsets and keep repeating the process as much as necessary until you can start connecting opposite color points.

Need a proof that a line must exist that can divide a set of points into two separate sets of points with equal numbers of red and blue? Draw any old line and it will divide the points into two regions; if they have equal numbers of red and blue points then you’re done, and if not then call the region with more blue than red points region B and call the region with more red than blue points R. If you gradually rotate the line 180 degrees, then regions B and R will be swapped so now B has more red than blue points and R has more blue than red. At some point during that rotation, if you’re allowed to nudge the line around a bit to make sure that only one point crosses the line at a time (I know I’m doing some hand waving but I think it’s still reasonable), the B and R regions must have reached a point where the number of blue and red vertices were equal.

 

[Molly Mae]

 

If I understand correctly:

For n=1, yes.
For n=2, also yes: a triangle with a point in the centre

For n>2, should I assume that the lines are 1) redrawn for next possible colouring of each point, 2) evaluated for crossings after each redraw, 3) erased if if passes the evaluation, and 4) iterated back 1-4?

Edited January 29, 2018 by Molly Mae

[bonanova]

For each n it's a fresh start. So really it's just one question:

For any (every) n, can n red dots and n blue dots be joined pairwise with n line segments no two of which intersect?

[bonanova]

This puzzle has a nice "Aha!" proof.

[bonanova]

14 minutes ago, plasmid said:

  Hide contents

Draw a convex perimeter around the set of points (the shape of a taut rubber band with all the points inside). Unless every point on the perimeter is the same color, you will be able to find a segment on the perimeter with alternating colors at its vertices. Draw a line connecting those points, and you can remove them from the puzzle and be left with a smaller set of points where the line you just drew is outside of its convex perimeter and therefore won’t prevent you from drawing any more lines, so you can just repeat until you’ve joined all the points with lines.

But what if you reach a state where every point on the convex perimeter is the same color? Find a line that can divide the set of points into two separate sets of points that each have the same number of red and blue points, and then apply that algorithm to each of those two subsets. If the subsets also have monochromatic perimeters, divide those subsets into subsets and keep repeating the process as much as necessary until you can start connecting opposite color points.

Need a proof that a line must exist that can divide a set of points into two separate sets of points with equal numbers of red and blue? Draw any old line and it will divide the points into two regions; if they have equal numbers of red and blue points then you’re done, and if not then call the region with more blue than red points region B and call the region with more red than blue points R. If you gradually rotate the line 180 degrees, then regions B and R will be swapped so now B has more red than blue points and R has more blue than red. At some point during that rotation, if you’re allowed to nudge the line around a bit to make sure that only one point crosses the line at a time (I know I’m doing some hand waving but I think it’s still reasonable), the B and R regions must have reached a point where the number of blue and red vertices were equal.

 

Not bad. I like the fact you can throw away the connections you find without fear of removing a potential crossing with a future connection. It’s not the solution I had in mind but I think it works. Nice. 

[bonanova]

Spoiler

Another answer is the matching that minimizes the total length of the connecting line segments, which has a simple proof

 

[plasmid]

Probably not what you have in mind, but I realized part of my previous answer was superfluous so this is a little more elegant and gets rid of some hand waving.

Spoiler

Given a set with an equal number of red and blue points, it’s always possible to divide the set with a straight line into two subsets that each have an equal, positive number of red and blue points:

Pick a pivot point (not a red or blue point, just some unoccupied point) somewhere within the perimeter of the set of red and blue points and not colinear with any pair of the red or blue points, and draw a line through it that doesn’t intersect any of the red or blue points. If it divides the set into two subsets that each have an equal number of red and blue points, then you’re done. Otherwise, call the region with more red than blue points R and call the region with more blue than red points B. If you rotate the line 180 degrees around the pivot point then R and B will be swapped, so region R will have more blue than red and region B will have more red than blue. Since the pivot point is not colinear with any pair of red or blue points, the number of red or blue points in each region must increase or decrease by 1 if the line is rotated by a small enough angle, so during the rotation as region R goes from having more red to having more blue it must reach some angle where the number of red and blue points are equal. Since the pivot point is within the perimeter of the set of red and blue points, there must be at least one red and blue point in both subsets.

So you can start with the entire set of red and blue points and divide it into two subsets each with an equal number of red and blue points, then if either of those subsets have more than one point of each color you can divide that subset into two new subsets with equal numbers of red and blue to end up with three subsets, and keep repeating until you have many subsets each with one red and one blue point. Since the subsets will be convex, a line drawn between a red and a blue point within a subset won’t enter the regions of any other subsets, so you can connect the pair of points within each subset without worrying about overlap.

 

[bonanova]

Nice. A construction is certainly a proof of existence. A pairing without intersects exists and ... here it is!

Spoiler

I like this puzzle because the result is at first dubious. What if there were billions of points? But (think diagonals of a square) removing intersects always reduces connection length. So the pairing with the shortest connection length (which must exist) has no intersects.

Now I wonder if for any groups of n blue and n red points there is only one pairing without crossings?