All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 100 Chords (Posted on 2005-11-11)
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?

 See The Solution Submitted by Brian Smith Rating: 4.0000 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Almost adjacent pairs idea | Comment 5 of 10 |
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

 Search: Search body:
Forums (2)