display | more...
Answer to old chestnut: more graph problems:

The problem posed is unsolvable.

To see why it's unsolvable, count the number of ways in and out of each of the "rooms" (including the outside):

  | 1 | 2 | 3 |
  |  4  |  5  |

There are four ways in/out of rooms 1 and 3, but there are five ways in and out of rooms 2, 4, and 5, and nine ways between the outside and various rooms.

Now, in any continuous path you draw, you enter/exit each room an even number of times, with the possible exception of the starting and ending rooms, which you will enter/exit an odd number of times as long as they are not the same room.

Since there four rooms with an odd number of entrances/exits, you cannot make a single complete path using all of them exactly once each; such a path would need to have four ends, but by definition it only has two.

This principle can be applied in general to problems of this sort. For each "node" (place where paths end/meet), count the number of paths in and out of the node. If all nodes have an even number of paths, then it is possible to construct a path which starts and ends in the same place. If two nodes have an odd number of paths, it is possible to construct a path starting and ending in those nodes. If more than two nodes have an odd number of paths, the construction is impossible.

Log in or register to write something here or to contact authors.