3 Agatha Parrot is in her garden and overhears her neighbours talking about four new people who have moved into her village. Each of the new people has a different job, and Agatha's neighbours are guessing who has which job.
Using the information she has overheard, Agatha counts how many times she heard it guessed that each person has each job.
| Nurse | Police officer | Radiographer | Teacher |
| Jill Jenkins | 7 | 8 | 8 | 8 |
| Kevin Keast | 8 | 4 | 5 | 7 |
| Liz Lomax | 5 | 1 | 0 | 4 |
| Mike Mitchell | 8 | 3 | 4 | 4 |
Agatha wants to find the allocation of people to jobs that maximises the total number of correct guesses. She intends to use the Hungarian algorithm to do this. She starts by subtracting each value in the table from 10.
- Write down the table which Agatha gets after she has subtracted each value from 10. Explain why she did a subtraction.
- Apply the Hungarian algorithm, reducing rows first, to find which job Agatha concludes each person has. State how each table of working was calculated from the previous one.
Agatha later meets Liz Lomax and is surprised to find out that she is the radiographer.
- Using this additional information, but without formally using the Hungarian algorithm, find which job Agatha should now conclude each person has. Explain how you know that there is no better solution in which Liz is the radiographer.