Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/5/84; site rochester.UUCP
Path: utzoo!linus!philabs!cmcl2!seismo!rochester!nemo
From: nemo@rochester.UUCP (Wolfe)
Newsgroups: net.puzzle,net.math
Subject: Re: Re: Another neat problem from Putnam Exam
Message-ID: <2544@rochester.UUCP>
Date: Thu, 25-Oct-84 09:13:44 EDT
Article-I.D.: rocheste.2544
Posted: Thu Oct 25 09:13:44 1984
Date-Received: Sat, 27-Oct-84 06:05:48 EDT
References: <170@ihnet.UUCP> <3055@alice.UUCP>
Organization: U. of Rochester, CS Dept.
Lines: 37

> The problem is:
> 	Given two sets each of n points in the plane, no 3 collinear,
> prove that each point in one
> set can be paired with a point in the other set such that none of the resulting
> line segments intersect.  Consider the following algorithm:
> 
> 	pick a pairing arbitrarily
> 	while there exist two intersecting lines AB and CD
> 		replace AB and CD by AD and CB
> 
> Clearly, if this algorithm terminates it finds the required pairing.  To prove
> termination we need only note that there is a finite number (factorial(n), actually)
> of possible pairings, and look at the sum of the lengths of the lines in each
> pairing.  Each iteration of the loop decreases the sum (that's where you
> need the triangle inequality.)  Since there are only a finite number of different
> lengths, the loop must eventually terminate.

The algorithm does *NOT* necessarily terminate.  There are configurations and
pairings which cycle (left to the reader ...).  A proof that there is a
solution is as follows.
First, define the *length of a pairing* on a set of points as the sum of the
lengths of the segments connecting the pairs.
Then define a *minimal pairing* as one whose length is less than or equall
to any other pairing on the points (satisfying the problem's constraints).
Now, note that 
	1) there are (as you note) only a finite number of pairings
	2) therefore there exist minimal pairings in the set of possible
		pairings
	3) No minimal pairing can have intersecting segments (by the triangle
		inequality, since as you note above, replacing intersecting
		segments (A1, B1) and (A2, B2) which intersected at point C
		by (A1, B2) and (A2, B1) in effect replaces segments (A1, C)
		and (C, B2) by (A1, B2), and segments (A2, C) and (C, B1) by
		(A2, B1), which reduces the sum of the lengths).
	4) Hence, any minimal pairing will be a solution.
How to get a minimal pairing is another problem.
Nemo