wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Three houses with Gas, Electrical, and Water
        
(Message started by: Lightboxes on Aug 7^th, 2003, 2:53pm)

Title: Three houses with Gas, Electrical, and Water
Post by Lightboxes on Aug 7^th, 2003, 2:53pm

There are three houses.
They all need Gas, Electrical, and Water.
Connect them with continous lines; however, the lines can not intersect (overlap) each other.

1 2 3

G E W

If you can do it (mathematically or not), explain.
If you can't do it (mathematically or not), explain.

Title: Re: Three houses with Gas, Electrical, and Water
Post by Sir Col on Aug 7^th, 2003, 4:18pm

::[hide]
The easiest way to explain why this CANNOT be done is as follows...

WLOG, rearrange the diagram:

2 3

G E W

1

Now imagine houses 1 and 2 being fully connected (with G, E, and W).
By doing this we create two closed regions: 2E1G and 2E1W.
If 3 is not placed inside one of these regions it has no access to E (due to the external boundary: 2W1G).
If 3 is placed inside one of these regions it has no access to G or W, depending which region you place it in.

Hence, there is no planar solution.
[/hide]::

Title: Re: Three houses with Gas, Electrical, and Water
Post by Icarus on Aug 7^th, 2003, 5:52pm

The standard solution to this is to route one of the utilities from its plant to its house either through one of the other houses or one of the other plants.



    __________
   /   ______ \
  /   /   [hide].[/hide]  \ \
 1    |2     3  |
 |\   ||\\   /| |
 | \  || |\  || |
 |  \ || | \ || |
 |   \\| |  \\|/
 A    B  |    C
 |\_____/     |
  \__________/

3 routes to A by passing through C.

Title: Re: Three houses with Gas, Electrical, and Water
Post by wowbagger on Aug 8^th, 2003, 3:50am

I'd say the standard solution is the one on a toroid. I'll spare you the gruesome ASCII art.
As Sir Col demonstrated, there is no solution in a plane (apart from Icarus's tunnelling). However, there was no restriction to a plane.

Title: Re: Three houses with Gas, Electrical, and Water
Post by Sir Col on Aug 8^th, 2003, 4:19am

Okay, using the surface of a torus:

http://mathforum.org/dr.math/faq/images/utilities_torus.gif

Title: Re: Three houses with Gas, Electrical, and Water
Post by James Fingas on Aug 8^th, 2003, 6:23am

If the houses are in Bermuda, you can run the gas and electricity to all three houses, run the water to two houses, and then set up a hose (not passing over either a gas nor an electric line) that spouts water onto the third house's roof!

Title: Re: Three houses with Gas, Electrical, and Water
Post by James Fingas on Aug 8^th, 2003, 6:28am

Actually, if I were going to do this in real life, I'd probably do the following:

___A___ ___B___ ___C___ | | | | | | Gas ------------------------------------- Water ----------------------------------- Electricity ----------------------------- |_____| |_____| |_____|

Title: Re: Three houses with Gas, Electrical, and Water
Post by Kitty on Aug 10^th, 2003, 12:35pm

[hide]The anwser i know is that the houses are the sources.[/hide]

Title: Re: Three houses with Gas, Electrical, and Water
Post by william wu on Sep 15^th, 2003, 3:09am

Graph Theory proof using Euler's Formula:
::
[hide]
Make a graph out of the scenario. Utilities and houses become vertices, and supply lines become edges.

After making the necessary supply line connections, we want to know if the resultant graph can be planar. A planar graph is a graph where no two edges cross each other.

Euler's formula: For planar graphs, F - E + V = 2, where F = number of faces, E = number of edges, V = number of vertices. A face is simply a region enclosed by a loop of edges, which does not itself contain a face. The void which surrounds the whole graph also counts as a face, for it is enclosed in some sense by the graph's outermost edges. (Sidenote: 17 (!) different proofs of this formula can be found http://www.ics.uci.edu/~eppstein/junkyard/euler/)

So if the graph is planar, Euler's formula should hold. We plug in V = 6 and E = 3[times]3 = 9. Then F = 2 - 6 + 9 = 5.

Now note that in our graph, a face can have either four or six edges. The 6 edge face will look like a bear claw with 3 fingers, and the 4 edge face will look like a bear claw with 2 fingers. This is due to the restraints of the problem (e.g. supply lines between utilties are not allowed).

Knowing this, we can lower bound the number of edges in our graph:

E[ge](F*4)/2 = (5*4)/2 = 10

The divide by 2 comes from the fact that every edge is a boundary for two faces, so we would be double-counting every edge if we did not divide by 2.

However, we know that the number of edges must be 9, since 3[times]3 = 9. So we have a contradiction with our lower bound. Thus the graph cannot be planar, and a supply line routing with no intersections is impossible.
[/hide]

Edit: 9:02 AM 9/16/2003 Changed [le] to [ge].

Title: Re: Three houses with Gas, Electrical, and Water
Post by wowbagger on Sep 16^th, 2003, 4:53am

Somehow I can't follow your train of thought, William.

I admit that I haven't bothered to visualise these bear claws, but I don't see a contradiction between your lower bound of E<=10 and the value 9 for three houses with three edges each. ???

Perhaps one should look at the (possible vs. target) number of faces?

Title: Re: Three houses with Gas, Electrical, and Water
Post by william wu on Sep 16^th, 2003, 9:04am

Sorry, there was a typo: the [le] should have been a [ge]. So E [ge] 10. I used the right word ("lower bound") but the wrong symbol. The proof by contradiction should follow through now.

Title: Re: Three houses with Gas, Electrical, and Water
Post by william wu on Sep 16^th, 2003, 9:19am

Drew some bear claws in xfig -- I should call them upside-down bear claws if the row of utilities is placed above the row of houses: