[bonanova]

Being a puzzle freak I have no social life to speak of, so ...

last night I made some blue dots on a sheet of paper.

Be still my heart. But wait, there's more.

Then I made an equal number of red dots on the paper,

being careful not to have any three points, regardless of color,

in a straight line.

I imagined they were boys [blue dots] and girls [red dots] who

didn't solve puzzles, and therefore were capable of a social life.

So I endeavored to pair them up, using straight line segments,

each line segment connecting a boy [blue dot] with a girl [red dot].

This way, I reasoned, they could conveniently meet for a date.

But I found a problem: some of the lines crossed over previously

drawn lines. That might be confusing, I thought. A boy might take

a wrong turn at a crossing point, and end up meeting a girl who had

already met her date. [i assumed the dots were heterosexual.]

That suggested a puzzle. Heaven forbid it should suggest a date.

Here's the puzzle:

A computer, one that actually does have a random-number generator,

has placed n blue points and n red points at random on a sheet of

paper so that no three points are collinear. You are to connect them,

pairwise, red to blue, with straight line segments.

How large can n be so that, no matter where the dots are placed

on the paper, a set of connecting lines can be found such that

no two of the lines intersect?

Assume the paper is large enough and the pencil is sharp enough.

[Guest]

The procedure is not a construction of the minimal length condition.

It's only a proof that when you eliminate a crossing you decrease the

total length.

The proof that an arbitrarily large number of pairs can be connected

without crossings rests on the fact that whenever crossings are

eliminated the total length goes down. To repeat the proof,

Take all the possible pairings of the [artibrarily large] set of red

and blue points. Each pairing has a certain total length. Select

the pairing that has the shortest total length. This pairing has

no crossing. Proof: if it had a crossing, its length could be shortened.

OK?

There are few things more satisfying than a good old-fashioned non-constructive proof.

cheers.