Questions - A-Level Maths

AQA D1 2016 June Q5

8 marks Standard +0.8

5 A fair comes to town one year and sets up its rides in two large fields that are separated by a river. The diagram shows the ten main rides, at $A , B , C , \ldots , J$. The numbers on the edges represent the times, in minutes, it takes to walk between pairs of rides. A footbridge connects the rides at $D$ and $F$.

1. Use Dijkstra's algorithm on the diagram below to find the minimum time to walk from $A$ to each of the other main rides.
2. Write down the route corresponding to the minimum time to walk from $A$ to $G$.
The following year, the fair returns. In addition to the information shown on the diagram, another footbridge has been built to connect the rides at $E$ and $G$. This reduces the time taken to travel from $A$ to $G$, but the time taken to travel from $A$ to $J$ is not reduced. The time to walk across the footbridge from $E$ to $G$ is $x$ minutes, where $x$ is an integer. Find two inequalities for $x$ and hence state the value of $x$. \section*{Answer space for question 5}
1. \includegraphics[max width=\textwidth, alt={}, center]{fb95068f-f76d-492a-b385-bce17b26ae30-12_659_1591_1692_223}

AQA D1 2016 June Q6

7 marks Moderate -0.5

6 A connected graph is semi-Eulerian if exactly two of its vertices are of odd degree.

A graph is drawn with 4 vertices and 7 edges. What is the sum of the degrees of the vertices?
Draw a simple semi-Eulerian graph with exactly 5 vertices and 5 edges, in which exactly one of the vertices has degree 4 .
Draw a simple semi-Eulerian graph with exactly 5 vertices that is also a tree.
A simple graph has 6 vertices. The graph has two vertices of degree 5 . Explain why the graph can have no vertex of degree 1.

AQA D1 2016 June Q7

17 marks Moderate -0.5

7 A company operates a steam railway between six stations. The minimum cost (in euros) of travelling between pairs of stations is shown in the table below.

On Figure 1 below, use Prim's algorithm, starting from $P$, to find a minimum spanning tree for the graph connecting $P , Q , R , S , T$ and $U$. State clearly the order in which you select the vertices and draw your minimum spanning tree. \section*{Question 7 continues on page 20} \begin{table}[h]

\captionsetup{labelformat=empty} \caption{Figure 1}

	$\boldsymbol { P }$	$\boldsymbol { Q }$	$\boldsymbol { R }$	$\boldsymbol { S }$	$\boldsymbol { T }$	$\boldsymbol { U }$
$\boldsymbol { P }$	-	14	7	11	6	12
$\boldsymbol { Q }$	14	-	8	10	9	10
$\boldsymbol { R }$	7	8	-	12	13	15
$\boldsymbol { S }$	11	10	12	-	5	11
$\boldsymbol { T }$	6	9	13	5	-	10
$\boldsymbol { U }$	12	10	15	11	10	-

\end{table}

Another station, $V$, is opened. The minimum costs (in euros) of travelling to and from $V$ to each of the other stations are added to the table in part (a), as shown in Figure 2(i) below. Further copies of this table are shown in Figure 2(ii). Arjen is on holiday and he plans to visit each station. He intends to board a train at $V$ and visit all the other stations, once only, before returning to $V$.

By first removing $V$, obtain a lower bound for the minimum travelling cost of Arjen's tour. (You may use Figure 2(i) for your working.)
Use the nearest neighbour algorithm twice, starting each time from $V$, to find two different upper bounds for the minimum cost of Arjen's tour. State, with a reason, which of your two answers gives the better upper bound. (You may use Figure 2(ii) for your working.)

Hence find an optimal tour of the seven stations. Explain how you know that it is optimal. Answer space for question 7(b) \begin{table}[h]

\captionsetup{labelformat=empty} \caption{Figure 2(ii)}

	$\boldsymbol { P }$	$Q$	$\boldsymbol { R }$	$\boldsymbol { S }$	$T$	$\boldsymbol { U }$	$V$
$\boldsymbol { P }$	-	14	7	11	6	12	15
$Q$	14	-	8	10	9	10	18
$\boldsymbol { R }$	7	8	-	12	13	15	14
$\boldsymbol { S }$	11	10	12	-	5	11	14
$T$	6	9	13	5	-	10	17
$\boldsymbol { U }$	12	10	15	11	10	-	12
$V$	15	18	14	14	17	12	-

\end{table}

AQA D1 2016 June Q8

