Problem about red and blue dots

Task text

Given a plane. On it are located n red and n blue points, and no three points lie on the same straight line. Prove that it is always possible to connect points by pairwise non-intersecting segments so that each red point is connected by a segment to a blue one and each blue point is connected by a segment to a red one.

I suggest not to jump to the analysis immediately, but to stop and think. Below is a hint for self-control that the condition is correctly understood.

Tip for self-control

Obviously, the segments should be exactly n things.

Indeed, we have n red dots. Each red dot requires at least one segment, so there must be at least one segment n.

In this case, no point can be connected to more than one other, because otherwise, the point will lie on two different segments, which means that technically it will be the point of their intersection, which is forbidden. Therefore, in total n segments.

My decision

Let’s prove it by induction. The base is an empty set of points. The idea of the transition is to reduce the problem of size n to problems of size less than n.

Consider the boundary of the convex hull of the set of all points (imagine that we pulled a rubber band over the points so that they were inside, some of the points fell on the boundary). Note that the result is a polygon, at the corners of which there are points. Moreover, the points can lie only in its corners, because By assumption, no three points lie on the same straight line.

An example of a convex hull for an arbitrary set of points

Note that if on the boundary of the resulting polygon at least two points have a different color, then there are two points of the same color nearby. Let’s find two such points, connect them with a segment. Now all the other points are in one of the half-planes relative to the straight line on which our segment lies, which means that no other possible segments will intersect with it, i.e. you can “delete” this pair of points and go to the size problem n – 1.

This can be done as long as at least two points of different colors lie on the boundary of the convex hull. Consider separately the case when all points on the boundary have the same color.

Without loss of generality, we assume that all points on the boundary turn out to be blue. Since the set of points is finite, so is the set of lines on which at least two points lie. Therefore, the set of angles of inclination of these lines is also finite. So, you can choose a new angle of inclination, such that no two points lie on a line with such an angle. Let’s build a straight line with this same angle and start moving it (for definiteness, from left to right). Then all the points will first be in the right half-plane relative to the line, then their number will change as the line intersects with the points, and in the end – all the points will be on the left.

Note that the leftmost and rightmost points belong to the boundary of the convex hull, which means they are the same color!

Movement of a straight line from the left point to the right (the straight line might not be vertical)

We will count the number of blue and red dots to the left of the straight line: red_cnt(x) And blue_cnt(x). Initially red_cnt(x) = blue_cnt(x) = 0. Loan line intersects the first blue point and then red_cnt(x) = 0, blue_cnt(x) = 1. As the line moves to the right, these numbers increase (each time one of the numbers increases by 1). At the end, the last blue dot will be added and the numbers reached n (red_cnt(x) = blue_cnt(x) = n). This means that before the last blue dot was added, the values were red_cnt(x) = n, blue_cnt(x) = n – 1. Those. we have two functions, and blue_cnt began to grow earlier, but reached n later than red_cnt. This means that these functions take the same value somewhere between the start left and right points: red_cnt(x) = blue_cnt(x). In other words, there is a line that divides the plane into two non-empty half-planes, each of which has an equal number of blue and red points! So, we reduced the problem of size n to two smaller problems. Ch.t.d.

The solution of the authors of the problem

Let’s build n segments whose ends connect points of different colors (not necessarily without intersections). You can build like this: as long as there are points not connected by a segment, we will take a pair of “free” points and connect them.

Now consider any pair of segments that have an intersection (see figure). Let’s delete two segments with intersection and construct two new segments without intersections. Note that due to the triangle inequality, each time we perform such an action, we reduce the total length of all available segments. Since the number of ways to connect the segments is finite and each time we move from one method to another, reducing the total length, this process will have to stop one day. At this moment, we will not have any more intersections, therefore we will always get the desired construction. Ch.t.d.

Transition from the intersection of a pair of segments with a decrease in the total length

Conclusion

The peculiarity of the second solution is that we have introduced a certain numerical parameter that characterizes the construction and learned how to perform actions that lead to its reduction. Personally, it reminded me of the twenty-card problem from my favorite movie. X+Y (see excerpt in English.), thus resonated in my soul. However, if I had immediately spied on it, I would never have come up with my own.