Water, Gas, Electricity to Three Homes Puzzle

Date: 06/30/2002 at 01:15:50
From: Sam Brownfield
Subject: water gas electricity to 3 homes puzzle


This is a puzzle that I have tried over and over and over to try to 
get.  You have the three letters W G E  arranged in any position and
you also have 3 circles (homes) arranged in any position.  You have to
draw a line from each of the W G and E to each of the 3 circles
without crossing lines.  You can put the letter and shapes in any
shape or positions to do this.  I have always got to one line left
over and over and over.  I believe that this is an impossible one to
solve.  If you figure it out, can you tell me what order you put down
the lines since that's half of how you do the problem.   


                  0   W  0  G
                    E   0       (any position)  I HATE THIS PUZZLE!

Date: 06/30/2002 at 05:44:29
From: Doctor Anthony
Subject: Re: water gas electricity to 3 homes puzzle


We have 3 utilities A, B, C and 3 houses 1, 2, 3 as shown

     A    B    C

     1    2    3

and we must join each letter to each number without any of the lines 
crossing each other.

This problem comes under the heading of graph theory.

You have probably heard of Euler's formula for plane graphs.  If p = 
number of verticies, q = number of edges, r = number of regions then

   p - q + r = 2

A plane graph has none of its edges intersecting except at a vertex.

For example, in a square, you have p = 4, q = 4, r = 2 (one region 
inside the square, one region outside the square) and

       p - q + r = 4 - 4 + 2 = 2   as required.

The proof of Euler's formula is straightforward and can be found in 
any textbook on basic graph theory.  We now use it to show that it is 
impossible to join the three letters to the three numbers without any 
intersections of the edges.

We prove the result by contradiction.  Suppose that it is possible to 
draw the figure without any intersections of the edges.

We sum the number of edges lying on the boundary of each region over 
all r regions and denote this number by N.  Since no edges join 
letters to each other or numbers to each other, the graph contains no 
triangles, so it follows that N >= 4r  [To illustrate this, think 
again of a square.  The inner region has 4 edges on its boundary.  
The outer region has 4 edges on its boundary and so N = 8.  If we had 
a triangle then N would be 3+3 = 6 but as stated above there are NO 
TRIANGLES.]

On the other hand N counts each edge AT MOST twice (an edge can only 
have 1 or 2 regions on either side), so N <= 2q (= 2 x 9 = 18).

We had N >= 4r   so  4r <= N <= 18

                         r <= 9/2  (=4.5)   ......(1)

However by Euler's formula,  p - q + r = 2

                             6 - 9 + r = 2

                                     r = 5  ......(2)

Comparing (1) and (2) we see that there is a contradiction and our 
assumption that the figure is a plane graph is clearly impossible.

It follows that the letters and numbers cannot be joined without at 
least one intersection of two lines.


- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/