(This is not "my" solution. I think I read a solution to this problem
or one very like it many years ago - no idea where. I'm not a graph
theory guy, so I'm pretty sure I didn't come up with it entirely on
my own.)
Definition of problem:
We are given that there are 3 utilities and 3 houses which are laid out
something like the following:
X X X
0 0 0
Where the utilities are represented by 0s in this problem and the
houses are represented by Xs.
For the sake of argument, we can say that the utilities are water,
electricity, and telephone. We are asked to draw lines connecting
each utility to each house without having any line overlap any other
line. We are asked to do this without tricks and without going out
of the plane of the sheet of paper on which the objects are drawn.
The solution is that the problem is unsolvable. Here is the reasoning.
We will divide and conquer to develop our solution. We note that in
order to connect 3 houses to 3 utilities, that we must first connect
1 house to one utility. This, we can do easy enough:
0----X (Diagram 1)
We note that we might have drawn this as
0 0 X 0
| or \ or \ /\/ (Diagrams 2, 3, and 4)
| \ \/
X X
and that all of these different solutions to the smaller problem
are in some sense identical. That is, no matter how complicated we
make the drawing, there really does only seem to be only one real
solution to the problem of connecting one house to one utility.
Convince yourself of this before proceeding. (If you go on w/o
convincing yourself of this, you are wasting your time.)
Now, let's add one more utility and one more house to the problem.
We find a solution is:
X------0
| |
| A | B (Diagram 5)
| |
0------X
Again, we note that there is really only ONE solution to this
problem. (Convince yourself of this.) We can draw the lines
however we wish, but there really, in some strange sense, is
only one solution. You will note that we have cut the plane
into two parts now. We have created a polygon that has an
inside which we denote as 'A' and an outside which we denote 'B'.
Now, we add one more utility and we note that there seems, at
first, to be two solutions. We can add the utility to Diagram
5 either on the inside or the outside, giving us either Diagram
6 or Diagram 7, respectively.
0
_____/ \
/ |
X------0 X------0 |
|\ B | C | | B| C
| 0 | | A | /
| A \ | | |/
0------X 0------X
(Diagram 6) (Diagram 7)
We note, however, that, in some sense, both of THESE solutions
to 3 utilities and 2 houses is identical, because each of them
divides the plane of solution (the piece of paper) into the 3
regions: A, B, and C! If we look really hard, we can SEE that
they are really the same!
So now comes the moment of Truth! We've solved the problem of
3 utilities and 2 houses, and what's more is we kinda suspect that
there really is only ONE solution to this problem, which can be
drawn (for example) as either diagram 6 or diagram 7. But we
need to add one more house, to solve the original problem of
connecting 3 houses and 3 utilities. But where do we add it?
If we put it into region A, then we can't reach the utility between
region's B and C! If we put it into region B, then we can't reach
the utility between A and C! And if we put it into region C we can't
reach the utility between A and B! And so, the problem appears to
be unsolvable (without going outside of the plane -- without drawing
off the paper).
One problem remains. We may not feel comfortable drawing these lines
all over the place, when the original problem put the houses in one
line and the utilities in another. One way to think about it is this:
In our solution we allowed ourselves to put the houses wherever we
needed to put them in order to solve the problem. If we can't solve
the problem if we allow ourselves to put things wherever we want, then
we certainly can't solve it in any particular configuration!
(I've heard that this proof is very similar to the proof of what is
called "The Four Color Problem" in topology, which is apparently still
known as "The Five Color Problem" to some cartographers.)