Questions - OCR - A-Level Maths

OCR D1 2016 June Q2

9 marks Moderate -0.8

2 Shaun measured the mass, in kg, of each of 9 filled bags. He then used an algorithm to sort the masses into increasing order. Shaun's list after the first pass through the sorting algorithm is given below. $$\begin{array} { l l l l l l l l l } 32 & 41 & 22 & 37 & 53 & 43 & 29 & 15 & 26 \end{array}$$

Explain how you know that Shaun did not use bubble sort. In fact, Shaun used shuttle sort, starting at the left-hand end of the list.
Write down the two possibilities for the original list.
Write down the list after the second pass through the shuttle sort algorithm.
How many passes through shuttle sort were needed to sort the entire list? Shaun's sorted list is given below. $$\begin{array} { l l l l l l l l l } 15 & 22 & 26 & 29 & 32 & 37 & 41 & 43 & 53 \end{array}$$ Shaun wants to pack the bags into bins, each of which can hold a maximum of 100 kg .
Write the list in decreasing order of mass and then apply the first-fit decreasing method to decide how to pack the bags into bins. Write the weights of the bags in each bin in the order that they are put into the bin.
Find a way to pack all the bags using only 3 bins, each of which can hold a maximum of 100 kg .

OCR D1 2016 June Q3

11 marks Moderate -0.8

3 A problem to maximise $P$ as a function of $x , y$ and $z$ is represented by the initial Simplex tableau below.

$P$	$x$	$y$	$z$	$s$	$t$	RHS
1	- 10	2	3	0	0	0
0	5	0	- 5	1	0	60
0	4	3	0	0	1	100

Write down $P$ as a function of $x , y$ and $z$.
Write down the constraints as inequalities involving $x , y$ and $z$.
Carry out one iteration of the Simplex algorithm. After a second iteration of the Simplex algorithm the tableau is as given below.
$P$ $x$ $y$ $z$ $s$ $t$ RHS
1 0 7.25 0 0.6 1.75 211
0 1 0.75 0 0 0.25 25
0 0 0.75 1 - 0.2 0.25 13
Explain how you know that the optimal solution has been achieved.
Write down the values of $x , y$ and $z$ that maximise $P$. Write down the optimal value of $P$.

OCR D1 2016 June Q4

11 marks Standard +0.3

4 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected. Molly says that she has drawn a graph with exactly five vertices, having vertex orders 1, 2, 3, 4 and 5.

State how you know that Molly is wrong. Holly has drawn a connected graph with exactly six vertices, having vertex orders 2, 2, 2, 2, 4 and 6.
(a) Explain how you know that Holly's graph is not simply connected.
(b) Determine whether Holly's graph is Eulerian, semi-Eulerian or neither, explaining how you know which of these it is. Olly has drawn a simply connected graph with exactly six vertices.
(a) State the minimum possible value of the sum of the vertex orders in Olly's graph.
(b) If Olly's graph is also Eulerian, what numerical values can the vertex orders take? Polly has drawn a simply connected Eulerian graph with exactly six vertices and exactly ten arcs.
(a) What can you deduce about the vertex orders in Polly's graph?
(b) Draw a graph that fits the description of Polly's graph.

OCR D1 2016 June Q5

12 marks Standard +0.3

5 The network below represents a single-track railway system. The vertices represent stations, the arcs represent railway tracks and the weights show distances in km. The total length of the arcs shown is 60 km . \includegraphics[max width=\textwidth, alt={}, center]{d783915d-5950-4a97-b6a0-70959214e218-5_442_1152_429_459}

Apply Dijkstra's algorithm to the network, starting at $G$, to find the shortest distance (in km ) from $G$ to $N$ and write down the route of this shortest path. Greg wants to travel from the station represented by vertex $G$ to the station represented by vertex $N$. He especially wants to include the track $K L$ (in either direction) in his journey.
Show how to use your working from part (i) to find the shortest journey that Greg can make that fulfils his requirements. Write down his route. Percy Li needs to check each track to see if any maintenance is required. He wants to start and end at the station represented by vertex $G$ and travel in one continuous route that passes along each track at least once. The direction of travel along the tracks does not matter.
Apply the route inspection algorithm, showing your working, to find the minimum distance that Percy will need to travel. Write down those arcs that Percy will need to repeat. If he travels this minimum distance, how many times will Percy travel through the station represented by vertex $L$ ?