13 marks Easy -1.2

8 Nerys runs a cake shop. In November and December she sells Christmas hampers. She makes up the hampers herself, in two sizes: Luxury and Special. Each day, Nerys prepares $x$ Luxury hampers and $y$ Special hampers.
It takes Nerys 10 minutes to prepare a Luxury hamper and 15 minutes to prepare a Special hamper. She has 6 hours available, each day, for preparing hampers. From past experience, Nerys knows that each day:

she will need to prepare at least 5 hampers of each size
she will prepare at most a total of 32 hampers
she will prepare at least twice as many Luxury hampers as Special hampers.

Each Luxury hamper that Nerys prepares makes her a profit of $\pounds 15$; each Special hamper makes a profit of $\pounds 20$. Nerys wishes to maximise her daily profit, $\pounds P$.

Show that $x$ and $y$ must satisfy the inequality $2 x + 3 y \leqslant 72$.
In addition to $x \geqslant 5$ and $y \geqslant 5$, write down two more inequalities that model the constraints above.
On the grid opposite draw a suitable diagram to enable this problem to be solved graphically. Indicate a feasible region and the direction of an objective line.
1. Use your diagram to find the number of each type of hamper that Nerys should prepare each day to achieve a maximum profit.
2. Calculate this profit.
  \includegraphics[max width=\textwidth, alt={}]{fb95068f-f76d-492a-b385-bce17b26ae30-27_2490_1719_217_150}
  \section*{DO NOT WRITE ON THIS PAGE ANSWER IN THE SPACES PROVIDED}

OCR MEI D1 2007 January Q1

8 marks Easy -1.8

1 Each of the following symbols consists of boundaries enclosing regions.
(0) 1

OCR MEI D1 2007 January Q3

8 marks Easy -1.8

3 $\triangle$ 5
(5) 7
(8)
(O) The symbol representing zero has three regions, the outside, that between the two boundaries and the inside. To classify the symbols a graph is produced for each one. The graph has a vertex for each region, with arcs connecting regions which share a boundary. Thus the graph for \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_110_81_900_767}
is \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_49_350_959_959}

Produce the graph for the symbol
Give two symbols each having the graph \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_52_199_1187_1030}
Produce the graph for the symbol .
Produce a single graph for the composite symbol \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_112_158_1398_1165}
Give the name of a connected graph with $n$ nodes and $n - 1 \operatorname { arcs }$. 2 The following algorithm is a version of bubble sort.
Step 1 Store the values to be sorted in locations $\mathrm { L } ( 1 ) , \mathrm { L } ( 2 ) , \ldots , \mathrm { L } ( \mathrm { n } )$ and set i to be the number, n , of values to be sorted. Step $2 \quad$ Set $\mathrm { j } = 1$.
Step 3 Compare the values in locations $\mathrm { L } ( \mathrm { j } )$ and $\mathrm { L } ( \mathrm { j } + 1 )$ and swap them if that $\mathrm { in } \mathrm { L } ( \mathrm { j } )$ is larger than that in $\mathrm { L } ( \mathrm { j } + 1 )$. Step 4 Add 1 to j.
Step 5 If j is less than i then go to step 3.
Step 5 Write out the current list, $\mathrm { L } ( 1 ) , \mathrm { L } ( 2 ) , \ldots , \mathrm { L } ( \mathrm { n } )$.
Step 6 Subtract 1 from i .
Step 7 If i is larger than 1 then go to step 2.
Step 8 Stop.
Apply this algorithm to sort the following list. $$\begin{array} { l l l l l } 109 & 32 & 3 & 523 & 58 \end{array} .$$ Count the number of comparisons and the number of swaps which you make in applying the algorithm.
Put the five values into the order which maximises the number of swaps made in applying the algorithm, and give that number.
Bubble sort has quadratic complexity. Using bubble sort it takes a computer 1.5 seconds to sort a list of 1000 values. Approximately how long would it take to sort a list of 100000 values? (Give your answer in hours and minutes.) 3 A bag contains five pieces of paper labelled A, B, C, D and E. One piece is drawn at random from the bag. If the piece is labelled with a vowel (A or E) then the process stops. Otherwise the piece of paper is replaced, the bag is shaken, and the process is repeated. You are to simulate this process to estimate the mean number of draws needed to get a vowel.
Show how to use single digit random numbers to simulate the process efficiently. You need to describe exactly how your simulation will work.
Use the random numbers in your answer book to run your simulation 5 times, recording your results.
From your results compute an estimate of the mean number of draws needed to get a vowel.
State how you could produce a more accurate estimate. Section B (48 marks)

