Three cottage problem
From Wikipedia, the free encyclopedia
The classical mathematical puzzle known as water, gas, and electricity, the (three) utilities problem, or sometimes the three cottage problem, can be stated as follows:
- Suppose there are three cottages on a plane (or sphere) and each needs to be connected to the gas, water, and electric companies. Using a third dimension or going through a company or cottage are illegal. Is there a way to do so without any of the lines crossing each other?
[edit] Solution
-
-
Thomsen graph, Utility graph, K3,3
n = 6, m = 9
-
The problem is part of the mathematical field of topological graph theory which studies the embedding of graphs on surfaces. In more formal graph-theoretic terms, the problem asks whether the complete bipartite graph K3,3 is planar. Kazimierz Kuratowski proved in 1930 that K3,3 is nonplanar, and thus that the three cottage problem has no solution.
But K3,3 is toroidal, that is it can be embedded on the torus. In terms of the three cottage problem this means the problem can be solved by punching a hole through the plane (or the sphere). This changes the topological properties of the surface and using the hole we can connect the three cottages without crossing lines.
It is not possible to redraw these without edge intersections. Repeated attempts should convince you that this is plausible. To prove this mathematically requires knowledge of topology. The three cottage problem is a simplified version of a problem that electronic circuit board designers face. When all of the connections on a circuit board are limited to one side of a board. then all nonplanar electronic circuits are impossible. If you are allowed to use a third dimension by using wires or connecting to the second side of the board, all electronic circuit paths are possible.
