Problem A and Solution

Finding Treasure

You have been invited to an old house with six rooms, one of which contains a treasure. A floor plan of the house is shown below. Each room is labelled with a letter. Some rooms are connected by doors, which are locked. Each door is labelled with the symbol of the key that will unlock it.

You start in Room A and want to get to the treasure in Room F. What is the fewest number of keys you need to get to the treasure? What are the symbols on those keys?

**Not printing this page?** You can use our interactive
worksheet.

One way to solve this problem would be to list all the different paths that you can take from Room A to Room F, and record the keys required to open the doors along the way. Note that there would be no reason to return to a room that you have already visited on a particular path. Then you can compare the paths to see which one requires the least number of keys.

One way to organize this information is using a tree diagram. Since we start in Room A, Room A appears at the top of the tree (first level). Since Room A is connected by a door only to Room B, we draw a single line from A to B (in the second level of the tree). Since the door between Room A and Room B requires a diamond key, we label the line connecting A and B with a diamond. We next consider the different possible doors out of Room B and build the rest of the tree in a similar way.

The complete tree diagram is shown below.

Using this tree diagram we can see the keys required for each path. For example, the path A \(\rightarrow\) B \(\rightarrow\) C \(\rightarrow\) D \(\rightarrow\) F requires three different keys: diamond, circle, and star.

However, the path A \(\rightarrow\) B \(\rightarrow\) E \(\rightarrow\) C \(\rightarrow\) D \(\rightarrow\) F requires only two keys: diamond and star.

This path is shown on the map.

When we check the other three paths in the tree, they all require three different keys, so this path requires the least number of keys.

We also note that to leave Room A we require a diamond key, and to
leave Room B we require a different key. We can conclude that we require
*at least* two keys to get from Room A to Room F. Since we found
a path that requires exactly two keys, this is the least number of keys
required.

Therefore, the fewest number of keys required to get to the treasure is two. The symbols on the keys are the diamond and the star.

**Teacher’s Notes**

When looking at solving real-world problems, the first step is often
to create a mathematical model of the situation. We sometimes refer to
this process as *abstraction*.

One form of abstraction is called a graph. A graph is a mathematical
model that uses circles we call *nodes* or *vertices* to
represent objects, and lines we call *edges* to represent links
between the objects. The edges between nodes may have labels on them to
indicate how the nodes are linked logically. The edges may also have
arrows indicating that a link between nodes has a specific direction.
Edges with arrows indicate this is a *directed* graph.

We can use a graph to represent many different real-world systems. For example we could represent cities on a map as nodes and the roads between them as edges. Another example is to represent webpages on the internet as nodes, and the links you click to get from one page to another as edges.

The key to abstraction is to keep the important information and
ignore the irrelevant details. We could represent the information in
this problem with a graph. The nodes could represent the rooms, and the
edges could represent the doors connecting the rooms. Each edge would be
labelled with the symbol for the key required to unlock the door. Since
you can move in either direction through a door from one room to
another, we would use an *undirected* graph. Here is a graph
representing the information in this problem.

The graph has all the information we need to find paths from Room A to Room F and the keys necessary to get from one room to another.