AS June 2024 Q2

EdexcelCurrent spec8 marksAllocation

2. A team of 5 players, A, B, C, D and E, competes in a quiz. Each player must answer one of 5 rounds, P, Q, R, S and T.

Each player must be assigned to exactly one round, and each round must be answered by exactly one player.

Player B cannot answer round Q, player D cannot answer round T, and player E cannot answer round R.

The number of points that each player is expected to earn in each round is shown in the table.

The team wants to maximise its total expected score.

The Hungarian algorithm is to be used to find the maximum total expected score that can be earned by the 5 players.

(a) Explain how the table should be modified. (2)

(b)

(i) Reducing rows first, use the Hungarian algorithm to obtain an allocation which maximises the total expected score.

(ii) Calculate the maximum total expected score. (6)

Mark scheme (a)

Scheme	Marks	AO
Subtract each entry from a constant (e.g. 50) to convert from maximisation problem to minimisation	B1	1.1b
Add a large value (e.g. 100) to cells BQ, DT and ER so that they cannot be selected	B1	2.4
	(2)

B1: Valid statement regarding converting a maximisation problem to a minimisation problem

B1: Explain the need to add a large value to avoid cells being selected – it must be clear which order the changes are applied