OCR D1 2016 June Q6

12 marks Moderate -0.5

6 William is making the bridesmaid dresses and pageboy outfits for his sister's wedding. He expects it to take 20 hours to make each bridesmaid dress and 15 hours to make each pageboy outfit. Each bridesmaid dress uses 8 metres of fabric. Each pageboy outfit uses 3 metres of fabric. The fabric costs $\pounds 8$ per metre. Additional items cost $\pounds 35$ for each bridesmaid dress and $\pounds 80$ for each pageboy outfit. William's sister wants to have at least one bridesmaid and at least one pageboy. William has 100 hours available and must not spend more than $\pounds 600$ in total on materials. Let $x$ denote the number of bridesmaids and $y$ denote the number of pageboys.

Show why the constraint $4 x + 3 y \leqslant 20$ is needed and write down three more constraints on the values of $x$ and $y$, other than that they must be integers.
Plot the feasible region where all four constraints are satisfied. William's sister wants to maximise the total number of attendants (bridesmaids and pageboys) at her wedding.
Use your graph to find the maximum number of attendants.
William costs his time at $\pounds 15$ an hour. Find, and simplify, an expression, in terms of $x$ and $y$, for the total cost (for all materials and William's time). Hence find, and interpret, the minimum cost solution to part (iii).

OCR D1 2016 June Q7

12 marks Moderate -0.5

7 A tour guide wants to find a route around eight places of interest: Queen Elizabeth Olympic Park ( $Q$ ), Royal Albert Hall ( $R$ ), Statue of Eros ( $S$ ), Tower Bridge ( $T$ ), Westminster Abbey ( $W$ ), St Paul's Cathedral ( $X$ ), York House ( $Y$ ) and Museum of Zoology ( $Z$ ). The table below shows the travel times, in minutes, from each of the eight places to each of the other places.

	$Q$	$R$	S	$T$	W	$X$	$Y$	$Z$
$Q$	-	30	35	25	37	40	43	32
$R$	30	-	12	15	15	20	20	8
S	35	12	-	20	10	18	25	16
$T$	25	15	20	-	12	16	18	18
W	37	15	10	12	-	8	14	20
$X$	40	20	18	16	8	-	17	22
$Y$	43	20	25	18	14	17	-	13
Z	32	8	16	18	20	22	13	-

Use the nearest neighbour method to find an upper bound for the minimum time to travel to each of the eight places, starting and finishing at $Y$. Write down the route and give the time in minutes.
The Answer Book lists the arcs by increasing order of weight (reading across the rows). Apply Kruskal's algorithm to this list to find the minimum spanning tree for all eight places. Draw your tree and give its total weight.
(a) Vertex $Q$ and all arcs joined to $Q$ are temporarily removed. Use your answer to part (ii) to write down the weight of the minimum spanning tree for the seven vertices $R , S , T , W , X , Y$ and $Z$.
(b) Use your answer to part (iii)(a) to find a lower bound for the minimum time to travel to each of the eight places of interest, starting and finishing at $Y$. The tour guide allows for a 5 -minute stop at each of $S$ and $Y$, a 10 -minute stop at $T$ and a 30 -minute stop at each of $Q , R , W , X$ and $Z$. The tour guide wants to find a route, starting and ending at $Y$, in which the tour (including the stops) can be completed in five hours (300 minutes).
Use the nearest neighbour method, starting at $Q$, to find a closed route through each vertex. Hence find a route for the tour, showing that it can be completed in time.

OCR D1 Specimen Q1

4 marks Easy -1.2

1 The graph $\mathrm { K } _ { 5 }$ has five nodes, $A , B , C , D$ and $E$, and there is an arc joining every node to every other node.

Draw the graph $\mathrm { K } _ { 5 }$ and state how you know that it is Eulerian.
By listing the arcs involved, give an example of a path in $\mathrm { K } _ { 5 }$. (Your path must include more than one arc.)
By listing the arcs involved, give an example of a cycle in $\mathrm { K } _ { 5 }$.

OCR D1 Specimen Q2

7 marks Moderate -0.8

2 This question is about a simply connected network with at least three arcs joining 4 nodes. The weights on the arcs are all different and any direct paths always have a smaller weight than the total weight of any indirect paths between two vertices.

Kruskal's algorithm is used to construct a minimum connector. Explain why the arcs with the smallest and second smallest weights will always be included in this minimum connector.
Draw a diagram to show that the arc with the third smallest weight need not always be included in a minimum connector.

OCR D1 Specimen Q3

8 marks Easy -1.2

3

Use the shuttle sort algorithm to sort the list $$\begin{array} { l l l l l } 6 & 3 & 8 & 3 & 2 \end{array}$$ into increasing order. Write down the list that results from each pass through the algorithm.
Shuttle sort is a quadratic order algorithm. Explain briefly what this statement means.

OCR D1 Specimen Q4

9 marks Easy -1.2

4 [Answer this question on the insert provided.]
An algorithm involves the following steps.
Step 1: Input two positive integers, $A$ and $B$.
Let $C = 0$ Step 2: If $B$ is odd, replace $C$ by $C + A$.
Step 3: If $B = 1$, go to step 6.
Step 4: Replace $A$ by $2 A$.
If $B$ is even, replace $B$ by $B \div 2$, otherwise replace $B$ by ( $B - 1$ ) ÷ 2 .
Step 5: Go back to step 2.
Step 6: Output the value of $C$.

Demonstrate the use of the algorithm for the inputs $A = 6$ and $B = 13$.
When $B = 8$, what is the output in terms of $A$ ? What is the relationship between the output and the original inputs?

OCR D1 Specimen Q5

9 marks Moderate -0.5

5 [Answer this question on the insert provided.] \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-3_659_1002_324_609} In this network the vertices represent towns, the arcs represent roads and the weights on the arcs show the shortest distances in kilometres.

