[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.

[Yoruichi-san]

Lol...well you can think about puzzles *and* date...you just have to know how to pretend like you're actually listening to what your date is saying instead of trying to figure out the answer to the latest puzzle...;P

Anyways, I think I'm misunderstanding the problem, are you asking for the largest n that it is possible to have all nonintersecting lines?

Make a circle w/ top half blue (blue semicircle) and bottom half red...then connect with lines going up and down...assuming you can put infinitely small dots, you can put an infinite number of lines...

This can also be done w/ other conic sections, i.e. red/blue hyperbola...but I'm not sure if this is what you meant...

[bonanova]

Lol...well you can think about puzzles *and* date...you just have to know how to pretend like you're actually listening to what your date is saying instead of trying to figure out the answer to the latest puzzle...;P

Anyways, I think I'm misunderstanding the problem, are you asking for the largest n that it is possible to have all nonintersecting lines?

Make a circle w/ top half blue (blue semicircle) and bottom half red...then connect with lines going up and down...assuming you can put infinitely small dots, you can put an infinite number of lines...

This can also be done w/ other conic sections, i.e. red/blue hyperbola...but I'm not sure if this is what you meant...

Yeah, you're missing this paragraph:

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.

If I get to place the points myself,

I'll place them at {0, y} and {1, y} for infinitely many y values.

You specified n.

The computer threw 2n dots at random onto the x-y plane, half red and half blue.

You connect the pairs with non-intersecting straight line segments, no two of which intersect.

How big a value of n can you specify, and still guarantee that you will succeed?

btw - i got a date for tomorrow def, and maybe next tuesday

[Guest]

Is this the same as asking, what is the fewest number of dots you could intentionally place on a piece of paper such that they can't be connected by non-intersecting lines? In other words, you're guaranteeing that the random placement won't be your intentional arrangement.

[Guest]

is it

half the resolution of the computer or the printer?

[bonanova]

Is this the same as asking, what is the fewest number of dots you could intentionally place on a piece of paper such that they can't be connected by non-intersecting lines? In other words, you're guaranteeing that the random placement won't be your intentional arrangement.

Yes, that's a fair restatement of the problem.

If it's possible for any set of N pairs [and below] but impossible for at least one set of N+1 pairs, what's N?

Equivalently, what's N+1?

[Guest]

Yes, that's a fair restatement of the problem.

If it's possible for any set of N pairs [and below] but impossible for at least one set of N+1 pairs, what's N?

Equivalently, what's N+1?

N does not exist. For any number of pairs, you can connect them with non-intersecting lines.

I'm not positive that's true, and I definitely don't know how to prove it, but that's what it looks like to me.

[bonanova]

is it

half the resolution of the computer or the printer?

No. You can assume these are mathematical lines and dots, so that

such mundane, real-life, engineering problems don't limit you.

[Guest]

I think I'm coming to the same conclusion as Chuck:

For any set of [n] pairs I try, I can't find an [n+1] pair which can't be solved by a set of "swapping" actions.

in the simplest case:

.......R3

.......¦

.......¦

R1-------B1

.......¦

R1-------B2

.......¦

.......B3

is solved by swapping connections to B3/B2 and then B1/B2.

The only other thought I had, was: is it possible to always draw a continuous line which divides the entire sheet of paper into two halves, one side of which has only red and the other which has only blue. If so, can we say that, topographically (and by choosing some arbitrarily complex coordinate system), it is just the same as the scenario suggested where all the red are at negative-y and the blue are at positive-y? The solution is then trivial (ish).

(Note: apologies for the dots: they are the only way I can find to space it. Any idea how I indent text? I don't have access to the editor side panel)

Edited August 1, 2008 by foolonthehill

[bonanova]

I think I'm coming to the same conclusion as Chuck:

For any set of [n] pairs I try, I can't find an [n+1] pair which can't be solved by a set of "swapping" actions.

in the simplest case:

.......R3

.......¦

.......¦

R1-------B1

.......¦

R1-------B2

.......¦

.......B3

is solved by swapping connections to B3/B2 and then B1/B2.

The only other thought I had, was: is it possible to always draw a continuous line which divides the entire sheet of paper into two halves, one side of which has only red and the other which has only blue. If so, can we say that, topographically (and by choosing some arbitrarily complex coordinate system), it is just the same as the scenario suggested where all the red are at negative-y and the blue are at positive-y? The solution is then trivial (ish).

(Note: apologies for the dots: they are the only way I can find to space it. Any idea how I indent text? I don't have access to the editor side panel)

You can format text horizontally using a code box:

(codebox)|1

2 there is a space before this 2

3 there are two spaces before this 3(/codebox) which gives

1

 2

  3[/codebox]
or specifying a monospace font: (except for that you do need a nonblank character in the first position) 

(font="Courier New")]|1

| 2 there is a space before this 2

|  3 there are two spaces before this 3(/font) which gives

[font=Courier New]|1

| 2

|   3 -- oops - no. leading and multiple blanks are ignored outside of code boxes[/font]

[Guest]

I had initially dismissed this problem as simply not to my taste, but after thinking upon it some more, there are some very interesting aspects to it. I don't have the time right now to properly organize my thoughts, but I have a feeling the solution contains a paradox.

Very nice brain-bender.

[HoustonHokie]

I tend to think Chuck's right as well. And I don't think anyone has to travel very far for their date...

I think the idea is to connect the pairs that are closest together, but there are some rules.

You can't do it arbitrarily, or you might end up with foolonthehill's crossing solution. If you figured out the distance between each possible pair b_x,g_y and organized them on a grid, similar to those they put in maps to tell you the distances between cities, you'd come up with a list of the distance between every boy and every girl.

Every boy and girl would each have a minimum distance to travel to meet a member of the opposite sex. Starting with the boy or girl who has to travel the farthest to meet the mate that's closest to them, connect that love-seeker with the closest member of the opposite sex. Remove those two members from the grid and recalculate. I think you'll find that you will connect as many happy couples as you could possibly plot.

I'll try my idea with a relatively large set (say 50 couples) and see what happens.

[HoustonHokie]

Well, it didn't work out quite like I planned, but I was able to connect 50 happy couples this afternoon. I just couldn't do it the way I theorized last night. I figure that if I can do it for 50, I can probably do it for 500, 5000, or 5000000. Just give me a sharp pencil, a big piece of paper, and a lot of coffee... I wish I could describe what I was doing in a logical way so that bona could get a proof out of the deal. All I can say is that it seemed I was working from the outside in - like I was maybe trying to create a new bounding area for the paper. Anyway, here's what I came up with for 50 pairs on a regular 8.5x11 sheet of paper.

50_Happy_Couples.pdf

[Guest]

I like fool's idea of using a curve to split the paper into two sections, with all reds on one side and all blue on the other. I'm pretty sure this will always be possible, but again I can't prove it.

Once you have that curve drawn, you can order the red and blue dots by how far along the line they are. Then you just pair them up across the curve, and the lines should never intersect.

[HoustonHokie]

I like fool's idea of using a curve to split the paper into two sections, with all reds on one side and all blue on the other. I'm pretty sure this will always be possible, but again I can't prove it.

Once you have that curve drawn, you can order the red and blue dots by how far along the line they are. Then you just pair them up across the curve, and the lines should never intersect.

I like the idea, although is seems to me there are two issues. First, you will probably need more than one curve, particularly if you want all the blues on one side and all the pinks on the other. The second, and more challenging, is how to construct the curve in the first place. In order to guarantee that no pairings cross one another, the curve has to be constructed so that it is always perpendicular to the pairing lines in order to guarantee no intersecting lines. From what I can tell so far, you have to construct the curve after you've already made the pairings. Is it purely visual, or is there some rhyme and reason to making the curve?

[Guest]

I like the idea, although is seems to me there are two issues. First, you will probably need more than one curve, particularly if you want all the blues on one side and all the pinks on the other. The second, and more challenging, is how to construct the curve in the first place. In order to guarantee that no pairings cross one another, the curve has to be constructed so that it is always perpendicular to the pairing lines in order to guarantee no intersecting lines. From what I can tell so far, you have to construct the curve after you've already made the pairings. Is it purely visual, or is there some rhyme and reason to making the curve?

I'm pretty certain that it would only require one line to divide them into blue/red, though I have no strategy to construct such a line - I would be keen to see a counter-example if you can find one (I couldn't!). As for making sure it is perpendicular, I'm not certain that this would help, because the dividing line can be arbitrarily deformed near each connecting line (the green line in my diagram A has been deformed locally so that it crosses perpendicular). Therefore, if I can solve it with a line which is perpendicular, then I can also solve it with an infinite number of other lines which passes through each of the same "meeting" points in the same direction.

In response to your last point, and when trying this, I have not been connecting the dots first. I simply move around the page, keeping blue left and red right, and then join them afterwards across the dividing line. Your points make me think: it should be true that if we can solve the problem with non-intersecting "connecting" lines, then there *must* be a (infinite set of) dividing line which separate red from blue:

mark the mid-points of each "connecting" line and draw a line which passes through all of them, in any order without crossing itself. (the "dividing" line) - this could simply be from left to right / top to bottom on the page.

each time the dividing line crosses a connecting line, it can be locally deformed around the end of the connecting line (diagram B)

each time the dividing line crosses a connecting line in the wrong direction, it can be locally deformed around both ends of the connecting line (diagram C)

(Actually, I think you need to do C before B).

However, can we do the reverse and say that for a given dividing line, there is a defined set of connecting lines which are non-intersecting? That is where I am heading.... or at least trying to!

[Guest]

Right I think I'm getting there....

Mark a point anywhere on the paper (green cross on my diagram)

Join each blue dot in order from the furthest to the nearest to form a spiral (you can never meet a red if you join them with straight lines, as there are no collinear points)

Perturb your line very lightly either side of the dots to make a spiral sausage that encloses the blue dots and no red dots.

I think it helps, but can't find a strategy to pair up the reds with each ordered blue, though it seems quite simple when you try!

edit: fixing diagrams

Edited August 4, 2008 by foolonthehill

[Guest]

Right I think I'm getting there....

Mark a point anywhere on the paper (green cross on my diagram)

Join each blue dot in order from the furthest to the nearest to form a spiral (you can never meet a red if you join them with straight lines, as there are no collinear points)

Perturb your line very lightly either side of the dots to make a spiral sausage that encloses the blue dots and no red dots.

I think it helps, but can't find a strategy to pair up the reds with each ordered blue, though it seems quite simple when you try!

edit: fixing diagrams

hmmmm....

[bonanova]

foth,

Interesting development.

To discuss the connection of the red dots, once the sausage is drawn,

what if all the red points were [say] in the lower left corner?

Is there a procedure for connecting them to the blues?

Starting with them all in one place [arbitrarily close, not coincident]

might help develop a general procedure.

I have a thought on this, but I'm interested in yours.

Edit: Ah, I see you are already thinking along that line.

[Guest]

I still like this procedure:

1. Separate the dots with a curve so that all blue are on one side, and all red are on the other side (white line)

2. Draw the shortest line possible from each point to the curve. For a smooth curve, these lines would all be perpendicular (yellow lines)

3. Starting at one end of the curve, number each intersection from 1 on up (teal numbers (running out of colors here...))

4. Pair up the lowest-intersecting blue dot with the lowest-intersecting red dot and draw the line between (green lines)

5. Repeat for the next lowest pair, and so on.

Again, not a proof, but I can't find a counter-example

Come to think of it, the spiral-sausage thing might be pretty good evidence that the dividing line in step 1 will always exist. Just open up one end of it.

[bonanova]

CR has found it.

The answer is that there is no limit to the number of points in the plane that can be paired by non-intersecting line segments.

Most of us concluded this. But how to prove it?

The proof has two parts:

1. describe a set of pairings that has no intersections - prove the existence of non-intersecting pairigs.
   
2. give a procedure for constructing a non-intersecting solution.
   

1. Description of a set of pairings that have no crossings. [Existence proof]

The set of pairings that minimizes the total length of the connecting line segments has no crossings.

To see this, suppose two line segments [a,b] and [c,d] cross.

Draw the quadrilateral adbc. Note that ab and cd are the diagonals of that figure.

Reverse the blue [or red] dots to connect [a,d] and [c,b].

These are the sides, rather than the diagonals of the figure.

They do not intersect, and, by the triangle inequality, they are [collectively] shorter.

Thus:

Any set of pairings that have crossings can be shortened.

Any set of pairings that cannot be shortened has no crossings -> the set that minimizes the total length has no crossings.

2. Procedure

Pair the red and blue dots in an arbitrary fashion.

If two lines cross, reverse the red [or blue] points.

Repeat until there are no more crossings.

[Guest]

CR has found it.

The answer is that there is no limit to the number of points in the plane that can be paired by non-intersecting line segments.

Most of us concluded this. But how to prove it?

The proof has two parts:

1. describe a set of pairings that has no intersections - prove the existence of non-intersecting pairigs.
   
2. give a procedure for constructing a non-intersecting solution.
   

1. Description of a set of pairings that have no crossings. [Existence proof]

The set of pairings that minimizes the total length of the connecting line segments has no crossings.

To see this, suppose two line segments [a,b] and [c,d] cross.

Draw the quadrilateral adbc. Note that ab and cd are the diagonals of that figure.

Reverse the blue [or red] dots to connect [a,d] and [c,b].

These are the sides, rather than the diagonals of the figure.

They do not intersect, and, by the triangle inequality, they are [collectively] shorter.

Thus:

Any set of pairings that have crossings can be shortened.

Any set of pairings that cannot be shortened has no crossings -> the set that minimizes the total length has no crossings.

2. Procedure

Pair the red and blue dots in an arbitrary fashion.

If two lines cross, reverse the red [or blue] points.

Repeat until there are no more crossings.

I see your theory, and it is where I started from, but have a problem with your statement that, because you can fix any 'pair' of crossing lines, that every cross can be fixed. I had the "you can always fix a pair of crossed lines" fairly early, but always had the problem that fixing one does not guarantee that you don't make a new crossing.

Though I can't find a counter-example (and still think that there aren't any), I don't think your proof excludes the possibility that "some" pairs of points mutually cross one another. ie. I am looking for a scenario where each time you fix a pair, you make a new crossing, and which eventually leads you back to making the first pair cross again.

