Question B1:

We briefly discussed “The Tower of Hanoi Puzzle” (see Example 2 of section 8.1) when discussing linear recurrences. Here we consider a graph whose vertices are all the possible configurations of discs in the 3-disc version of the puzzle. Two vertices are adjacent if and only if it is possible to move one disc according to the rules and get from one configuration to the other.

(a) We noted that the puzzle can be solved in 7 moves. This corresponds to the shortest path

from vertex 12 to vertex 21. How long is the shortest path that does not use the edge between

vertex 15 and vertex 27?

(b) Find a Hamilton Circuit that starts and ends at vertex 1.

Answer 9b1

(a) The shortest path from $12$ to $21$ does not use the edge between $15$ and $27$ and has a length of $11:$

$$ 12\rarr 11\rarr 16\rarr 18\rarr 6\rarr 4\rarr 8\rarr 9\rarr 24\rarr 23\rarr 19\rarr 21 $$

(b) A Hamilton Circuit that starts and ends at vertex $1$:

$$ 1\rarr 3\rarr 2\rarr\\ 7\rarr 8\rarr 9\rarr \\ 24\rarr 22\rarr 23\rarr \\19\rarr 21\rarr 20\rarr \\25\rarr 26\rarr 27\rarr\\ 15\rarr 13\rarr 14\rarr \\10\rarr 12\rarr 11\rarr \\16\rarr 17\rarr 18\rarr \\6\rarr 4\rarr 5\rarr 1 $$

Question B2:

Several classical logic puzzles become routine exercises once translated into the language of graph theory. One particular kind of puzzle, sometimes called a “tricky crossing” involves attempting to transport people or goods across a river by boat.

In this particular puzzle, three music critics and three guitarists need to cross from the left side of a stream in a rowboat to get to a music festival on the right side.

• All six people and the boat begin on the left of the river.
• The boat can only hold at most two people at a time.
• The boat can only cross if it is not empty.
• If music critics every outnumber guitarists on either side of the river, they will team up to break all of the guitars on that side of the river, since they have vowed to bring about a world in which all music is played on tubas.

The graph on the right shows how the possible configurations of this puzzle are related. We use the notation $L(ab|cd)$ to label a situation where there are a guitarists and b critics on the left of the river with the boat, and c guitarists and d critics on the right of the river. Similarly $R(ab|cd)$ describes the same situation, except with the boat on the right side of the river. An edge connects two vertices if a single crossing of the river can transform one situation into the other.

(a) Show that this graph is bipartite, by finding a bipartition of the vertices.

(b) Solve the puzzle by finding a path from $L(33|00)$ to $R(00|33)$.

(c) Is it possible to find a matching consisting of 8 edges in this graph? Either find such a matching, or adapt Hall’s Marriage Theorem to show that it is impossible to do so.