The diagram on the insert shows the result of deleting vertex $F$ and all the arcs joined to $F$. Show that a lower bound for the length of the travelling salesperson problem on the original network is 38 km . The corresponding lower bounds by deleting each of the other vertices are: $$A : 40 \mathrm {~km} , \quad B : 39 \mathrm {~km} , \quad C : 35 \mathrm {~km} , \quad D : 37 \mathrm {~km} , \quad E : 35 \mathrm {~km} \text {. }$$ The route $A - B - C - D - E - F - A$ has length 47 km .
Using only this information, what are the best upper and lower bounds for the length of the solution to the travelling salesperson problem on the network?
By considering the orders in which vertices $C , D$ and $E$ can be visited, find the best upper bound given by a route of the form $A - B - \ldots - F - A$.

OCR D1 Specimen Q6

15 marks Standard +0.3

6 [Answer part (i) of this question on the insert provided.]
The diagram shows a simplified version of an orienteering course. The vertices represent checkpoints and the weights on the arcs show the travel times between checkpoints, in minutes. \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-4_483_931_461_630}

Use Dijkstra's algorithm, starting from checkpoint $\boldsymbol { A }$, to find the least travel time from $A$ to $D$. You must show your working, including temporary labels, permanent labels and the order in which permanent labels were assigned. Give the route that takes the least time from $A$ to $D$.
By using an appropriate algorithm, find the least time needed to travel every arc in the diagram starting and ending at $A$. You should show your method clearly.
Starting from $A$, apply the nearest neighbour algorithm to the diagram to find a cycle that visits every checkpoint. Use your solution to find a path that visits every checkpoint, starting from $A$ and finishing at $D$.

OCR D1 Specimen Q7

20 marks Moderate -0.3

