Utilities puzzle
KIM asks:
IF YOU HAVE 3 HOUSES AND EACH NEED TO HAVE ELECTRIC, WATER AND GAS CONNECTED, IS IT POSSIBLE TO DO SO WITHOUT CROSSING ANY LINES?
Answer: Given the wording of your question, yes. One way is to simply run the water lines underneath the houses, like so:
Clearly, at no point do any of the utility lines cross any of the others. You could get the same result by running the electric lines over the houses. Obviously, in the three-dimensional real world, “crossing lines” is not generally a difficult problem: just move one of the lines up or down.
I suspect, however, that you were trying to ask a classic mathematical puzzle, which is stated more precisely as: “Suppose there are three houses on a plane and each needs to be connected to the gas, water, and electric companies, also on the same plane. Is there a way to connect them without any of the lines crossing each other, without using the third dimension, and without allowing the lines to go through the houses?”
Note the difference in the wording, which eliminates my solution above. The part about everything being on the same plane is surprisingly important: if the houses and utilities are arranged on, say, a doughnut-shaped object like a torus, then the puzzle is solvable even with the other restrictions.
If we restrict ourselves to the flat, paper-and-pencil world (or, for that matter, an electronic circuit board, where trying to connect different areas of the board without crossing lines is a common design problem), then no, the puzzle has no solution. This fact was proven in 1930 by Polish mathematician Kazimierz Kuratowski. Stated formally, the complete bipartite graph K3,3 is nonplanar.
For more information, Wikipedia has a good entry on the topic. Thanks for your question!