OCR MEI D1 2007 January Q5

16 marks Easy -1.8

5
(5) 7
(8)
(O) The symbol representing zero has three regions, the outside, that between the two boundaries and the inside. To classify the symbols a graph is produced for each one. The graph has a vertex for each region, with arcs connecting regions which share a boundary. Thus the graph for \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_110_81_900_767}
is \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_49_350_959_959}

Produce the graph for the symbol
Give two symbols each having the graph \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_52_199_1187_1030}
Produce the graph for the symbol .
Produce a single graph for the composite symbol \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_112_158_1398_1165}
Give the name of a connected graph with $n$ nodes and $n - 1 \operatorname { arcs }$. 2 The following algorithm is a version of bubble sort.
Step 1 Store the values to be sorted in locations $\mathrm { L } ( 1 ) , \mathrm { L } ( 2 ) , \ldots , \mathrm { L } ( \mathrm { n } )$ and set i to be the number, n , of values to be sorted. Step $2 \quad$ Set $\mathrm { j } = 1$.
Step 3 Compare the values in locations $\mathrm { L } ( \mathrm { j } )$ and $\mathrm { L } ( \mathrm { j } + 1 )$ and swap them if that $\mathrm { in } \mathrm { L } ( \mathrm { j } )$ is larger than that in $\mathrm { L } ( \mathrm { j } + 1 )$. Step 4 Add 1 to j.
Step 5 If j is less than i then go to step 3.
Step 5 Write out the current list, $\mathrm { L } ( 1 ) , \mathrm { L } ( 2 ) , \ldots , \mathrm { L } ( \mathrm { n } )$.
Step 6 Subtract 1 from i .
Step 7 If i is larger than 1 then go to step 2.
Step 8 Stop.
Apply this algorithm to sort the following list. $$\begin{array} { l l l l l } 109 & 32 & 3 & 523 & 58 \end{array} .$$ Count the number of comparisons and the number of swaps which you make in applying the algorithm.
Put the five values into the order which maximises the number of swaps made in applying the algorithm, and give that number.
Bubble sort has quadratic complexity. Using bubble sort it takes a computer 1.5 seconds to sort a list of 1000 values. Approximately how long would it take to sort a list of 100000 values? (Give your answer in hours and minutes.) 3 A bag contains five pieces of paper labelled A, B, C, D and E. One piece is drawn at random from the bag. If the piece is labelled with a vowel (A or E) then the process stops. Otherwise the piece of paper is replaced, the bag is shaken, and the process is repeated. You are to simulate this process to estimate the mean number of draws needed to get a vowel.
Show how to use single digit random numbers to simulate the process efficiently. You need to describe exactly how your simulation will work.
Use the random numbers in your answer book to run your simulation 5 times, recording your results.
From your results compute an estimate of the mean number of draws needed to get a vowel.

State how you could produce a more accurate estimate. Section B (48 marks)
4 Cassi is managing the building of a house. The table shows the major activities that are involved, their durations and their precedences.

Activity		Duration (days)	Immediate predecessors
A	Build concrete frame	10	-
B	Lay bricks	7	A
C	Lay roof tiles	10	A
D	First fit electrics	5	B
E	First fit plumbing	4	B
F	Plastering	6	C, D, E
G	Second fit electrics	3	F
H	Second fit plumbing	2	F
I	Tiling	10	G, H
J	Fit sanitary ware	2	H
K	Fit windows and doors	5	I