7 Consider the linear programming problem: $$\begin{array} { l l } \text { maximise } & P = 4 y - x , \\ \text { subject to } & x + 4 y \leqslant 22 , \\ & x + y \leqslant 10 , \\ & - x + 2 y \leqslant 8 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 . \end{array}$$

Represent the constraints graphically, shading out the regions where the inequalities are not satisfied. Calculate the value of $x$ and the value of $y$ at each of the vertices of the feasible region. Hence find the maximum value of $P$, clearly indicating where it occurs.
By introducing slack variables, represent the problem as an initial Simplex tableau and use the Simplex algorithm to solve the problem.
Indicate on your diagram for part (i) the points that correspond to each stage of the Simplex algorithm carried out in part (ii). \section*{OXFORD CAMBRIDGE AND RSA EXAMINATIONS} Advanced Subsidiary General Certificate of Education Advanced General Certificate of Education MATHEMATICS
4736
Decision Mathematics 1
INSERT for Questions 4, 5 and 6
Specimen Paper

4

STEP A $B$ C
1
2
STEP A $B$ C
1
2

5

\includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-7_661_1004_285_557}
Upper bound = $\_\_\_\_$ km Lower bound = $\_\_\_\_$ km
$\_\_\_\_$ Best upper bound = $\_\_\_\_$ km

6

\includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-8_668_1406_292_406} \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-8_307_1342_1014_424}
Least travel time = $\_\_\_\_$ minutes Route: A- $\_\_\_\_$ $- D$

OCR D2 2006 January Q3

12 marks Standard +0.3

3 The network represents a system of pipes along which fluid can flow from $S$ to $T$. The values on the arcs are the capacities in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-3_634_1112_404_484}

Calculate the capacity of the cut with $\mathrm { X } = \{ S , A , B , C \} , \mathrm { Y } = \{ D , E , F , G , H , I , T \}$.
Explain why the capacity of the cut $\alpha$, shown on the diagram, is only 21 litres per second.
Explain why neither of the arcs $S C$ and $A D$ can be full to capacity. Give the maximum flow in $\operatorname { arc } S B$.
Find the maximum flow through the system and draw a diagram to show a way in which this can be achieved. Show that your flow is maximal by using the maximum flow-minimum cut theorem.

OCR D2 2006 January Q4

13 marks Moderate -0.8

4 Four workers, $A , B , C$ and $D$, are to be allocated, one to each of the four jobs, $W , X , Y$ and $Z$. The table shows how much each worker would charge for each job. \includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-3_401_846_1745_642}

What is the total cost of the four jobs if $A$ does $W , B$ does $X , C$ does $Y$ and $D$ does $Z$ ?
Apply the Hungarian algorithm to the table, reducing rows first. Show all your working and explain each step. Give the resulting allocation and the total cost of the four jobs with this allocation.
What problem does the Hungarian algorithm solve?

OCR D2 2006 January Q6

15 marks Moderate -1.0

6 Lucy and Maria repeatedly play a zero-sum game. The pay-off matrix shows the number of points won by Lucy, who is playing rows, for each combination of strategies.


\cline { 2 - 5 }	$X$	$Y$	$Z$
$A$	2	- 3	4
\cline { 2 - 5 } Lucy's	$B$	- 3	5	1
\cline { 2 - 5 } strategyy	$C$	4	2	- 3

