10
$\begingroup$

Suppose $n$ red dots and $n$ blue dots are arranged in the plane so that no three dots lie on a single line. Show that you can connect each red dot to a blue dot using a line segment so that no pair of line segments intersect.

$\endgroup$
  • $\begingroup$ Straight line segments, or can they be curved? $\endgroup$ – Bailey M Jun 18 '15 at 20:34
  • $\begingroup$ @BaileyM: Straight line segments is the intended puzzle. $\endgroup$ – Tyler Seacrest Jun 18 '15 at 20:42
  • $\begingroup$ Can blue dots be connected to multiple red dots, or is it always a 1-to-1 relationship? $\endgroup$ – Bailey M Jun 18 '15 at 20:46
  • 1
    $\begingroup$ @BaileyM: Good question; needs to be a 1-to-1 relationship. $\endgroup$ – Tyler Seacrest Jun 19 '15 at 2:43
  • $\begingroup$ Is the no-three-dots lie on a line a strictly necessary condition? $\endgroup$ – BmyGuest Jun 19 '15 at 8:17
16
$\begingroup$

Start by drawing a line segment from each red point to an arbitrary blue point.

If there are no intersections, we are done. Otherwise,

pick any two intersecting segments AX and BY, where A and B are blue and X and Y are red. Now BX and AY cannot intersect, so erase AX and BY and replace them by BX and AY. By the triangle inequality (AX, BY, BX, AY form a butterfly shape with two triangles), the total length of the line segments has strictly decreased.

Keep on repeating this process as long as intersections exist. Since the total length decreases at each step and there are only finitely many ways of connecting each red point to a different blue point, the process must terminate. When it does, there are no intersections.

QED.


For the more visual types:

Solution

and if you continue this to the end:

enter image description here

enter image description here

$\endgroup$
  • 1
    $\begingroup$ @BmyGuest Thanks for the pics! Wish I could upvote you for it :-) $\endgroup$ – Rand al'Thor Jun 19 '15 at 8:14
  • 1
    $\begingroup$ Nice solution. I took the liberty and edited in some visuals. Wouldn't the algorithm be "better" if at start each red point is attached to its "closest" blue point? Which brings up a bonus question: What general statements can be made about the maximum steps necessary? (Additional information from the starting set may be incorporated.) $\endgroup$ – BmyGuest Jun 19 '15 at 8:14
7
$\begingroup$

A concise and elegant proof was given by rand al'thor. Here's a considerably less concise proof:

First, we'll define dividing connection as follows: extend the line segment connecting one pair of blue and red points into an infinite line. This line splits the plane into two parts. If, within each part, there are equally many blue and red points, call the connection between the blue point and the red point a dividing connection.

A dividing connection between two points

This figure shows a dividing connection between the points $B_6$ and $R_6$. There are three blue and three red points above the line, and two red and two blue points below the line.

A connection between $B_5$ and $R_5$ would also be a dividing connection, with five blue and red points to the left of the line, and none to the right.

Assumption: Every set of points has a dividing connection. I will use this assumption in an inductive proof that we can connect opposite colored points for any sized set of points, and then provide a proof of the assumption.

If every set of points has a dividing connection, then in every set of $n$ red and $n$ blue points, we can connect points of opposite colors with non-overlapping line segments. Call a set where we can make such connections a connectable set.

The set of $0$ red and $0$ blue points is trivially connectable. The set of $1$ red and $1$ blue point is also trivially connectable: just connect the two points.

Assume any set of $k$ red and $k$ blue points is connectable. For a set of $k+1$ red and $k+1$ blue points, we can find a dividing connection within that set. That dividing connection splits the plane into two parts, each containing $k$ or fewer red and blue points. By our inductive assumption, the set of points in each part of the plane is connectable. The set of $k+1$ red and blue points is connectable: take the connections for each of the two separate parts together with the dividing connection.

Therefore, by induction, any set of $n$ red and $n$ blue points is connectable.

Proof of existence of dividing connection: I will show that every set of points has a dividing connection.

Consider the leftmost point, the point with the least $X$-coordinate. If two points have the same $X$-coordinate, consider the one of those that has the least $Y$-coordinate. That point has a dividing connection with some other point. Call this point $A$.

Consider the vertical line through $A$. For any other point $B$, we can find the angle between that line and the line segment $\overline{AB}$.

Angle between vertical line and point

This image shows this angle between the point $A$ and one of the other points. Since no three points are co-linear, all points have a distinct value for this angle, and since we chose a left-most point, the values of this angle are in the range $[0^\circ,180^\circ)$. We can put all of the points other than $A$ in sequence based on the value of this angle. For the above figure, the sequence would be:

$\color{blue}{B}\color{red}{R}\color{red}{R}\color{red}{R}\color{blue}{B}$

For a set of $n$ blue and red points, this sequence is of length $2n-1$. For each point in the sequence, we will consider three things:

  • The number of same-colored points at this location or earlier in the sequence. Call this quantity $S$.
  • The number of different-colored points at this location or earlier in the sequence. Call this quantity $D$.
  • Whether the point is a different color from $A$

This is a table of these values for the above image:

$$ \begin{array}{c|cccc} \text{index} & \text{color} & \text{S} & \text{D} & \text{different?} \\ \hline 1 & \color{blue}{B} & 1 & 0 & \text{no} \\ 2 & \color{red}{R} & 1 & 1 & \text{yes} \\ 3 & \color{red}{R} & 1 & 2 & \text{yes} \\ 4 & \color{red}{R} & 1 & 3 & \text{yes} \\ 5 & \color{blue}{B} & 2 & 3 & \text{no} \\ \end{array} $$

In general, if there are $n$ red and blue points, the final values of $S$ and $D$ in this table will be:

$$ \begin{array}{c|cccc} \text{index} & \text{S} & \text{D} \\ \hline 2n-1 & n-1 & n \\ \end{array} $$

since there are $n$ other points of a different color than $A$, and $n-1$ other points the same color.

For any point where $D = S+1$ and that is a different color from point $A$, the connection between $A$ and that point is a dividing connection. For that point, there will be $D$ points of each color on one side of the connection, and $n-D$ points of each color on the other.

Such a point always exists. $S$ and $D$ start out equal at $0$, and always end with $D = S+1$. Thus, there must be some point in the table where $D$ becomes greater than $S$. $D$ can only increase at points in the sequence that are a different color than $A$, so at such a point in the table, we have the conditions necessary for a dividing connection: $D = S+1$ at a point a different color than $A$.

Thus, a dividing connection can always be found, which proves the assumption we needed for the inductive proof that for any set of $n$ red and $n$ blue points, we can connect distinct pairs of different colored points with non-overlapping line segments.

$\endgroup$
  • $\begingroup$ Not as concise but very interesting and very well written. $\endgroup$ – Tyler Seacrest Jun 19 '15 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.