Three Cottages Problem

Three Cottage Problem
Field: Other
Image Created By: Unknown

Three Cottage Problem

The three cottage problem is a problem in graph theory.

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

[show more][hide]

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.

For another solution that is less intuitive, see the following.

Alternate Solution

[show more][hide]

In this proof we will use Euler's formula for planar graphs:

$F - E + V = 2 \,$

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:

$F - 9 + 6 = 2\,$

$F = 5\,$

We now will proceed to examine the exact nature of these 5 faces more closely. We denote $F_i\,$ to be the number of faces bounded by i edges. $F_1\,$ is all faces bounded by one edge (in other words, the space bounded by an edge that begins and ends on one vertex).

(1) $F = 5 = F_1 + F_2 + F_3 + F_4 + ...\,$

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) $2E = F_1 + 2F_2 + 3F_3 + 4F_4 + ...\,$

Now we aim to simplify this equation by making a few key observations:

1. $F_1 = 0 \,$since there will never be a case of a road beginning and ending at a house.

2. $F_2 = 0 \,$because there will never be two roads that go from the same house to the same well.

3. $F_3 = 0 \,$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. $F_i = 0 \,$, for any odd i since we can extend our reasoning from $F_3 = 0$.

We now apply these results to equation (2) to arrive at the following:

$2E = 2F_2 + 4F_4 + 6F_6 + ...\,$

Remembering that E = 9, we get get

(3) $18 = 4F_4 + 6F_6 + 8F_8 \,$

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

$F = 5 = F_4\,$

and by substituting this into (3), we get our minimum value for $4F_4 + 6F_6 + 8F_8,$

$4F_4 + 6F_6 + 8F_8 > 20\,$

By comparing this result to our earlier result in (3), we arrive at our contradiction:

$18 = 4F_4 + 6F_6 + 8F_8 > 20\,$

$18 > 20\,$

Thus a solution to the three cottage problem is not possible.

Interactive Flash App

Draw lines from the houses to the wells and see for yourself how this problem works:

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

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.

Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.

---

If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.