2 The following table shows the scores of five people, Alice, Baji, Cath, Dip and Ede, after playing five different computer games.
| Alice | Baji | Cath | Dip | Ede |
| Game 1 | 17 | 16 | 19 | 17 | 20 |
| Game 2 | 20 | 13 | 15 | 16 | 18 |
| Game 3 | 16 | 17 | 15 | 18 | 13 |
| Game 4 | 13 | 14 | 18 | 15 | 17 |
| Game 5 | 15 | 16 | 20 | 16 | 15 |
Each of the five games is to be assigned to one of the five people so that the total score is maximised. No person can be assigned to more than one game.
- Explain why the Hungarian algorithm may be used if each number, \(x\), in the table is replaced by \(20 - x\).
- Form a new table by subtracting each number in the table above from 20, and hence show that, by reducing columns first and then rows, the resulting table of values is as below.
| 3 | 1 | 1 | 1 | 0 |
| 0 | 4 | 5 | 2 | 2 |
| 4 | 0 | 5 | 0 | 7 |
| 5 | 1 | 0 | 1 | 1 |
| 5 | 1 | 0 | 2 | 5 |
- Show that the zeros in the table in part (b) can be covered with one horizontal and three vertical lines. Hence use the Hungarian algorithm to reduce the table to a form where five lines are needed to cover the zeros.
- Hence find the possible allocations of games to the five people so that the total score is maximised.
- State the value of the maximum total score.