| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Physical space modeling |
| Difficulty | Moderate -0.8 This is a straightforward application of wall-following algorithms in maze traversal. Parts (i) requires simple tracing of routes, (ii) asks for basic justification of a well-known result, and (iii-iv) involve minor modifications. The question requires spatial reasoning but no mathematical calculation, proof, or novel insight—it's primarily about understanding and applying a simple algorithmic rule. |
| Spec | 7.02r Graph modelling: model and solve problems using graphs |
| Answer | Marks |
|---|---|
| (i) [Diagrams of Janet's and John's routes shown with solid and dotted lines] | M1 A1 A1 |
| (ii) Yes. Janet's route traces west and south walls plus "attachments". John's route traces north and east walls plus "attachments". – or equivalent (Any "islands" are irrelevant.) | M1 A1 B1 |
| (iii) Yes | B1 |
| (iv) Yes. All avenues covered by forward and backward pass (i.e. by John's original route + Janet's route). | B1 |
| (i) [Diagrams of Janet's and John's routes shown with solid and dotted lines] | M1 A1 A1 | |
| (ii) Yes. Janet's route traces west and south walls plus "attachments". John's route traces north and east walls plus "attachments". – or equivalent (Any "islands" are irrelevant.) | M1 A1 B1 | |
| (iii) Yes | B1 | |
| (iv) Yes. All avenues covered by forward and backward pass (i.e. by John's original route + Janet's route). | B1 | |2 Answer this question on the insert provided.
A maze is constructed by building east/west and north/south walls so that there is a route from the entrance to the exit. The maze is shown in Fig. 2.1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-3_495_717_470_671}
\captionsetup{labelformat=empty}
\caption{Fig. 2.1}
\end{center}
\end{figure}
On entering the maze Janet says "I'm always going to keep a hand in contact with the wall on the right." John says "I'm always going to keep a hand in contact with the wall on the left."\\
(i) On the insert for this question show Janet's route through the maze.
On the insert show John's route.\\
(ii) Will these strategies always find a way through such mazes? Justify your answer.
In some mazes the objective is to get to a marked point before exiting. An example is shown in Fig. 2.2, where $\mathbf { X }$ is the marked point.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-3_497_716_1672_669}
\captionsetup{labelformat=empty}
\caption{Fig. 2.2}
\end{center}
\end{figure}
In the maze shown in Fig. 2.2 Janet's algorithm takes her to $\mathbf { X }$. John's algorithm does not take him to $\mathbf { X }$. John modifies his algorithm by saying that he will turn his back on the exit if he arrives there without visiting $\mathbf { X }$. He will then move onwards, continuing to keep a hand in contact with the wall on the left.\\
(iii) Will this modified algorithm take John to the point $\mathbf { X }$ in the maze in Fig. 2.2?\\
(iv) Will this modified algorithm take John to any marked point in the maze in Fig. 2.2? Justify your answer.
\hfill \mbox{\textit{OCR MEI D1 2005 Q2 [8]}}