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

Home > Shapes > Geometry
100 Chords (Posted on 2005-11-11) Difficulty: 4 of 5
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.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
re: 100% SolutionTristan2005-11-15 20:34:45
100% SolutionSteve Herman2005-11-15 12:10:23
Solution99% solutionCory Taylor2005-11-15 01:21:27
re(2): Solution? Spoiler?Steve Herman2005-11-12 12:09:31
re: Solution? Spoiler?Charlie2005-11-12 10:48:32
Almost adjacent pairs ideaLarry2005-11-12 09:55:51
172 and 173 -- SpoilerSteve Herman2005-11-11 19:49:13
Solution? Spoiler?Steve Herman2005-11-11 19:08:43
re: are they consecutive? - nevermindJosh706792005-11-11 14:19:22
Questionare they consecutive?Josh706792005-11-11 13:19:41
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (45)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information