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?

 Submitted by Brian Smith Rating: 4.0000 (3 votes) Solution: (Hide) First, prove that if we have any set of 2n points on a circle, divided into two subsets A and B of n points each, then there is a way to pair each element of A with an element of B such that the chords between the paired elements do not intersect. It's easy by induction. It's obviously true for n = 1. Assume it's true for n and suppose that we have 2(n+1) points on the circle divided into two sets of size n+1 each. There clearly must be an element, a, of A which is adjacent to an element, b, of B. We will pair a and b, and then use the induction hypothesis to pair up A-{a} and B-{b}. None of the latter n chords intersect by the induction hypothesis, and none of them intersect the chord between a and b since those points are adjacent. Now the problem's solution is immediate by letting A be the set of points numbered from 51 to 150 and B be all of the other points.

 Subject Author Date re: 100% Solution Tristan 2005-11-15 20:34:45 100% Solution Steve Herman 2005-11-15 12:10:23 99% solution Cory Taylor 2005-11-15 01:21:27 re(2): Solution? Spoiler? Steve Herman 2005-11-12 12:09:31 re: Solution? Spoiler? Charlie 2005-11-12 10:48:32 Almost adjacent pairs idea Larry 2005-11-12 09:55:51 172 and 173 -- Spoiler Steve Herman 2005-11-11 19:49:13 Solution? Spoiler? Steve Herman 2005-11-11 19:08:43 re: are they consecutive? - nevermind Josh70679 2005-11-11 14:19:22 are they consecutive? Josh70679 2005-11-11 13:19:41

 Search: Search body:
Forums (45)