Follow us on Facebook

The Water-Gas-and-Electricity

The Water-Gas-and-Electricity Puzzle by Gianni A. Sarcone

Solutions for your logic and mechanical puzzles
water gas puzzleshoked face"Dear Archimedes Lab, if you have 3 houses and each need to have water, gas and electricity connected, is it possible to do so without crossing any lines? Can you please post the solution? Thank you very much!" -- Gerald
Category: Topological graph theory.
Name: Water Gas and Electricity puzzle, Three Utilities puzzle, or Three Cottage problem.
Material: Pencil, piece of paper.
Configuration: There are three houses (or squares) drawn on paper and below them three smaller squares representing gas, water, and electricity suppliers.
Aim of the game: Draw lines to get each utility into every house, without crossing over any line.
Origin of the puzzle: Unknown. Sam Loyd claimed that he invented this recreational math problem about 1903. But this puzzle is MUCH older than electric lighting or even gas, Loyd most probably modified a previously existing puzzle.
Editor's notice: This is a pure abstract mathematical puzzle that imposes constraints that would not be issues in a practical engineering scenario... As such, this puzzle CANNOT be solved.

Water, Optical fiber, Light - a connection dilemma
Each year, we receive an extraordinary number of letters regarding a classic route problem called “Water, Gas and Electricity”. Since the puzzle is very famous, we have chosen to present it in a new light. Ok... We have laid on water, internet connection and electricity from the utility suppliers W, O, L to each of the 3 houses A, B and C without any pipe crossing another (see fig. below). Take a pencil and check if the work has been done properly!

Water, Optical fiber and light puzzle
arrow See the solution
Simple explanation
Why is it impossible to solve this puzzle in 2 dimensions? Have a look at the diagram in fig. a below and you will understand that 3 connections starting from 2 utility suppliers will inevitably ENCLOSE one of the houses preventing it from being connected to at least one utility supplier (according to Jordan's curve theorem, a loop or a closed curve will have an inside and an outside no matter how we stretch or curve our lines, as long as they don't cross).

solution a
Alternative solution 1
Nevertheless, this puzzle is possible to solve by using subterfuge... The only way this can be done without the lines crossing is by allowing one of the lines (it doesn't matter which one) to enter a house or a utility company and then emerge from the building on the other side. In fact, the wording of the puzzle is a bit imprecise and doesn't forbid lines to go through the houses or to use the third dimension!
Alternative solution 2
Here is another neat way to solve it: reproduce the puzzle on a paper sheet, then roll it up to form a cylinder and add a paper strip to it as shown in fig. b. The final image c shows how the puzzle should appear and how the houses A, B and C are finally connected to the utility suppliers.

solution 3
Alternative solution 3
There is another neat and elegant way to topologically solve the puzzle! To get a hint or to suggest a solution, please, contact us. But if you are impatient visit our FB page to see the solution and click like if you liked it!

brain and gearsMaths behind the puzzle: Graph theory and examples
A planar graph is a collection of points connected by lines, that can be drawn on the plane in such a way that its lines (called edges) intersect only at their vertices (endpoints). In other words, a planar graph, unlike the other complete graphs, can be represented with no intersecting edges. For instance, the graph in the example below with 4 vertices (K4) is planar because if we move the vertex 4 through and beyond the triangle 123, we can see that there are no more edge intersections.

graph 1
'The Water Gas and Electricity problem' actually asks whether the complete graph K3,3 with two sets of points, each point of which connecting three points of the other set, is planar. If we perform the same transformation to this graph, we notice that there are always at least two edges that intersect, as shown in the fig. e.
graph 2
Euler characteristic
Math enthusiasts can use the simple Euler graph formula V - E + F = 2 (where V = number of Vertices, E = number of Edges, and F = number of Faces) to discuss and prove that this puzzle is unsolvable...
In our puzzle, the houses and utility suppliers together represent the Vertices, and the Faces are the areas inside a closed loop of Edges (this formula counts the area outside the graph as one of the Faces). Important: there can't be any Vertices in the middle of a Face.

graph 3If we connect the utility suppliers to the houses we obtain then 3 x 3 = 9 Edges (see graph K3,3 above), because each of the 3 utility suppliers is connected to 3 houses. We know that the boundary of every Face is a closed loop of Edges, and we know that every Edge goes between a house and a utility supplier (there is no reason to go from a house to a utility and back to the same house). That means the boundary of a Face is made by at least 4 Edges (see fig. f opposite).
Now let’s use Euler’s formula to figure out how many faces there are in the puzzle:
    V - E + F = 2
    F = 2 + E - V
    F = 2 + 9 - 6
    F = 5 faces
Every Face has at least 4 Edges, so the number of Edges in all the Faces is at least 4 x 5 = 20 Edges. This counts each Edge twice, as every Edge is a boundary for 2 Faces. So, the smallest number of Edges is 20 / 2 = 10 Edges. We know, however, that there are only 9 Edges! This is a contradiction... Since nothing can have 9 edges and 10 edges at the same time, drawing a solution to the three utilities puzzle must be impossible.
Share on Google Plus

About Naresh Sahu

This is a short description in the author block about the author. You edit it by entering text in the "Biographical Info" field in the user admin panel.
    Blogger Comment
    Facebook Comment


Post a Comment

Blog Archive