Draw an activity-on-arc network to represent this information.
Find the early time and the late time for each event. Give the project duration and list the critical activities.
Calculate total and independent floats for each non-critical activity. Cassi's clients wish to take delivery in 42 days. Some durations can be reduced, at extra cost, to achieve this.
- The tiler will finish activity I in 9 days for an extra $\pounds 250$, or in 8 days for an extra $\pounds 500$.
- The bricklayer will cut his total of 7 days on activity B by up to 3 days at an extra cost of $\pounds 350$ per day.
- The electrician could be paid $\pounds 300$ more to cut a day off activity D, or $\pounds 600$ more to cut two days.
- What is the cheapest way in which Cassi can get the house built in 42 days?
5 Leone is designing her new garden. She wants to have at least $1000 \mathrm {~m} ^ { 2 }$, split between lawn and flower beds. Initial costs are $\pounds 0.80$ per $\mathrm { m } ^ { 2 }$ for lawn and $\pounds 0.40$ per $\mathrm { m } ^ { 2 }$ for flowerbeds. Leone's budget is $\pounds 500$.
Leone prefers flower beds to lawn, and she wants the area for flower beds to be at least twice the area for lawn. However, she wants to have at least $200 \mathrm {~m} ^ { 2 }$ of lawn. Maintenance costs each year are $\pounds 0.15$ per $\mathrm { m } ^ { 2 }$ for lawn and $\pounds 0.25$ per $\mathrm { m } ^ { 2 }$ for flower beds. Leone wants to minimize the maintenance costs of her garden.
Formulate Leone's problem as a linear programming problem.
Produce a graph to illustrate the inequalities.
Solve Leone's problem.
If Leone had more than $\pounds 500$ available initially, how much extra could she spend to minimize maintenance costs?

OCR MEI D1 2007 January Q7

Easy -1.8

7
(8)
(O) The symbol representing zero has three regions, the outside, that between the two boundaries and the inside. To classify the symbols a graph is produced for each one. The graph has a vertex for each region, with arcs connecting regions which share a boundary. Thus the graph for \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_110_81_900_767}
is \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_49_350_959_959}

Produce the graph for the symbol
Give two symbols each having the graph \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_52_199_1187_1030}
Produce the graph for the symbol .
Produce a single graph for the composite symbol \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_112_158_1398_1165}
Give the name of a connected graph with $n$ nodes and $n - 1 \operatorname { arcs }$. 2 The following algorithm is a version of bubble sort.
Step 1 Store the values to be sorted in locations $\mathrm { L } ( 1 ) , \mathrm { L } ( 2 ) , \ldots , \mathrm { L } ( \mathrm { n } )$ and set i to be the number, n , of values to be sorted. Step $2 \quad$ Set $\mathrm { j } = 1$.
Step 3 Compare the values in locations $\mathrm { L } ( \mathrm { j } )$ and $\mathrm { L } ( \mathrm { j } + 1 )$ and swap them if that $\mathrm { in } \mathrm { L } ( \mathrm { j } )$ is larger than that in $\mathrm { L } ( \mathrm { j } + 1 )$. Step 4 Add 1 to j.
Step 5 If j is less than i then go to step 3.
Step 5 Write out the current list, $\mathrm { L } ( 1 ) , \mathrm { L } ( 2 ) , \ldots , \mathrm { L } ( \mathrm { n } )$.
Step 6 Subtract 1 from i .
Step 7 If i is larger than 1 then go to step 2.
Step 8 Stop.
Apply this algorithm to sort the following list. $$\begin{array} { l l l l l } 109 & 32 & 3 & 523 & 58 \end{array} .$$ Count the number of comparisons and the number of swaps which you make in applying the algorithm.
Put the five values into the order which maximises the number of swaps made in applying the algorithm, and give that number.
Bubble sort has quadratic complexity. Using bubble sort it takes a computer 1.5 seconds to sort a list of 1000 values. Approximately how long would it take to sort a list of 100000 values? (Give your answer in hours and minutes.) 3 A bag contains five pieces of paper labelled A, B, C, D and E. One piece is drawn at random from the bag. If the piece is labelled with a vowel (A or E) then the process stops. Otherwise the piece of paper is replaced, the bag is shaken, and the process is repeated. You are to simulate this process to estimate the mean number of draws needed to get a vowel.
Show how to use single digit random numbers to simulate the process efficiently. You need to describe exactly how your simulation will work.
Use the random numbers in your answer book to run your simulation 5 times, recording your results.
From your results compute an estimate of the mean number of draws needed to get a vowel.

State how you could produce a more accurate estimate. Section B (48 marks)
4 Cassi is managing the building of a house. The table shows the major activities that are involved, their durations and their precedences.

Activity		Duration (days)	Immediate predecessors
A	Build concrete frame	10	-
B	Lay bricks	7	A
C	Lay roof tiles	10	A
D	First fit electrics	5	B
E	First fit plumbing	4	B
F	Plastering	6	C, D, E
G	Second fit electrics	3	F
H	Second fit plumbing	2	F
I	Tiling	10	G, H
J	Fit sanitary ware	2	H
K	Fit windows and doors	5	I

