Most Wanted Puzzle Solutions

"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

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!

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).

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.

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!

Maths 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 (K₄) 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.

'The Water Gas and Electricity problem' actually asks whether the complete graph K_3,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.

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.

If we connect the utility suppliers to the houses we obtain then 3 x 3 = 9 Edges (see graph K_3,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.

All the Most Wanted Puzzle Solutions in a look!