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?
Editor's note:
The following proof, while retained for historical purposes, is
INCORRECT. In particular, OBSERVATION 1 is incorrect, so all
reasoning and conclusions which follow from it are incorrect
also. Credit to Charlie for pointing this out.
/******************************************/
Well, I'll try first.
I think it is NOT always possible.
Here's a counter-example (hope I didn't make a mistake).
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.
OBSERVATIONAL ASIDE (not required for my counterexample):
If the points are spaced evenly, then all the chords are parallel.
OBSERVATIONAL ASIDE (not required for my counterexample):
If the points are numbered sequentially, then every odd number must connect to an even number.
OBSERVATION 2:
If a set of points are contiguous on the circle, and if none of them
are connected to each other, then the set of points to which they
connect is also contiguous.
CONSTRUCTION OF COUNTEREXAMPLE:
Assign the numbers 1, 200, 199, 198,197,196, 2 to contiguous
points. There are 193 points left to place on the circle.
The numbers 3 to 45 are clearly not safe, in the sense that none of the
5 consecutive high numbers already placed can be connected to them
without having a difference that exceeds 150. Let's define these
43 numbers as "clearly unsafe". Let's define the 150 numbers from
46 to 195 as "safer". Note that there is less then 4 "safer"
numbers for every "clearly unsafe" number. Therefore. we can
assign the remaining points so that there are never 5 "safer" numbers
in a row.
(There are many ways to do this. One way is
to continue around the circle, assigning consecutive points with 4
"safer numbers", then 1 "clearly unsafe" number,then 4 "safer numbers",
1 "clearly unsafe" number, etc., until you run out of "safer
numbers". Fill in the remaining unassigned points with the
remaining "clearly unsafe" numbers.
For instance, one such arrangement would be:
1, 200, 199, 198,197,196, 2, 195, 194, 193, 192, 3, 191, 190,
189, 188, 4 ... , 39, 47, 46, and then the remaining "clearly unsafe"
40, 41, 42, 43, 44, 45. )
WHY THIS CONSTRUCTION FAILS:
a) If any of the highest 5 numbers is joined to another of the highest
5, then one of them will need to be joined to either the number 1 or
2. But this causes the difference to exceed 150.
b) If none
of the highest 5 is joined to another of the highest 5, then they must
be joined to 5 consecutive other points on the circle. But we
have assigned points so that any 5 consecutive other points will always
include at least one "clearly unsafe" number. This causes the
difference to exceed 150.
THEREFORE:
It is not
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.
Edited on November 13, 2005, 7:32 am
Solution? Spoiler?