Draw an activity-on-arc network to represent this information.
Find the early time and the late time for each event. Give the project duration and list the critical activities.
Calculate total and independent floats for each non-critical activity. Cassi's clients wish to take delivery in 42 days. Some durations can be reduced, at extra cost, to achieve this.
- The tiler will finish activity I in 9 days for an extra $\pounds 250$, or in 8 days for an extra $\pounds 500$.
- The bricklayer will cut his total of 7 days on activity B by up to 3 days at an extra cost of $\pounds 350$ per day.
- The electrician could be paid $\pounds 300$ more to cut a day off activity D, or $\pounds 600$ more to cut two days.
- What is the cheapest way in which Cassi can get the house built in 42 days?
5 Leone is designing her new garden. She wants to have at least $1000 \mathrm {~m} ^ { 2 }$, split between lawn and flower beds. Initial costs are $\pounds 0.80$ per $\mathrm { m } ^ { 2 }$ for lawn and $\pounds 0.40$ per $\mathrm { m } ^ { 2 }$ for flowerbeds. Leone's budget is $\pounds 500$.
Leone prefers flower beds to lawn, and she wants the area for flower beds to be at least twice the area for lawn. However, she wants to have at least $200 \mathrm {~m} ^ { 2 }$ of lawn. Maintenance costs each year are $\pounds 0.15$ per $\mathrm { m } ^ { 2 }$ for lawn and $\pounds 0.25$ per $\mathrm { m } ^ { 2 }$ for flower beds. Leone wants to minimize the maintenance costs of her garden.
Formulate Leone's problem as a linear programming problem.
Produce a graph to illustrate the inequalities.
Solve Leone's problem.
If Leone had more than $\pounds 500$ available initially, how much extra could she spend to minimize maintenance costs? 6 In a factory a network of pipes connects 6 vats, A, B, C, D, E and F. Two separate connectors need to be chosen from the network The table shows the lengths of pipes (metres) connecting the 6 vats.
A B C D E F
A - 7 - - 12 -
B 7 - 5 3 6 6
C - 5 - 8 4 7
D - 3 8 - 1 5
E 12 6 4 1 - 7
F - 6 7 5 7 -
Use Kruskal's algorithm to find a minimum connector. Show the order in which you select pipes, draw your connector and give its total length.
Produce a new table excluding the pipes which you selected in part (i). Use the tabular form of Prim's algorithm to find a second minimum connector from this reduced set of pipes. Show your working, draw your connector and give its total length.
The factory manager prefers the following pair of connectors: $\{ \mathrm { AB } , \mathrm { BC } , \mathrm { BD } , \mathrm { BE } , \mathrm { BF } \}$ and $\{ \mathrm { AE } , \mathrm { BF } , \mathrm { CE } , \mathrm { DE } , \mathrm { DF } \}$.
Give two possible reasons for this preference.

OCR MEI D1 2013 June Q1

8 marks Moderate -0.8

1 The adjacency graph for a map has a vertex for each country. Two vertices are connected by an arc if the corresponding countries share a border.

Draw the adjacency graph for the following map of four countries. The graph is planar and you should draw it with no arcs crossing. \includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-2_531_1486_561_292}
Number the regions of your planar graph, including the outside region. Regarding the graph as a map, draw its adjacency graph.
Repeat parts (i) and (ii) for the following map. \includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-2_533_1484_1361_294}

OCR MEI D1 2013 June Q2

8 marks Easy -1.8

2 The instructions labelled 1 to 7 describe the steps of a sorting algorithm applied to a list of six numbers.
1 Let $i$ equal 1.
2 Repeat lines 3 to 7, stopping when $i$ becomes 6 .

OCR MEI D1 2013 June Q3

8 marks Easy -1.8

3 Let $j$ equal 1.

OCR MEI D1 2013 June Q4

16 marks Easy -1.8

4 Repeat lines 5 and 6 , until $j$ becomes $7 - i$.

OCR MEI D1 2013 June Q5

16 marks Easy -1.8

5 If the $j$ th number in the list is bigger than the $( j + 1 )$ th, then swap them.

OCR MEI D1 2013 June Q6

16 marks Easy -1.8

6 Let the new value of $j$ be $j + 1$.

OCR MEI D1 2013 June Q7

Moderate -0.8

7 Let the new value of $i$ be $i + 1$.

