| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2012 |
| Session | January |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Moderate -0.3 This is a standard Hungarian algorithm application with clear tabular data and routine steps. While it requires multiple iterations and careful bookkeeping, the method is algorithmic and well-practiced in D2. The maximisation variant and interpretation of multiple solutions adds slight complexity, but this remains a typical textbook exercise requiring procedural execution rather than problem-solving insight. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Pearl necklace | Ruby ring | Sapphire bracelet | |
| Butler | 80 | 100 | 20 |
| Cook | 40 | 35 | 60 |
| Gardener | 60 | 45 | 30 |
| Handyman | 20 | 100 | 80 |
3 The famous fictional detective Agatha Parrot has been called in to investigate the theft of some jewels. Each thief is known to have taken just one item of jewellery.
Agatha has invented a scoring system based on motive, opportunity and past experience. The table shows the score for each of four suspects with each of three items of jewellery. The higher the score the more likely the suspect is to have stolen that item of jewellery.
Suspect
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
& Pearl necklace & Ruby ring & Sapphire bracelet \\
\hline
Butler & 80 & 100 & 20 \\
\hline
Cook & 40 & 35 & 60 \\
\hline
Gardener & 60 & 45 & 30 \\
\hline
Handyman & 20 & 100 & 80 \\
\hline
\end{tabular}
\end{center}
(i) Assuming that three of these four suspects are the thieves, find who is most likely to have stolen each item of jewellery for the total score to be maximised. State how each table of working was calculated. Write down the two possible solutions for who should be suspected of stealing each item of jewellery and who should be thought to be innocent.
Further evidence shows that the butler stole the sapphire bracelet.\\
(ii) Using this additional information, find out which suspect should be thought to be innocent. Explain your reasoning.
\hfill \mbox{\textit{OCR D2 2012 Q3 [11]}}