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?

(In reply to Solution? Spoiler? by Steve Herman)

I didn't follow completely your entire argument, but I note something wrong with observation 1:

"OBSERVATION 1:
Because the chords are non-overlapping, the first chord drawn determines all the rest.  Just to explain, number the points sequentially (1, 2, 3, etc.).  If 2 is connected to 75, then 3 must be connected to 74, and 4 must be connected to 73, and 1 must be connected to 76, and 200 must be connected to 77, etc.  "

Take a simpler case: 1 is connected to 6. Then either 2 could be connected to 5 and 3 to 4, or 2 could be connected to 3 and 4 to 5.  A larger gap, such as your 2 to 75 would allow even more possible subsets to be formed among 3 to 74, as for example, 3 might be connected to 40 and 41 to 74, and continue from there, with choices at each subdivision until you're down to 2.

 

Posted by Charlie on 2005-11-12 10:48:32