| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 683.1 | | BEING::POSTPISCHIL | Always mount a scratch monkey. | Wed Mar 25 1987 12:28 | 6 |
| Re .0:
What is are N sections?
-- edp
|
| 683.2 | rephrasing -- looks interesting! | CLT::GILBERT | eager like a child | Wed Mar 25 1987 23:20 | 6 |
| N black points and N white points are placed on plane,
in such a way that no 3 points are colinear.
Prove that there is a way to form N black-white pairs
of points, such that none of the N line segments that
connect the pairs of points intersect.
|
| 683.3 | It's easy! | TAV02::NITSAN | Duvdevani, DEC Israel | Thu Apr 09 1987 09:07 | 5 |
| Hint follows:
Form randomly N black-white pairs of points
and connect them with N line segments.
Now, sum all the lengths of all the segments..
|
| 683.4 | | CLT::GILBERT | eager like a child | Thu Apr 09 1987 17:34 | 12 |
| Here's one approach, but there are some good loose ends.
Randomly form N segments connecting black-white pairs of points.
Now, if none of the segments intersect, we are done.
If some intersect, then replace the two segments with the 'other'
pair of segments connecting the black and white points. We assert
*without proof* that these two segments won't intersect, and that
the sum of thir lengths is shorter than the original two segments.
So whenever we have an intersection, we can decrease the total length
of the segments, and since we keep decreasing the total length of the
segments, we must eventually terminate.
|
| 683.5 | enjoying .3 and .4 | VINO::JMUNZER | | Thu Apr 09 1987 20:23 | 24 |
| Suppose AB and CD intersect (at O):
C
/
A---------------------O---------------B
/
/
/
/
D
Then (1) AC & BD don't intersect, because (a) triangles AOC and BOD are
disjoint, except for point O; and (b) AC & BD are in those triangles,
and don't include point O. (The triangles are nontrivial because
no three points are colinear.)
(2) |AC| + |BD| < |AB| + |CD|
because
|AC| < |AO| + |OC| and |BD| < |BO| + |OD| implies that
|AC| + |BD| < |AO| + |OC| + |BO| + |OD|
= |AO| + |OB| + |CO| + |OD|
= |AB| + |CD|
John
|
| 683.6 | Another Solution? | TAV02::NITSAN | Duvdevani, DEC Israel | Thu Apr 23 1987 11:16 | 19 |
| There's also a different way to prove the original statement. Construct the
convex hull (sp?) of the 2N points. Now distinguish between two cases:
[1] If it has points of both colors on it, then there is a black-white pair
of neighbors (on the convex hull). Connect them and continue recursively.
[2] If all points (on the convex hull) are of the same colors (say, black),
then construct two parallel lines on two "edges" of the convex hull, such
that they are not parallel to any other segment (posiible because no three
points are colinear). The variable:
# white points to right of line - # black points to right of line
changes continuously from 1 to -1 while moving from the left line to the
right line, so there must be a line in the middle that splits the set of
2N points into two sets where the # blacks = # whites in each, and then
continue recursively.
Nitsan.
|