Can You Prove It? Brain Teaser - 3 Houses & Utilities

[BigStelly]

Here is another brain Teaser...


in 2D not 3D assume crossing lines disrupts the electric field,

3 houses need to be hooked up to electrical, telephone and gas. Is it possible to hook every house up to every building without crossing lines?

I know this is impossible but can anyone prove it, id be interested to see how.

Yeah some teacher once actually told me that same thing a few years ago in high school and i didnt believe them after trying about 500 times to solve the darn thing.

 

[Galileo]

Euler proved a beautiful theorem for polyhedra with the following analogon for graphs (The problem is a graph problem. You have to find a planar graph (i.e. a graph that can be drawn on a flat plane without the lines intersecting).

If you have a planar graph with n>0 vertices, m lines (branches, edges) and r regions (including the outer region), then: n-m+r=2

You can use this to prove the problem has no solution.

I found a site about it:
http://mathforum.org/dr.math/faq/faq.3utilities.html

 

[tacman]

It is not possible to hook every house up to every building without crossing lines. This is because in order for each house to be connected to all three utilities (electric, telephone, and gas), there would have to be at least three lines running from each house to each building. This would result in a total of nine lines crossing over each other, which would disrupt the electric field and make it impossible for the utilities to function properly. This can be proven by drawing a diagram and trying to connect all three houses to all three buildings without any lines crossing. It simply cannot be done.