Author |
Topic: Three houses with Gas, Electrical, and Water (Read 4898 times) |
|
Lightboxes
Full Member
Gender: 
Posts: 203
|
 |
Three houses with Gas, Electrical, and Water
« on: Aug 7th, 2003, 2:53pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
A job is not worth doing unless it's worth doing well.
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Three houses with Gas, Electrical, and Water
« Reply #1 on: Aug 7th, 2003, 4:18pm » |
Quote Modify
|
::
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.
::
|
| « Last Edit: Aug 7th, 2003, 4:20pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Three houses with Gas, Electrical, and Water
« Reply #2 on: Aug 7th, 2003, 5:52pm » |
Quote Modify
|
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.
__________
/ ______ \
/ / . \ \
1 |2 3 |
|\ ||\\ /| |
| \ || |\ || |
| \ || | \ || |
| \\| | \\|/
A B | C
|\_____/ |
\__________/
3 routes to A by passing through C.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: Three houses with Gas, Electrical, and Water
« Reply #3 on: Aug 8th, 2003, 3:50am » |
Quote Modify
|
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.
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Three houses with Gas, Electrical, and Water
« Reply #4 on: Aug 8th, 2003, 4:19am » |
Quote Modify
|
Okay, using the surface of a torus:
|
| « Last Edit: Aug 8th, 2003, 4:20am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Three houses with Gas, Electrical, and Water
« Reply #5 on: Aug 8th, 2003, 6:23am » |
Quote Modify
|
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!
|
| « Last Edit: Aug 8th, 2003, 6:29am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Three houses with Gas, Electrical, and Water
« Reply #6 on: Aug 8th, 2003, 6:28am » |
Quote Modify
|
Actually, if I were going to do this in real life, I'd probably do the following:
___A___ ___B___ ___C___
| | | | | |
Gas -------------------------------------
Water -----------------------------------
Electricity -----------------------------
|_____| |_____| |_____|
|
| « Last Edit: Aug 8th, 2003, 6:29am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Kitty
Full Member
Gender: 
Posts: 287
|
|
Re: Three houses with Gas, Electrical, and Water
« Reply #7 on: Aug 10th, 2003, 12:35pm » |
Quote Modify
|
The anwser i know is that the houses are the sources.
|
|
IP Logged |
If the human brain was simple enough for us to understand, we would still be so stupid that we couldn't understand it.~Kant (1724-1804)
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Three houses with Gas, Electrical, and Water
« Reply #8 on: Sep 15th, 2003, 3:09am » |
Quote Modify
|
Graph Theory proof using Euler's Formula:
::
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.
Edit: 9:02 AM 9/16/2003 Changed [le] to [ge].
|
| « Last Edit: Sep 16th, 2003, 9:03am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: Three houses with Gas, Electrical, and Water
« Reply #9 on: Sep 16th, 2003, 4:53am » |
Quote Modify
|
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?
|
| « Last Edit: Sep 16th, 2003, 4:54am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Three houses with Gas, Electrical, and Water
« Reply #10 on: Sep 16th, 2003, 9:04am » |
Quote Modify
|
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.
|
| « Last Edit: Sep 19th, 2003, 8:59pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
3utilities_claws.png