Apply the sorting algorithm to the list of numbers shown below. Record in the table provided the state of the list after each pass. Record the number of comparisons and the number of swaps that you make in each pass. (The result of the first pass has already been recorded.) List: $\begin{array} { l l l l l l } 9 & 11 & 7 & 3 & 13 & 5 \end{array}$
Suppose now that the list is split into two sublists, $\{ 9,11,7 \}$ and $\{ 3,13,5 \}$. The sorting algorithm is adapted to apply to three numbers, and is applied to each sublist separately. This gives $\{ 7,9,11 \}$ and $\{ 3,5,13 \}$. How many comparisons and swaps does this need?
How many further swaps would the original algorithm need to sort the revised list $\{ 7,9,11,3,5,13 \}$ into increasing order? 3 The network below represents a number of villages together with connecting roads. The numbers on the arcs represent distances (in miles). \includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-3_684_785_1612_625}
Use Dijkstra's algorithm to find the shortest routes from A to each of the other villages. Give these shortest routes and the corresponding distances. Traffic in the area travels at 30 mph . An accident delays all traffic passing through C by 20 minutes.
Describe how the network can be adapted and used to find the fastest journey time from A to F .

AQA D2 Q4

Standard +0.3

4 [Figures 3, 4 and 5, printed on the insert, are provided for use in this question.]
The network shows a system of pipes, with the lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-005_547_1214_555_404}

Figure 3, on the insert, shows a partially completed diagram for a feasible flow of 10 litres per second from $S$ to $T$. Indicate, on Figure 3, the flows along the edges $M N , P Q , N P$ and $N T$.
1. Taking your answer from part (a) as an initial flow, use flow augmentation on Figure 4 to find the maximum flow from $S$ to $T$.
2. State the value of the maximum flow and illustrate this flow on Figure 5.
Find a cut with capacity equal to that of the maximum flow.

AQA D2 Q7

Moderate -0.3

7 The network below shows a system of one-way roads. The number on each edge represents the number of bags for recycling that can be collected by driving along that road. A collector is to drive from $A$ to $I$. \includegraphics[max width=\textwidth, alt={}, center]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-144_867_1644_552_191}

Working backwards from $\boldsymbol { I }$, use dynamic programming to find the maximum number of bags that can be collected when driving from $A$ to $I$. You must complete the table opposite as your solution.
State the route that the collector should take in order to collect the maximum number of bags.
Stage State From Value
1 G I
H I
2

AQA D2 Q8

Moderate -0.3

8 The network below represents a system of pipes. The capacity of each pipe, in litres per second, is indicated on the corresponding edge. \includegraphics[max width=\textwidth, alt={}, center]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-146_743_977_404_536}

Find the maximum flow along each of the routes $A B E H , A C F H$ and $A D G H$ and enter their values in the table on Figure 4 opposite.
1. Taking your answers to part (a) as the initial flow, use the labelling procedure on Figure 4 to find the maximum flow through the network. You should indicate any flow-augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
2. State the value of the maximum flow and, on Figure 5 opposite, illustrate a possible flow along each edge corresponding to this maximum flow.
Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut. \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Figure 4}
Route Flow
$A B E H$
$A C F H$
$A D G H$
\end{table} \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-147_746_972_397_845}
\end{figure} \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-147_739_971_1311_539}
\end{figure}

AQA D2 2006 January Q1

9 marks Moderate -0.5

1 Five trainers, Ali, Bo, Chas, Dee and Eve, held an initial training session with each of four teams over an assault course. The completion times in minutes are recorded below.

	Ali	Bo	Chas	Dee	Eve
Team 1	16	19	18	25	24
Team 2	22	21	20	26	25
Team 3	21	22	23	21	24
Team 4	20	21	21	23	20

Each of the four teams is to be allocated a trainer and the overall time for the four teams is to be minimised. No trainer can train more than one team.

Modify the table of values by adding an extra row of values so that the Hungarian algorithm can be applied.
Use the Hungarian algorithm, reducing columns first then rows, to decide which four trainers should be allocated to which team. State the minimum total training time for the four teams using this matching.

AQA D2 2006 January Q2

9 marks Moderate -0.8

2 A manufacturing company is planning to build three new machines, $A , B$ and $C$, at the rate of one per month. The order in which they are built is a matter of choice, but the profits will vary according to the number of workers available and the suppliers' costs. The expected profits in thousands of pounds are given in the table.

\multirow[b]{2}{*}{Month}	\multirow[b]{2}{*}{Already built}	Profit (in units of £1000)
		$\boldsymbol { A }$	$\boldsymbol { B }$	$\boldsymbol { C }$