Show that strategy $A$ does not dominate strategy $B$ and also that strategy $B$ does not dominate strategy $A$.
Show that Maria will not choose strategy $Y$ if she plays safe.
Give a reason why Lucy might choose to play strategy $B$. Lucy decides to play strategy $A$ with probability $p _ { 1 }$, strategy $B$ with probability $p _ { 2 }$ and strategy $C$ with probability $p _ { 3 }$. She formulates the following LP problem to be solved using the Simplex algorithm: $$\begin{array} { l l } \text { maximise } & M = m - 3 , \\ \text { subject to } & m \leqslant 5 p _ { 1 } + 7 p _ { 3 } , \\ & m \leqslant 8 p _ { 2 } + 5 p _ { 3 } , \\ & m \leqslant 7 p _ { 1 } + 4 p _ { 2 } , \\ & p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1 , \\ \text { and } & p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , p _ { 3 } \geqslant 0 , m \geqslant 0 . \end{array}$$ [You are not required to solve this problem.]
Explain why 3 has to be subtracted from $m$ in the objective row.
Explain how $5 p _ { 1 } + 7 p _ { 3 } , 8 p _ { 2 } + 5 p _ { 3 }$ and $7 p _ { 1 } + 4 p _ { 2 }$ were obtained.
Explain why $m$ has to be less than or equal to each of the expressions in part (v). Lucy discovers that Maria does not intend ever to choose strategy $Y$. Because of this she decides that she will never choose strategy $B$. This means that $p _ { 2 } = 0$.
Show that the expected number of points won by Lucy when Maria chooses strategy $X$ is $4 - 2 p _ { 1 }$ and find a similar expression for the number of points won by Lucy when Maria chooses strategy $Z$.
Set your two expressions from part (vii) equal to each other and solve for $p _ { 1 }$. Calculate the expected number of points won by Lucy with this value of $p _ { 1 }$ and also when $p _ { 1 } = 0$ and when $p _ { 1 } = 1$. Use these values to decide how Lucy should choose between strategies $A$ and $C$ to maximise the expected number of points that she wins.

OCR D2 2007 January Q1

8 marks Moderate -0.8

1 Four friends have rented a house and need to decide who will have which bedroom. The table below shows how each friend rated each room, so the higher the rating the more the room was liked.

The Hungarian algorithm is to be used to find the matching with the greatest total. Before the Hungarian algorithm can be used, each rating is subtracted from 6.

Explain why the ratings could not be used as given in the table.
Apply the Hungarian algorithm, reducing rows first, to match the friends to the rooms. You must show your working and say how each matrix was formed.

OCR D2 2007 January Q2

8 marks Moderate -0.8

2 The table shows the activities involved in a project, their durations, precedences and the number of workers needed for each activity. The graph gives a schedule with each activity starting at its earliest possible time.

Activity	Duration (hours)	Immediate predecessors	Number of workers
$A$	3	-	3
$B$	5	$A$	2
C	3	A	2
$D$	3	B	1
E	3	C	3
$F$	5	D, E	2
$G$	3	$B , E$	3

\includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-03_473_1591_964_278}

Using the graph, find the minimum completion time for the project and state which activities are critical.
Draw a resource histogram, using graph paper, assuming that there are no delays and that every activity starts at its earliest possible time. Assume that only four workers are available but that they are equally skilled at all tasks. Assume also that once an activity has been started it continues until it is finished.
The critical activities are to start at their earliest possible times. List the start times for the non-critical activities for completion of the project in the minimum possible time. What is this minimum completion time?

OCR D2 2007 January Q3

8 marks Easy -2.0

3 Rebecca and Claire repeatedly play a zero-sum game in which they each have a choice of three strategies, $X , Y$ and $Z$. The table shows the number of points Rebecca scores for each pair of strategies. \begin{table}[h]

\captionsetup{labelformat=empty} \caption{Claire}

	$X$	$Y$	$Z$
\cline { 2 - 5 }	$X$	5	- 3	1
\cline { 2 - 5 } Rebecca	$Y$	3	2	- 2
\cline { 2 - 5 }	$Z$	- 1	1	3
\cline { 2 - 5 }
\cline { 2 - 5 }

\end{table}

If both players choose strategy $X$, how many points will Claire score?
Show that row $X$ does not dominate row $Y$ and that column $Y$ does not dominate column $Z$.
Find the play-safe strategies. State which strategy is best for Claire if she knows that Rebecca will play safe.
Explain why decreasing the value ' 5 ' when both players choose strategy $X$ cannot alter the playsafe strategies.

OCR D2 2007 January Q4

10 marks Standard +0.3

4 The table gives the pay-off matrix for a zero-sum game between two players, Rowan and Colin. \begin{table}[h]

