\(\mathbf { 5 }\) & 15 & 23 & 43 & 16 & 30
\hline \end{tabular} \end{center} (ii) Perform the fourth iteration. There are no changes on the fifth iteration, so your answer to part (ii) should give the complete network of shortest distances.
(iii) Use your matrices to find the shortest distance and route from vertex \(\mathbf { 3 }\) to vertex \(\mathbf { 1 }\), and explain how you do it.
(iv) Draw the complete network of shortest distances, not including the loops.
(v) Apply the nearest neighbour algorithm to your network in part (iv), starting at vertex 2. Give the length of the Hamilton cycle that is produced. Interpret the Hamilton cycle in terms of the original diagram and state what the algorithm has achieved. OCR is committed to seeking permission to reproduce all third-party content that it uses in its assessment materials. OCR has attempted to identify and contact all copyright holders whose work is used in this paper. To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced in the OCR Copyright Acknowledgements Booklet. This is produced for each series of examinations, is given to all schools that receive assessment material and is freely available to download from our public website (\href{http://www.ocr.org.uk}{www.ocr.org.uk}) after the live examination series.
If OCR has unwittingly failed to correctly acknowledge or clear any third-party content in this assessment material, OCR will be happy to correct its mistake at the earliest possible opportunity.
For queries or further information please contact the Copyright Team, First Floor, 9 Hills Road, Cambridge CB2 1PB.
OCR is part of the Cambridge Assessment Group; Cambridge Assessment is the brand name of University of Cambridge Local Examinations Syndicate (UCLES), which is itself a department of the University of Cambridge. \section*{ADVANCED GCE
MATHEMATICS (MEI)} Decision Mathematics 2 \section*{Candidates answer on the Answer Booklet} \section*{OCR Supplied Materials:}

• 8 page Answer Booklet
• MEI Examination Formulae and Tables (MF2)
• Graph paper

\section*{Other Materials Required:}

• Scientific or graphical calculator

\section*{Tuesday 22 June 2010 Afternoon} Duration: 1 hour 30 minutes \(\| \| \| \| \| \| \| \| \| \| \| \| \|\)

• Write your name clearly in capital letters, your Centre Number and Candidate Number in the spaces provided on the Answer Booklet.
• Use black ink. Pencil may be used for graphs and diagrams only.
• Read each question carefully and make sure that you know what you have to do before starting your answer.
• Answer all the questions.
• Do not write in the bar codes.
• You are permitted to use a graphical calculator in this paper.
• Final answers should be given to a degree of accuracy appropriate to the context.

• The number of marks is given in brackets [ ] at the end of each question or part question.
• You are advised that an answer may receive no marks unless you show sufficient detail of the working to indicate that a correct method is being used.
• The total number of marks for this paper is \(\mathbf { 7 2 }\).
• This document consists of \(\mathbf { 8 }\) pages. Any blank pages are indicated.

1

1. Mickey ate the last of the cheese. Minnie was put out at this. Mickey's defence was "There wasn't enough left not to eat it all". Let "c" represent "there is enough cheese for two" and "e" represent "one person can eat all of the cheese".
   1. Which of the following best captures Mickey's argument? $$\mathrm { c } \Rightarrow \mathrm { e } \quad \mathrm { c } \Rightarrow \sim \mathrm { e } \quad \sim _ { \mathrm { c } } \Rightarrow \mathrm { e } \quad \sim \mathrm { c } \Rightarrow \sim \mathrm { e }$$ In the ensuing argument Minnie concedes that if there's a lot left then one should not eat it all, but argues that this is not an excuse for Mickey having eaten it all when there was not a lot left.
   2. Prove that Minnie is right by writing down a line of a truth table which shows that $$( c \Rightarrow \sim e ) \Leftrightarrow ( \sim c \Rightarrow e )$$ is false.
      (You may produce the whole table if you wish, but you need to indicate a specific line of the table.)
2. 1. Show that the following combinatorial circuit is modelling an implication statement. Say what that statement is, and prove that the circuit and the statement are equivalent.
      \includegraphics[max width=\textwidth, alt={}, center]{83d00f1f-25e5-4a26-bac5-dc2baf965438-23_188_533_1272_767}
   2. Express the following combinatorial circuit as an equivalent implication statement.
      \includegraphics[max width=\textwidth, alt={}, center]{83d00f1f-25e5-4a26-bac5-dc2baf965438-23_314_835_1599_616}
   3. Explain why \(( \sim \mathrm { p } \wedge \sim \mathrm { q } ) \Rightarrow \mathrm { r }\), together with \(\sim \mathrm { r }\) and \(\sim \mathrm { q }\), give p . 2 The network is a representation of a show garden. The weights on the arcs give the times in minutes to walk between the six features represented by the vertices, where paths exist.
      \includegraphics[max width=\textwidth, alt={}, center]{83d00f1f-25e5-4a26-bac5-dc2baf965438-24_483_985_342_539}
   4. Why might it be that the time taken to walk from vertex \(\mathbf { 2 }\) to vertex \(\mathbf { 3 }\) via vertex \(\mathbf { 4 }\) is less than the time taken by the direct route, i.e. the route from \(\mathbf { 2 }\) to \(\mathbf { 3 }\) which does not pass through any other vertices? The matrices shown below are the results of the first iteration of Floyd's algorithm when applied to the network. \begin{center} \begin{tabular}{ | c | c | c | c | c | c | c | } \cline { 2 - 7 } \multicolumn{1}{c|}{} & \(\mathbf { 1 }\) & \(\mathbf { 2 }\) & \(\mathbf { 3 }\) & \(\mathbf { 4 }\) & \(\mathbf { 5 }\) & \(\mathbf { 6 }\)
      \hline \(\mathbf { 1 }\) & \(\infty\) & 15 & \(\infty\) & \(\infty\) & 7 & 8
      \hline \(\mathbf { 2 }\) & 15 & 30 & 6 & 2 & 6 & 23
      \hline \(\mathbf { 3 }\) & \(\infty\) & 6 & \(\infty\) & 3 & \(\infty\) & \(\infty\)
      \hline \(\mathbf { 4 }\) & \(\infty\) & 2 & 3 & \(\infty\) & 10 & 17
      \hline \(\mathbf { 5 }\) & 7 & 6 & \(\infty\) & 10 & 14 & 8
      \hline