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?

Editor's note:
The following post, while retained for historical purposes, is INCORRECT.  In particular, OBSERVATION 1 on my first post is incorrect, so all reasoning and conclusions which follow from it (including this post) are incorrect also.  Credit to Charlie for pointing this out.
/******************************************/

 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 172?

Clearly, it is easier to not exceed 172 than it is to not exceed 150.  But I think the method I used in my solution (already posted) can be used to prove that even this easier objective is NOT always possible.

Place the 11 highest numbers contiguously.  The lowest of these is 190,  and there are 17 "clearly unsafe" numbers, including 1 and 2, and 172 "safer" numbers . (See my earlier post for a definition of "clearly unsafe" and "safer").  The remaining 189 numbers can be placed so that 1 "clearly unsafe" number is on either side of the highest 11, and so that there are never 11 consecutive "safer" numbers.   So it is not always possible to not exceed 172.

OPEN QUESTION:
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 173?  I can't disprove this using my technique, but maybe a sharper method would do it.  Anybody?

Edited on November 13, 2005, 7:33 am

Posted by Steve Herman on 2005-11-11 19:49:13