2021 Paper 2, Q6
A tow truck company has three tow trucks (A, B and C) and receives calls from three motorists (P, Q and R), who have broken down.
The network shows the distances in kilometres (km) from each of the tow trucks to each of the motorists, where \(x\) represents the distance between Tow Truck C and Motorist P.
The minimum total distance travelled by the three tow trucks in order for each tow truck to visit exactly one motorist is 32 km.
Use the Hungarian algorithm to determine the distance between Tow Truck C and Motorist P.
Find the allocation first, then the number
You are given the answer to a Hungarian problem and asked for a missing distance. Run the algorithm with \(x\) still in the matrix. The \(x\) terms cancel inside each row, so the algorithm still tells you which trucks go where.
Algebra inside a matrix
Put the trucks down the side and the motorists across the top. Read each entry carefully off the network, because a diagram that is not to scale makes it easy to swap two.
In every row, the P column is the smallest, because it has the smallest constant with a single \(x\). Subtracting it removes the \(x\) from the R column and leaves \(x\) only in the Q column.
The total is only useful once you know which three distances it is made of. Then it is a linear equation in \(x\).
Does the best allocation depend on the distance?
Slide the distance from C to P. Every allocation uses one entry from each column, so every total is \(4x\) plus a constant. The same allocation wins every time, and only its total changes.
| P | Q | R | |
|---|---|---|---|
After both reductions, two lines cover every zero. What next?
Two lines for a 3 × 3 matrix means there is no full allocation on zeros yet. You would end up giving two trucks the same motorist.
Yes. The smallest uncovered entry is 1. Subtract it from every uncovered entry and add it where the two lines cross. Then three lines are needed, and you can allocate.
Every row already contains a zero, so another row reduction changes nothing. The next move in the algorithm is the adjustment step.
QCAA marking guide · 7 marks
\[\begin{array}{c|ccc}&P&Q&R\\\hline A&x+6&2x+3&x+7\\B&x+3&2x+4&x+5\\C&x&2x+1&x+3\end{array}\]
Marker: correctly converts the network information into matrix form. This mark may be implied by later working.
\[R_1-(x+6),\ R_2-(x+3),\ R_3-x:\qquad\begin{bmatrix}0&x-3&1\\0&x+1&2\\0&x+1&3\end{bmatrix}\]
Marker: determines each matrix element by reducing each row. Follow-through marks are allowed from here on.
\[C_2-(x-3),\ C_3-1:\qquad\begin{bmatrix}0&0&0\\0&4&1\\0&4&2\end{bmatrix}\]
Marker: determines each matrix element by reducing each column. Column reduction before row reduction is accepted. Every \(x\) has now gone.
Two lines (row A and column P) cover all the zeros, so adjust with the smallest uncovered entry, 1. Add 1 where the lines cross and subtract 1 from every uncovered entry.
\[\begin{bmatrix}1&0&0\\0&3&0\\0&3&1\end{bmatrix}\]
Marker: correctly applies the Hungarian algorithm. Three lines are now needed.
C has only one zero, in column P, so C goes to P. Then A’s remaining zeros are in Q and R, and B’s are in R. B goes to R, so A goes to Q.
\[\text{A}\to\text{Q},\quad\text{B}\to\text{R},\quad\text{C}\to\text{P}\]
Marker: determines the minimum allocation. The guide shows it as a bipartite graph.
\[(2x+3)+(x+5)+x=32\]\[4x+8=32\quad\Rightarrow\quad x=6\]
It is 6 km from Tow Truck C to Motorist P.
Marker: determines \(x\).
Label each reduction, draw the covering lines on your matrices, and say how many lines you needed at each stage.
Marker: shows logical organisation, communicating key steps, such as connecting statements and lines to cover the zeros.
Check it with numbers
With \(x=6\), A to Q is 15 km, B to R is 11 km and C to P is 6 km. That adds to 32, and the next best allocation is 33, so 32 really is the minimum.
"Use the Hungarian algorithm" means five of the seven marks are for the algorithm. Listing all six totals in terms of \(x\) finds the same answer, but it earns far fewer marks.
The Hungarian algorithm normally takes numbers in and gives a minimum out. Here the minimum is given and one of the inputs is missing. That means running the algorithm on algebraic entries, which most people have never tried, and trusting that the \(x\) terms will cancel. They do, because every row has a single \(x\) in two columns and \(2x\) in the third. Once the allocation is known, the given total turns into an ordinary equation.
Question wording and marking-guide steps are from the 2021 QCAA General Mathematics external assessment, © State of Queensland (QCAA) 2021, licensed under CC BY 4.0, and have been adapted. Tangent Tuition is not affiliated with the QCAA.
Spot a mistake on this page? Report it