| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2011 |
| Session | January |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for minimisation |
| Difficulty | Moderate -0.5 This is a straightforward application of the Hungarian algorithm with clear instructions (reduce rows first, assign £25 to diagonal). The algorithm is mechanical once learned, requiring no problem-solving insight. However, it involves multiple careful steps (row reduction, column reduction, covering zeros, adjustments) which elevates it slightly above pure recall, placing it just below average difficulty. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| To | |||||
| \cline { 2 - 6 } | Amir | Bex | Cerys | Duncan | |
| \multirow{4}{*}{From} | Amir | - | 15 | 21 | 19 |
| \cline { 2 - 6 } | Bex | 20 | - | 16 | 14 |
| \cline { 2 - 6 } | Cerys | 25 | 12 | - | 16 |
| \cline { 2 - 6 } | Duncan | 24 | 10 | 18 | - |
| \cline { 2 - 6 } | |||||
| \cline { 2 - 6 } | |||||
| Answer | Marks | Guidance |
|---|---|---|
| Reduce rows; resulting matrix: A: 10,0,6,4 / B: 6,11,2,0 / C: 13,0,13,4 / D: 14,0,8,15 | M1, A1 | Reduce rows; correct row reduced matrix (cao) |
| Reduce columns; resulting matrix: A: 4,0,4,4 / B: 0,11,0,0 / C: 7,0,11,4 / D: 8,0,6,15 | M1, A1 | Reduce columns; their correct column reduced matrix (ft) |
| Cross through zeros using minimum number of lines; augment by 4 giving: A: 0,0,0,0 / B: 0,15,0,0 / C: 3,0,7,0 / D: 4,0,2,11 | M1, A1 | Cross through zeros (may be implied) and augment efficiently; correct augmented matrix (cao) |
| Cannot match A to A; complete matching: Amir chose Cerys, Bex chose Amir, Cerys chose Duncan, Duncan chose Bex | B1 | This matching (cao) |
# Question 2:
| Reduce rows; resulting matrix: A: 10,0,6,4 / B: 6,11,2,0 / C: 13,0,13,4 / D: 14,0,8,15 | M1, A1 | Reduce rows; correct row reduced matrix (cao) |
| Reduce columns; resulting matrix: A: 4,0,4,4 / B: 0,11,0,0 / C: 7,0,11,4 / D: 8,0,6,15 | M1, A1 | Reduce columns; their correct column reduced matrix (ft) |
| Cross through zeros using minimum number of lines; augment by 4 giving: A: 0,0,0,0 / B: 0,15,0,0 / C: 3,0,7,0 / D: 4,0,2,11 | M1, A1 | Cross through zeros (may be implied) and augment efficiently; correct augmented matrix (cao) |
| Cannot match A to A; complete matching: Amir chose Cerys, Bex chose Amir, Cerys chose Duncan, Duncan chose Bex | B1 | This matching (cao) |
---2 Amir, Bex, Cerys and Duncan all have birthdays in January. To save money they have decided that they will each buy a present for just one of the others, so that each person buys one present and receives one present. Four slips of paper with their names on are put into a hat and each person chooses one of them. They do not tell the others whose name they have chosen and, fortunately, nobody chooses their own name.
The table shows the cost, in $\pounds$, of the present that each person would buy for each of the others.
\begin{center}
\begin{tabular}{ l | l | c | c | c | c | }
\multicolumn{2}{c}{} & To & & & \\
\cline { 2 - 6 }
& & Amir & Bex & Cerys & Duncan \\
\hline
\multirow{4}{*}{From} & Amir & - & 15 & 21 & 19 \\
\cline { 2 - 6 }
& Bex & 20 & - & 16 & 14 \\
\cline { 2 - 6 }
& Cerys & 25 & 12 & - & 16 \\
\cline { 2 - 6 }
& Duncan & 24 & 10 & 18 & - \\
\cline { 2 - 6 }
& & & & & \\
\cline { 2 - 6 }
\end{tabular}
\end{center}
As it happens, the names are chosen in such a way that the total cost of the presents is minimised.\\
Assign the cost $\pounds 25$ to each of the missing entries in the table and then apply the Hungarian algorithm, reducing rows first, to find which name each person chose.
\hfill \mbox{\textit{OCR D2 2011 Q2 [7]}}