1	-	52	47	48
\multirow[t]{3}{*}{2}	A	-	58	54
	B	70	-	54
	$\boldsymbol { C }$	68	63	-
\multirow[t]{3}{*}{3}	$\boldsymbol { A }$ and $\boldsymbol { B }$	-	-	64
	$\boldsymbol { A }$ and $\boldsymbol { C }$	-	67	-
	$\boldsymbol { B }$ and $\boldsymbol { C }$	69	-	-

Draw a labelled network such that the most profitable order of manufacture corresponds to the longest path within that network.
Use dynamic programming to determine the order of manufacture that maximises the total profit, and state this maximum profit.

AQA D2 2006 January Q3

18 marks Moderate -0.3

3 [Figures 1 and 2, printed on the insert, are provided for use in this question.] A building project is to be undertaken. The table shows the activities involved.

Activity	Immediate Predecessors	Duration (days)	Number of Workers Required
A	-	2	3
B	A	4	2
C	A	6	1
D	$B , C$	8	3
E	C	3	2
F	D	2	2
G	D, E	4	2
H	D, E	6	1
I	$F , G , H$	2	3

Complete the activity network for the project on Figure 1.
Find the earliest start time for each activity.
Find the latest finish time for each activity.
Find the critical path and state the minimum time for completion.
State the float time for each non-critical activity.
Given that each activity starts as early as possible, draw a resource histogram for the project on Figure 2.
There are only 3 workers available at any time. Use resource levelling to explain why the project will overrun and state the minimum extra time required.

AQA D2 2006 January Q4

14 marks Standard +0.3

4 [Figures 3, 4 and 5, printed on the insert, are provided for use in this question.]
The network shows a system of pipes, with the lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{30a88efe-fe9e-4384-a3e3-da2a05326797-04_547_1214_555_404}

Figure 3, on the insert, shows a partially completed diagram for a feasible flow of 10 litres per second from $S$ to $T$. Indicate, on Figure 3, the flows along the edges $M N , P Q , N P$ and $N T$.
1. Taking your answer from part (a) as an initial flow, use flow augmentation on Figure 4 to find the maximum flow from $S$ to $T$.
2. State the value of the maximum flow and illustrate this flow on Figure 5.
Find a cut with capacity equal to that of the maximum flow.

AQA D2 2006 January Q5

13 marks Standard +0.3

5

Display the following linear programming problem in a Simplex tableau. $$\begin{array} { l c } \text { Maximise } & P = 3 x + 2 y + 4 z \\ \text { subject to } & x + 4 y + 2 z \leqslant 8 \\ & 2 x + 7 y + 3 z \leqslant 21 \\ & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
Use the Simplex method to perform one iteration of your tableau for part (a), choosing a value in the $z$-column as pivot.
1. Perform one further iteration.
2. State whether or not this is the optimal solution, and give a reason for your answer.

AQA D2 2006 January Q6

11 marks Moderate -0.8

6 Sam is playing a computer game in which he is trying to drive a car in different road conditions. He chooses a car and the computer decides the road conditions. The points scored by Sam are shown in the table.

		Road Conditions
\cline { 2 - 5 }		$\boldsymbol { C } _ { \mathbf { 1 } }$	$\boldsymbol { C } _ { \mathbf { 2 } }$	$\boldsymbol { C } _ { \mathbf { 3 } }$
\cline { 2 - 5 }	$\boldsymbol { S } _ { \mathbf { 1 } }$	- 2	2	4
\cline { 2 - 5 } Sam's Car	$\boldsymbol { S } _ { \mathbf { 2 } }$	2	4	5
\cline { 2 - 5 }	$\boldsymbol { S } _ { \mathbf { 3 } }$	5	1	2
\cline { 2 - 5 }
\cline { 2 - 5 }

Sam is trying to maximise his total points and the computer is trying to stop him.

Explain why Sam should never choose $S _ { 1 }$ and why the computer should not choose $C _ { 3 }$.
Find the play-safe strategies for the reduced 2 by 2 game for Sam and the computer, and hence show that this game does not have a stable solution.
Sam uses random numbers to choose $S _ { 2 }$ with probability $p$ and $S _ { 3 }$ with probability $1 - p$.
1. Find expressions for the expected gain for Sam when the computer chooses each of its two remaining strategies.
2. Calculate the value of $p$ for Sam to maximise his total points.
3. Hence find the expected points gain for Sam.
  Surname Other Names
  Centre Number Candidate Number
  Candidate Signature
  \section*{General Certificate of Education January 2006
  Advanced Level Examination} \section*{MATHEMATICS
  Unit Decision 2} MD02 \section*{Insert} Wednesday 18 January 20061.30 pm to 3.00 pm Insert for use in Questions 3 and 4.
  Fill in the boxes at the top of this page.
  Fasten this insert securely to your answer book.