\captionsetup{labelformat=empty} \caption{Colin}

\cline { 2 - 5 }		Strategy $X$	Strategy $Y$	Strategy $Z$
\cline { 2 - 5 } Rowan	Strategy $P$	5	- 3	- 2
\cline { 2 - 5 }	Strategy $Q$	- 4	3	1
\cline { 2 - 5 }
\cline { 2 - 5 }

\end{table} Rowan makes a random choice between strategies $P$ and $Q$, choosing strategy $P$ with probability $p$ and strategy $Q$ with probability $1 - p$.

Write down and simplify an expression for the expected pay-off for Rowan when Colin chooses strategy $X$.
Using graph paper, draw a graph to show Rowan's expected pay-off against $p$ for each of Colin's choices of strategy.
Using your graph, find the optimal value of $p$ for Rowan.
Rowan plays using the optimal value of $p$. Explain why, in the long run, Colin cannot expect to win more than 0.25 per game.

OCR D2 2007 January Q5

12 marks Moderate -0.5

5

Capacity = $\_\_\_\_$
\includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_671_997_456_614}
Route: $\_\_\_\_$ Flow $=$ $\_\_\_\_$
Maximum flow = $\_\_\_\_$ Cut: $\mathrm { X } = \{$ \} $\quad \mathrm { Y } = \{$
\includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_659_995_1774_616}

OCR D2 2007 January Q7

14 marks Moderate -0.5

7 Annie (A), Brigid (B), Carla (C) and Diane ( $D$ ) are hanging wallpaper in a stairwell. They have broken the job down into four tasks: measuring and cutting the paper ( $M$ ), pasting the paper ( $P$ ), hanging and then trimming the top end of the paper ( $H$ ) and smoothing out the air bubbles and then trimming the lower end of the paper ( $S$ ). They will each do one of these tasks.

Annie does not like climbing ladders but she is prepared to do tasks $M , P$ or $S$
Brigid gets into a mess with paste so she is only able to do tasks $M$ or $S$
Carla enjoys hanging the paper so she wants to do task $H$ or task $S$
Diane wants to do task $H$

Initially Annie chooses task $M$, Brigid task $S$ and Carla task $H$.

Draw a bipartite graph to show the available pairings between the people and the tasks. Write down an alternating path to improve the initial matching and write down the complete matching from your alternating path. Hanging the wallpaper is part of a bigger decorating project. The table lists the activities involved, their durations and precedences.
Maximin value $=$ Route $=$

OCR D2 2008 January Q1

14 marks Easy -1.8

1 Arnie (A), Brigitte (B), Charles (C), Diana (D), Edward (E) and Faye (F) are moving into a home for retired Hollywood stars. They all still expect to be treated as stars and each has particular requirements. Arnie wants a room that can be seen from the road, but does not want a ground floor room; Brigitte wants a room that looks out onto the garden; Charles wants a ground floor room; Diana wants a room with a balcony; Edward wants a second floor room; Faye wants a room, with a balcony, that can be seen from the road. The table below shows the features of each of the six rooms available.

Room	Floor	Can be seen from road	Looks out onto garden	Has balcony
1	Ground	✓
2	Ground		✓
3	First		✓	✓
4	First	✓		✓
5	Second		✓	✓
6	Second	✓

