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