| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2010 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for minimisation |
| Difficulty | Moderate -0.5 This is a standard Hungarian algorithm application with clear step-by-step instructions. The question guides students through row reduction, column reduction, line covering, and augmentation—all routine procedures for D2. While it requires careful arithmetic and following the algorithm systematically, it demands no problem-solving insight or novel thinking, making it easier than average A-level maths questions overall. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Game 1 | Game 2 | Game 3 | Game 4 | Game 5 | |
| Ali | 5 | 7 | 3 | 8 | 8 |
| Beth | 8 | 6 | 4 | 8 | 7 |
| Cat | 6 | 1 | 2 | 10 | 3 |
| Di | 4 | 4 | 3 | 10 | 7 |
| Ell | 4 | 6 | 4 | 7 | 9 |
| 2 | 4 | 0 | 2 | 3 |
| 4 | 2 | 0 | 1 | 1 |
| 5 | 0 | 1 | \(k\) | 0 |
| 1 | 1 | 0 | 4 | 2 |
| 0 | 2 | 0 | 0 | 3 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Row reduction: subtract row minima (3,4,1,3,4) from each row | M1 | |
| Column reduction applied after row reduction | M1 | |
| \(k = 9\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Three lines identified covering all zeros | B1 | |
| Minimum uncovered element identified and augmentation performed correctly | M1 | |
| Resulting table shown with zeros requiring five lines to cover | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Allocation 1: Ali–G3, Beth–G2, Cat–G5, Di–G1, Ell–G4 | B1 | |
| Allocation 2: Ali–G3, Beth–G2, Cat–G5, Di–G4, Ell–G1 | B1 | |
| Both allocations stated | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Minimum total penalty points = 22 | B1 |
# Question 2:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Row reduction: subtract row minima (3,4,1,3,4) from each row | M1 | |
| Column reduction applied after row reduction | M1 | |
| $k = 9$ | A1 | |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Three lines identified covering all zeros | B1 | |
| Minimum uncovered element identified and augmentation performed correctly | M1 | |
| Resulting table shown with zeros requiring five lines to cover | A1 | |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Allocation 1: Ali–G3, Beth–G2, Cat–G5, Di–G1, Ell–G4 | B1 | |
| Allocation 2: Ali–G3, Beth–G2, Cat–G5, Di–G4, Ell–G1 | B1 | |
| Both allocations stated | B1 | |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Minimum total penalty points = 22 | B1 | |
---2 Five students attempted five different games, and penalty points were given for any mistakes that they made. The table shows the penalty points incurred by the students.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& Game 1 & Game 2 & Game 3 & Game 4 & Game 5 \\
\hline
Ali & 5 & 7 & 3 & 8 & 8 \\
\hline
Beth & 8 & 6 & 4 & 8 & 7 \\
\hline
Cat & 6 & 1 & 2 & 10 & 3 \\
\hline
Di & 4 & 4 & 3 & 10 & 7 \\
\hline
Ell & 4 & 6 & 4 & 7 & 9 \\
\hline
\end{tabular}
\end{center}
Using the Hungarian algorithm, each of the five students is to be allocated to a different game so that the total number of penalty points is minimised.
\begin{enumerate}[label=(\alph*)]
\item By reducing the rows first and then the columns, show that the new table of values is
\begin{center}
\begin{tabular}{ | l | l | l | l | l | }
\hline
2 & 4 & 0 & 2 & 3 \\
\hline
4 & 2 & 0 & 1 & 1 \\
\hline
5 & 0 & 1 & $k$ & 0 \\
\hline
1 & 1 & 0 & 4 & 2 \\
\hline
0 & 2 & 0 & 0 & 3 \\
\hline
\end{tabular}
\end{center}
and state the value of the constant $k$.
\item Show that the zeros in the table in part (a) can be covered with three lines, and use augmentation to produce a table where five lines are required to cover the zeros.
\item Hence find the possible ways of allocating the five students to the five games with the minimum total of penalty points.
\item Find the minimum possible total of penalty points.
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-05_2484_1709_223_153}
\end{center}
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2010 Q2 [10]}}