Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site alice.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!alice!td
From: td@alice.UUCP (Tom Duff)
Newsgroups: net.puzzle,net.math
Subject: Re: Another neat problem from Putnam Exam
Message-ID: <3055@alice.UUCP>
Date: Tue, 23-Oct-84 15:27:40 EDT
Article-I.D.: alice.3055
Posted: Tue Oct 23 15:27:40 1984
Date-Received: Wed, 24-Oct-84 04:02:32 EDT
References: <170@ihnet.UUCP>
Organization: AT&T Bell Laboratories, Murray Hill
Lines: 16

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.