| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2004 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Moderate -0.8 This is a standard textbook application of the Hungarian algorithm with clear instructions to reduce rows first. The method is algorithmic and routine for D2 students, requiring careful execution rather than problem-solving insight. The maximisation context requires converting to minimisation (subtracting from maximum), but this is a standard step taught explicitly in the specification. |
| Spec | 7.03c Working with algorithms: trace, interpret, adapt |
| Art | Literature | Music | Science | |
| Donna | 31 | 24 | 32 | 35 |
| Hannah | 16 | 10 | 19 | 22 |
| Kerwin | 19 | 14 | 20 | 21 |
| Thomas | 18 | 15 | 21 | 23 |
In a quiz there are four individual rounds, Art, Literature, Music and Science. A team consists of four people, Donna, Hannah, Kerwin and Thomas. Each of four rounds must be answered by a different team member. The table shows the number of points that each team member is likely to get on each individual round.
\begin{center}
\begin{tabular}{|l|c|c|c|c|}
\hline
& Art & Literature & Music & Science \\
\hline
Donna & 31 & 24 & 32 & 35 \\
\hline
Hannah & 16 & 10 & 19 & 22 \\
\hline
Kerwin & 19 & 14 & 20 & 21 \\
\hline
Thomas & 18 & 15 & 21 & 23 \\
\hline
\end{tabular}
\end{center}
Use the Hungarian algorithm, reducing rows first, to obtain an allocation which maximises the total points likely to be scored in the four rounds. You must make your method clear and show the table after each stage. [9]
(Total 9 marks)
\hfill \mbox{\textit{Edexcel D2 2004 Q2 [9]}}