THE ANSWER TO THE IMPOSSIBLE PUZZLE – THE 3 UTILITIES / 6 DOT PROBLEM

How many times have you been challenged by someone to solve this puzzle? I remember myself as a kid spending hours and hours drawing lines and circles, trying to find a solution. The puzzle appears to be simple enough. You have to draw 3 houses on a piece of paper and below them you need to draw the three utilities: Water, Gas and Electricity. Each house must be connected to all three utilities. The owners of each of the houses do not like each other, therefore they don’t want their utilities lines to cross each other or pass through any of the other houses. You can simplify the puzzle by replacing each house and each utility with a dot. You must find a way to connect each of the top three dots to all three bottom dots, without any lines crossing each other and without going from house to house or utility to utility. The solution must be contained within the 2 dimensional space of the diagram on the paper.  

After multiple attempts you will have probably started thinking that if you follow all of its rules, this puzzle is simply impossible to solve on a flat piece of paper. If you thought that, then you are absolutely right. The answer of this puzzle is that it is mathematically impossible to solve and whoever ‘invented it’ just enjoyed watching and imagining people failing over and over again. In the remaining of this article I will try to explain to you why exactly the puzzle is impossible. There are some basic mathematic principles involved but once you understand them, it will be simple to impress your friends next time they try to challenge you with this puzzle. 

SOME BASIC PRINCIPLES

First of all we need to understand what this mathematical problem is about. The creator of the puzzle wants you to try and connect these 6 points in such way that you will be creating what is called a plane graph. But what exactly is a plane graph? Firstly let’s explain what the word graph means in Discrete Mathematics:  

•  A graph is a set of points which are interconnected by lines. The combination of points and lines can form different regions. Points are also called vertices, lines are called edges and regions are called faces. But for this article, let’s keep things simple. A graph can take many forms and consist of various point, line and region combinations. This is an example of a graph formed by 4 points and 4 lines:

R= region, L= line, P= point.  Everytime a closed (bounded) region - in this case R1 - is formed by a graph in the 2-D plane then automatically a surrounding (unbounded) region - R2 - is also formed.

Now that we know what a graph is, let’s define plane graphs. Simply explained, a plane graph is a graph that has been drawn in a single plane (two dimensional such as a piece of paper) without having any of its lines crossing each other. In the following picture we have 3 different graphs. 2 of them are K4 graphs. This means that they have 4 points shown by 4 red dots. The third one is a K5 graph (5 points). In the first K4 graph, the two insight lines cross each other (intersect). Therefore this graph is a non-plane graph. In the second K4 graph, one of the insight lines was moved to the outside. There is no intersection anymore and therefore our K4 graph is now a plane one. The 3rd graph is similar to the first, but a 5th point was added insight the box at the point of intersection of the two lines. This added point removed the intersection and changed the graph from a non-plane K4 to a plane K5 one. 

Now try to remember again what the puzzle is asking from us. We need to draw lines from the three houses (3 points) in such way that each house is joined to each of the three utilities (3 more points). This would result to the creation of a graph. The basic rule is that none of the lines should intersect. In simple mathematical words, the puzzle is asking us to create a plane graph. To get into more details, it is asking us to create a very specific type of graph where every point of the top layer of points (the three houses) is connected to every point of the bottom layer of points (the three utilities). This graph is called in mathematics a ‘complete bipartite graph’.  The mathematical question therefore that needs to be answered here is the following: 

Can the requested graph (a complete bipartite graph) be a plane graph?  

If the answer was yes, then this puzzle would have a solution which most of you I am sure would have already found. But the answer is NO, the requested graph can NEVER be a plane graph. There will always be a line intersection and therefore this puzzle is impossible to answer.  

THE PROOF

Before I give you the proof, I will have to torture you with one last piece of mathematics. This is called the Euler’s Characteristic or the Euler’s Formula of Planar Graphs. It is a simple mathematical formula which is valid for every single plane graph. If a graph doesn’t follow this formula, then it cannot be a plane one. It simply states that for every plane graph, the number of regions minus the number of lines plus the number of points will ALWAYS be equal to 2. Here it is in a picture to help you remember it better:  

Now let’s see some more examples so I can convince you that this formula is indeed true for all plane graphs:

Now let’s try to figure out if Euler’s formula would apply to the puzzle’s requested graph. We already know, that our puzzle has 6 points (3 houses and 3 Utilities). We know that each house has to connect to all 3 utilities. This means that we will need 9 lines. Now let’s put these numbers into the formula:      

What the calculation above tells us, is that if our graph can be plane (no intersections) then it will need to have 5 REGIONS. Since a line is not allowed to move from house to house or utility to utility, then the simplest way to create a closed region, will be by using at least 4 LINES.     

Therefore, if each of the 5 regions we need in order for the puzzle graph to be plane needs to have at least 4 lines, then we will need a minimum of 20 lines. This number of lines counts each line TWICE as each line will serve as a boundary for two regions. Therefore 20 / 2 = 10. A hypothetical solution for a plane graph to exist will require AT LEAST 10 lines. But we already know that the rules of our puzzle allow for only 9 lines.  Therefore this means that the puzzle graph can NEVER be plane. A solution on the 2D piece of paper is therefore IMPOSSIBLE.  

(GIF source)

What could we need for a possible solution? First of all we would need to break the rules and use a different kind of shape. For example we could use a 3 dimensional figure such as a torus, which basically has the shape of a doughnut. 

(Image 1, Image 2)

I hope I didn’t bore you too much with the math...but now you know the answer to one of the world’s greatest mysteries 

INFO ABOUT IMAGES: UNLESS OTHERWISE STATED, ALL IMAGES HAVE BEEN DESIGNED BY ME EXCEPT THE FIRST IMAGE WHICH WAS TAKEN FROM A FREE SOURCE WEBSITE

 -CT.  

============================================================================

For more of my articles, follow me @nulliusinverba