Red–Blue Matching · affine·mess

n = 4

Drag the dots. The shortest red–blue pairing is drawn live. It may switch; it never crosses.

Shortest is never crossing

Put n red and n blue points in the plane, no three on a line, and pair every red with a blue so that the total length of the segments is as small as possible. Then no two segments cross. Ever.

Why

Suppose two segments r₁b₁ and r₂b₂ did cross, at a point X. Swap partners: r₁b₂ and r₂b₁. By the triangle inequality,

|r₁b₂| + |r₂b₁| < |r₁X| + |Xb₂| + |r₂X| + |Xb₁| = |r₁b₁| + |r₂b₂|,

strictly, because nothing is collinear. So the swap made the matching shorter, and the one we started with wasn't the shortest. Done.

What to look for

The shortest matching is not a continuous function of the points. Drag one dot slowly and the whole pairing can rearrange at once (it flashes when it does). The segments jump, but they still never cross.

Corollary

A crossing-free red–blue pairing always exists, which is a well-known olympiad problem (it appeared on the 1979 Putnam). The shortest one is a witness. The proof above is the whole solution.

Under the hood

The minimum is found exactly, not heuristically: a bitmask dynamic program over subsets of red points, O(n²·2ⁿ), recomputed on every drag. That's why n stops at 10.