Three Cottages Problem
From Math Images
| Three Cottage Problem |
|---|
 |
Three Cottage Problem
- The three cottage problem is a problem in graph theory.
Contents |
Basic Description
We have three cottages, represented as rectangles, and three wells, represented as circles. Each cottage requires an individual road to every well, but bad blood between the cottage owners requires that no two roads intersect.The problem is simple; can the roads be drawn in such a way to meet these conditions?
Keep in mind that the cottages are a completely 2 dimensional plane; clever use of bridges or tunnels are not allowed. Likewise, a road cannot be built through a well or a house.
It is highly recommended that you attempt to work out this problem yourself before seeing the solution.
Solution
There is no solution to this problem; it is impossible.
A basic solution to this problem begins by drawing some initial lines.
We draw six lines connecting each house to two wells and each well to two houses.
Notice how we have created loops in the problem as shown by the yellow shades. At this point we need only three more lines to solve this problem.
Here we are confronted with a choice; whether to put each newly created line inside the loop or outside the loop. With three lines left to draw, at least two lines will be either inside or outside the loop.
We draw two more lines, one on the inside of the loop and one on the outside.
The last line (which in this case is blue) must go inside or outside the loop; but in both cases it will be forced to intersect a line.
Alternate Solution
In this proof we will use Euler's formula for planar graphs:
where V is the number of nodes, E is the number of edges, and F is the number of faces.
In any solution to the problem, V = 6 and E = 9. By simply substituting these values into Euler's formula, we get:
We now will proceed to examine the exact nature of these 5 faces more closely. We denote 
to be the number of faces bounded by i edges. 
is all faces bounded by one edge (in other words, the space bounded by an edge that begins and ends on one vertex).
(1) 
The fact that each edge is the boundary of two faces (one on the "inside" and one on the "outside") leads us to the following statement:
(2) 
Now we aim to simplify this equation by making a few key observations:
1. 
since there will never be a case of a road beginning and ending at a house.
2. 
because there will never be two roads that go from the same house to the same well.
3. 
since this would be a triangle. A triangle could only be formed with vertex combinations of house-house-well or well-well-house, which would mean roads connecting two houses or two roads together.
4. 
, for any odd i since we can extend our reasoning from 
.
We now apply these results to equation (2) to arrive at the following:
Remembering that E = 9, we get get
(3) 
But with equation (1) in mind, we know that to find the minimum of the right hand side of (3), we will maximize the value of
We do this by setting
and by substituting this into (3), we get our minimum value for 
By comparing this result to our earlier result in (3), we arrive at our contradiction:
Other Solutions
The problem can be solved if it takes place on a torus. While technically the problem is still on a two dimensional surface, the two dimensional surface exists in a three dimensional space.
Ideas for the Future
Some applet that allows the user to draw lines and draw out solutions. Something like what I want for the bridges of Konigsberg. I think both this page and the bridges of Konigsberg should not go public until they have such an applet.
Better pictures in general.
A interactive animation of the torus solution. The user should be able to rotate the torus to see how the lines are drawn.
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.