Actually, thinking about it, maybe this is where the importance of the triangle inequality comes in...

[bonanova]

Any set of pairings that have crossings can be shortened.

Therefore any set of pairings that cannot be shortened has no crossings.

There is a set S of pairings for which the total length is minimized. S has no crossings.

[Prime]

CR has found it.

The answer is that there is no limit to the number of points in the plane that can be paired by non-intersecting line segments.

Most of us concluded this. But how to prove it?

The proof has two parts:

1. describe a set of pairings that has no intersections - prove the existence of non-intersecting pairigs.
   
2. give a procedure for constructing a non-intersecting solution.
   

1. Description of a set of pairings that have no crossings. [Existence proof]

The set of pairings that minimizes the total length of the connecting line segments has no crossings.

To see this, suppose two line segments [a,b] and [c,d] cross.

Draw the quadrilateral adbc. Note that ab and cd are the diagonals of that figure.

Reverse the blue [or red] dots to connect [a,d] and [c,b].

These are the sides, rather than the diagonals of the figure.

They do not intersect, and, by the triangle inequality, they are [collectively] shorter.

Thus:

Any set of pairings that have crossings can be shortened.

Any set of pairings that cannot be shortened has no crossings -> the set that minimizes the total length has no crossings.

2. Procedure

Pair the red and blue dots in an arbitrary fashion.

