The numbers 1 to 200 are randomly assigned to points on the circumfrence of a circle. The points are divided into 100 pairs, with no point in two pairs. The two points in each pair are joined by a chord.

Is it always possible to choose 100 pairs so that no chords intersect and the difference between the values in any one pair does not exceed 150?

I confess, I didn't completely follow the preceeding argument, but here is what I was thinking; admittedly not fully thought out.

Suppose the points are arranged in numeric order.  Connect point 1 to point 2, then 3 to 4, 5 to 6 etc.  The drawing would look like a 200 sided polygon inscribed inside a circle (except only every other side is drawn).

Now suppose you leave the chords all where they are, but scramble the numbers.  Find a "bad" chord where the numeric difference is more than 150.  It may be possible to move along the arc of the circle in either direction from the "bad" chord to find a subset of points such that the chords in that "arc" will satisfy the condition:

for example:  5---187     60---23  could be redrawn as
                          187---60
                    5------------------23

There may be a way to make a more rigorous chord-switching algorithm to make this into a proof (pro or con), but in this pre-coffee morning, I'm too combinatorially challenged to go further.

Posted by Larry on 2005-11-12 09:55:51