AQA D2 2007 January Q1

11 marks Easy -1.2

1 [Figure 1, printed on the insert, is provided for use in this question.]
A building project is to be undertaken. The table shows the activities involved.

Activity	Immediate Predecessors	Duration (weeks)
A	-	2
B	-	1
C	A	3
D	A, B	2
E	B	4
F	C	1
G	$C , D , E$	3
H	E	5
I	$F , G$	2
J	$H , I$	3

Complete an activity network for the project on Figure 1.
Find the earliest start time for each activity.
Find the latest finish time for each activity.
State the minimum completion time for the building project and identify the critical paths.

Route	Flow
\(A B E H\)
\(A C F H\)
\(A D G H\)

Questions (30179 questions)

Browse by module

Browse by board

AQA D1 2016 June Q5

AQA D1 2016 June Q6

AQA D1 2016 June Q7

AQA D1 2016 June Q8

OCR MEI D1 2007 January Q1

OCR MEI D1 2007 January Q3

OCR MEI D1 2007 January Q5

OCR MEI D1 2007 January Q7

OCR MEI D1 2013 June Q1

OCR MEI D1 2013 June Q2

OCR MEI D1 2013 June Q3

OCR MEI D1 2013 June Q4

OCR MEI D1 2013 June Q5

OCR MEI D1 2013 June Q6

OCR MEI D1 2013 June Q7

AQA D2 Q4

AQA D2 Q7

AQA D2 Q8

AQA D2 2006 January Q1

AQA D2 2006 January Q2

AQA D2 2006 January Q3

AQA D2 2006 January Q4

AQA D2 2006 January Q5

AQA D2 2006 January Q6

AQA D2 2007 January Q1

	\(\boldsymbol { P }\)	\(\boldsymbol { Q }\)	\(\boldsymbol { R }\)	\(\boldsymbol { S }\)	\(\boldsymbol { T }\)	\(\boldsymbol { U }\)
\(\boldsymbol { P }\)	-	14	7	11	6	12
\(\boldsymbol { Q }\)	14	-	8	10	9	10
\(\boldsymbol { R }\)	7	8	-	12	13	15
\(\boldsymbol { S }\)	11	10	12	-	5	11
\(\boldsymbol { T }\)	6	9	13	5	-	10
\(\boldsymbol { U }\)	12	10	15	11	10	-

	\(\boldsymbol { P }\)	\(Q\)	\(\boldsymbol { R }\)	\(\boldsymbol { S }\)	\(T\)	\(\boldsymbol { U }\)	\(V\)
\(\boldsymbol { P }\)	-	14	7	11	6	12	15
\(Q\)	14	-	8	10	9	10	18
\(\boldsymbol { R }\)	7	8	-	12	13	15	14
\(\boldsymbol { S }\)	11	10	12	-	5	11	14
\(T\)	6	9	13	5	-	10	17
\(\boldsymbol { U }\)	12	10	15	11	10	-	12
\(V\)	15	18	14	14	17	12	-

		Road Conditions
\cline { 2 - 5 }		\(\boldsymbol { C } _ { \mathbf { 1 } }\)	\(\boldsymbol { C } _ { \mathbf { 2 } }\)	\(\boldsymbol { C } _ { \mathbf { 3 } }\)
\cline { 2 - 5 }	\(\boldsymbol { S } _ { \mathbf { 1 } }\)	- 2	2	4
\cline { 2 - 5 } Sam's Car	\(\boldsymbol { S } _ { \mathbf { 2 } }\)	2	4	5
\cline { 2 - 5 }	\(\boldsymbol { S } _ { \mathbf { 3 } }\)	5	1	2
\cline { 2 - 5 }
\cline { 2 - 5 }

Stage	State	From	Value
1	G	I
	H	I

2

Activity	Immediate Predecessors	Duration (weeks)
A	-	2
B	-	1
C	A	3
D	A, B	2
E	B	4
F	C	1
G	\(C , D , E\)	3
H	E	5
I	\(F , G\)	2
J	\(H , I\)	3