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?
Yes it is possible.
A comment that was brought up while this problem was in the queue was
that 150 seemed a pretty arbitrary number. In fact, I believe
this number is not arbitrary, but dependant on the proof, i.e., it may
not be the smallest this number can be, but, may be the easiest to
provide a proof for...
I originally began thinking that the first step was to see if the
mathematics ensured or prohibited a solution - checking the total
number of ways that 200 points could be connected and comparing to the
total number of ways that 200 numbers could be arranged. Well,
both these numbers are much too large for me, so eventually I had to
come up with a different method.
On to the meat of it...
Consider the numbers from 51-150. These numbers can be paired
with any other number without violation. Beginning with the
arbitrary arrangement of nodes, begin by marking each location with one
of these values. Note that there will be an equal number of
marked and unmarked nodes.
What my solution does is recursively reduce the problem to a simpler
version until the trivial case is presented. Begin by connecting
any unlike adjacent pair of points. As the line created does not
prohibit any future moves, the scenario is basically left unchanged -
it can either still be solved or it still can't be solved. Based
on the 1:1 ratio of marked to unmarked points, and because the
arrangement is circular, you are guaranteed to have at least one such
set of two points. Once this (and for efficientcy sake, all other
possible) connection(s) has been made, consider the section of the
circle they take up to be empty. I can't really think of a
clearer way to say this, so I'll give an example.
In a circle of ten, arranged numerically, say that you could connect 3
with 4. Once this is done, if exeactly one of 2 and 5 are marked,
they should be considered adjacent (as all points between them are
connected, and joining them would not create intersection) and could be
connected in a following step.
Each time a pair of points is connected, the problem simplifies, but
the 1:1 ratio of marked to unmarked point remains, by extension, the
necessity for at least one marked point to be "adjacent" to an unmarked
point remains, and the process can be re-applied until the trivial case
where the last two points are joined.
Further, I believe that the number 150 in the problem statement is
directly based on a similar proof to this, as the range which I have
chosen to mark is not maximum (to me, I still see 2 points of freedom,
namely #50 and #151) - that is, I do not prove with this method that
the maximum minimum difference possible is 150, simply that the maximum
minimum difference is at least 150.
Now, all rigor aside, I believe that I have presented a "method" rather
than a proof (e.g., I didnt prove that at least one connection is
always possible), however, in one out of one trials, the method worke
perfectly :)
99% solution