Draw a bipartite graph to show the possible pairings between the stars ( $A , B , C , D , E$ and $F$ ) and the rooms ( $1,2,3,4,5$ and 6 ). Originally Arnie was given room 4, Brigitte was given room 3, Charles was given room 2, Diana was given room 5, Edward was given room 6 and Faye was given room 1.
Identify the star that has not been given a room that satisfies their requirements. Draw a second bipartite graph to show the incomplete matching that results when this star is not given a room.
Construct the shortest possible alternating path, starting from the star without a room and ending at the room that was not used, and hence find a complete matching between the stars and the rooms. Write a list showing which star should be given which room. When the stars view the rooms they decide that some are much nicer than others. Each star gives each room a value from 1 to 6 , where 1 is the room they would most like and 6 is the room they would least like. The results are shown below.
\multirow{2}{*}{} Room
1 2 3 4 5 6
Arnie (A) 3 6 4 1 5 2
Brigitte ( $B$ ) 5 3 2 4 1 6
Charles (C) 2 1 3 4 5 6
Diana (D) 5 4 1 3 2 6
Edward ( $E$ ) 5 6 4 3 2 1
Faye (F) 5 6 4 1 3 2
Apply the Hungarian algorithm to this table, reducing rows first, to find a minimum 'cost' allocation between the stars and the rooms. Write a list showing which star should be given which room according to this allocation. Write down the name of any star whose original requirements are not satisfied.

OCR D2 2008 January Q2

17 marks Easy -1.2

2 As part of a team-building exercise the reprographics technicians (Team R) and the computer network support staff (Team C) take part in a paintballing game. The game ends when a total of 10 'hits' have been scored. Each team has to choose a player to be its captain. The number of 'hits' expected by Team R for each pair of captains is shown below.

Complete the last two columns of the table in the insert.
State the minimax value and write down the minimax route.
Draw the network represented by the table.

OCR D2 2008 January Q3

12 marks Moderate -0.5

3

Stage	State	Action	Working	Minimax
\multirow{3}{*}{1}	0	0	1
	1	0	3
	2	0	2
\multirow{6}{*}{2}	\multirow{2}{*}{0}	0	(4,	\multirow{2}{*}{}
		1	(2,
	\multirow{2}{*}{1}	1	(3,	\multirow{2}{*}{}
		2	(5,
	\multirow{2}{*}{2}	0	(2,	\multirow{2}{*}{}
		2	(4,
\multirow{3}{*}{3}	\multirow{3}{*}{0}	0	(5,	\multirow{3}{*}{}
		1	(3,
		2	(1,

Minimax value = $\_\_\_\_$ Minimax route = $\_\_\_\_$
\includegraphics[max width=\textwidth, alt={}, center]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-10_958_1527_1539_351}

Previous
1
2
3
...
83
84
85
86
87
...
196
197
Next

\(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	RHS
1	- 10	2	3	0	0	0
0	5	0	- 5	1	0	60
0	4	3	0	0	1	100

Questions — OCR (4907 questions)

Browse by module

Browse by board

OCR D1 2016 June Q2

OCR D1 2016 June Q3

OCR D1 2016 June Q4

OCR D1 2016 June Q5

OCR D1 2016 June Q6

OCR D1 2016 June Q7

OCR D1 Specimen Q1

OCR D1 Specimen Q2

OCR D1 Specimen Q3

OCR D1 Specimen Q4

OCR D1 Specimen Q5

OCR D1 Specimen Q6

OCR D1 Specimen Q7

OCR D2 2006 January Q3

OCR D2 2006 January Q4

OCR D2 2006 January Q6

OCR D2 2007 January Q1

OCR D2 2007 January Q2

OCR D2 2007 January Q3

OCR D2 2007 January Q4

OCR D2 2007 January Q5

OCR D2 2007 January Q7

OCR D2 2008 January Q1

OCR D2 2008 January Q2

OCR D2 2008 January Q3

	\(Q\)	\(R\)	S	\(T\)	W	\(X\)	\(Y\)	\(Z\)
\(Q\)	-	30	35	25	37	40	43	32
\(R\)	30	-	12	15	15	20	20	8
S	35	12	-	20	10	18	25	16
\(T\)	25	15	20	-	12	16	18	18
W	37	15	10	12	-	8	14	20
\(X\)	40	20	18	16	8	-	17	22
\(Y\)	43	20	25	18	14	17	-	13
Z	32	8	16	18	20	22	13	-

\(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	RHS
1	0	7.25	0	0.6	1.75	211
0	1	0.75	0	0	0.25	25
0	0	0.75	1	- 0.2	0.25	13

STEP	A	\(B\)	C
1
2

STEP	A	\(B\)	C
1
2