Water, Gas, Electricity to Three Homes PuzzleDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/