If two lines cross, reverse the red [or blue] points.

Repeat until there are no more crossings.

I'm afraid, I don't understand the proof. Especially the part where "every set of pairings can be shortenned". Was it proved?

Consider:

Here is an example where after picking random paring of 8 points and applying the "procedure" as prescribed the crossing line sets multiply and become longer:

Where is the proof that after repeatedly applying the procedure as prescribed, we don't end up with different longer sets of crossed lines. Furthermore, why the points that we start with when applying the procedure can't come into cross-lined arrangements later on?

[Prime]

Upon further reflection, I do see the proof.

Here is an example of how the "procedure" increased number of intersecting lines:

Suppose we had a set of (n-1) points, which was ordered in a non-intersecting way. Add two new points Bn and Gn. Connect them with a straight line. That line may intersect a number of segments. After just two steps of applying the procedure: 1) connecting B1-Gn and Bn-G1; 2) connecting B2-Gn and B1-G2; we created higher complexity of intersecting lines including the intersection of Bn-G1 and B1-G2.

Nonetheless, THE TOTAL LENGTH OF ALL SEGMENTS HAS DECREASED.

Another example, where applying the "procedure" does not create the minimal total segment length. It comes to the arrangement (2) on the picture, whereas minimal arrangement would be as shown in (3).

Still, it does eliminate all intersections.

[bonanova]

Another example, where applying the "procedure" does not create the minimal total segment length. It comes to the arrangement (2) on the picture, whereas minimal arrangement would be as shown in (3).

Still, it does eliminate all intersections.

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?