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.
There are six rooms labelled A, B, C, D, E and F. There are seven doors connecting the rooms. Three of the doors are labelled with a diamond symbol, two are labelled with a star, one with a circle, and one with a triangle. The doors are placed as follows:
A door with a diamond connects Room A to Room B.
A door with a circle connects Room B to Room C.
A door with a star connects Room B to Room E.
A door with a star connects Room C to Room D.
A door with a diamond connects Room C to Room E.
A door with a diamond connects Room D to Room F.
A door with a triangle connects Room E to Room F.
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.
There are four different paths from A to F shown in the tree diagram.
The first path goes from A to B to C to E to F and passes through the symbols diamond, circle, diamond, triangle.
The second path goes from A to B to C to D to F and passes through the symbols diamond, circle, star, diamond.
The third path goes from A to B to E to F and passes through the symbols diamond, star, triangle.
The fourth path goes from A to B to E to C to D to F and passes through the symbols diamond, star, diamond, star, diamond.
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.
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.