Questions D1 - A-Level Maths

Apply Dijkstra's algorithm to the network, starting at $A$, to find the shortest route from $A$ to $H$.
Write down the shortest route from $A$ to $E$ and the shortest route from $A$ to $G$. Sheng-Li needs to travel along every street to deliver leaflets. He will start and finish at $A$.
Explain why Sheng-Li will need to repeat some streets.
Showing your working, find the length of the shortest route that Sheng-Li can take, starting and ending at $A$, to deliver leaflets to every street. The streets have houses on both sides. Sheng-Li does not want to keep crossing the streets from one side to the other. His friend Nadia offers to help him. They decide that they will work together and set off from $A$, with Sheng-Li delivering to one side of $A B$ and Nadia delivering to the other side. Each street will have to be travelled along twice, either by both of them travelling along it once or by one of them travelling along it twice. Nadia and Sheng-Li travel $A - B - C - E$. At this point Sheng-Li is called back to $A$. He travels along $E - C - A$, delivering leaflets on one side of $C A$. Nadia completes the leaflet delivery on her own.
Calculate the minimum distance that Nadia will need to travel on her own to complete the delivery. Explain how your answer was achieved and how you know that it is the minimum possible distance.
[0pt] [4]

OCR D1 2015 June Q6

6 The Devil's Dice are four cubes with faces coloured green, yellow, blue or red.
Cube 1 has three green faces and one each of yellow, blue and red.

Two of the green faces are opposite one another.
The other green face is opposite the yellow face.
The blue face is opposite the red face.

This information is represented using the graph in Fig. 1. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Cube 1} \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-08_359_330_685_957}

\end{figure} Fig. 1

Cube 2 has a green face opposite a blue face, another green face opposite a red face and a second red face opposite a yellow face. Draw a graph to represent this information. The graph in Fig. 2 represents opposite faces in cube 3. Cube 3 \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-08_350_326_1398_986} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure}
How many yellow faces does cube 3 have? Cube 4 has one green face, two yellow faces, one blue face and two red faces. The graph in Fig. 3 is an incomplete representation of opposite faces in cube 4 . \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Cube 4} \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-08_257_273_2115_1018}
\end{figure} Fig. 3
Complete the graph in your answer book. The Devil's Dice puzzle requires the cubes to be stacked to form a tower so that each long face of the tower uses all four colours. The puzzle can be solved using graph theory. First the graphs representing the opposite faces of the four cubes are combined into a single graph. The edges of the graph are labelled $1,2,3$ or 4 to show which cube they belong to. The labelled graph in Fig. 4 shows cube 1 and cube 3 together. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-09_630_689_625_689} \captionsetup{labelformat=empty} \caption{Fig. 4}
\end{figure}
Complete the copy of the labelled graph in your answer book to show all four cubes. A subgraph is a graph contained within a given graph.
From the graph representing all four cubes a subgraph needs to be found that will represent the front and back faces of the tower. Each face of the tower uses each colour once. This means that the graph representing the front and back faces must be a subgraph of the answer to part (iv) with four edges labelled $1,2,3$ and 4 and four nodes each having order two.
Explain why if the loop labelled 1 joining G to G is used, it is not possible to form a subgraph with four edges labelled 1, 2, 3 and 4 and nodes each having order two. Suppose that the edge labelled 1 that joins B and R is used.
Draw a subgraph that has the required properties and uses the edge labelled 1 that joins B and R .
Using your answer to part (vi), show the two possible colourings of the back of the tower.

OCR D1 2016 June Q1

1 The arc weights for a network on a complete graph with six vertices are given in the following table.

	A	B	$C$	D	E	$F$
A	-	5	7	9	8	12
B	5	-	4	6	5	10
C	7	4	-	7	6	8
D	9	6	7	-	5	10
E	8	5	6	5	-	10
F	12	10	8	10	10	-

Apply Prim's algorithm to the table in the Printed Answer Book. Start by crossing out the row for $A$ and choosing an entry from the column for $A$. Write down the arcs used in the order that they are chosen. Draw the resulting minimum spanning tree and give its total weight.

OCR D1 2016 June Q2

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

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

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

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

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

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

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

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

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

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

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

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

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
- This insert should be used to answer Questions 4, 5 and 6
- .
- Write your Name, Centre Number and Candidate Number in the spaces provided at the top of this page.
- Write your answers to Questions 4, 5 and 6
- in the spaces provided in this insert, and attach it to your answer booklet.
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 MEI D1 Q1

14 marks

1 The bipartite graph in Fig. 1 represents a board game for two players. At each turn a player tosses a coin and moves their counter. The graph shows which square the counter is moved to if the coin shows heads, and which square if it shows tails. Each player starts with their counter on square 1. Play continues until one player gets their counter to square 9 and wins. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-002_723_1287_569_425} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure}

Draw a tree to show all of the possibilities for the player's first three moves.
Show how a player can win in 3 turns.
List all squares which it is possible for a counter to occupy after 3 turns.
Show that a game can continue indefinitely.

OCR MEI D1 Q3

12 marks

3 The following algorithm finds the highest common factor of two positive integers. ("int (x)" stands for the integer part of x, e.g. int (7.8) = 7.) \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-004_888_693_422_717} \captionsetup{labelformat=empty} \caption{Fig. 3.1}

\end{figure}

Run the algorithm with $\mathrm { A } = 84$ and $\mathrm { B } = 660$, showing all of your calculations.
Run the algorithm with $\mathrm { A } = 660$ and $\mathrm { B } = 84$, showing as many calculations as are necessary.
The algorithm is run with $\mathrm { A } = 30$ and $\mathrm { B } = 42$, and the result is shown in Table 3.2 below. \begin{table}[h]
A B Q R 1 R 2
30 42 1 12
12 30 2 6
6
6 12 2 0
\captionsetup{labelformat=empty} \caption{Print 6}
\end{table} Table 3.2 The first line of the table shows that $12 = 42 - 1 \times 30$.
Use the second line to obtain a similar expression for 6 in terms of 30 and 12.
Hence express 6 in the form $\mathrm { m } \times 30 - \mathrm { n } \times 42$, where m and n are integers.

OCR MEI D1 2005 January Q1

\includegraphics[alt={},max width=\textwidth]{b9ee9306-18ca-42b3-9f2e-b23849374b5e-2_723_1287_569_425} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure}

Draw a tree to show all of the possibilities for the player's first three moves.
Show how a player can win in 3 turns.
List all squares which it is possible for a counter to occupy after 3 turns.
Show that a game can continue indefinitely.

OCR MEI D1 2005 January Q3

3 The following algorithm finds the highest common factor of two positive integers. ("int (x)" stands for the integer part of x, e.g. int (7.8) = 7.) \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{b9ee9306-18ca-42b3-9f2e-b23849374b5e-4_888_693_422_717} \captionsetup{labelformat=empty} \caption{Fig. 3.1}

\end{figure}

Run the algorithm with $\mathrm { A } = 84$ and $\mathrm { B } = 660$, showing all of your calculations.
Run the algorithm with $\mathrm { A } = 660$ and $\mathrm { B } = 84$, showing as many calculations as are necessary.
The algorithm is run with $\mathrm { A } = 30$ and $\mathrm { B } = 42$, and the result is shown in Table 3.2 below. \begin{table}[h]
A B Q R 1 R 2
30 42 1 12
12 30 2 6
6
6 12 2 0
\captionsetup{labelformat=empty} \caption{Print 6}
\end{table} Table 3.2 The first line of the table shows that $12 = 42 - 1 \times 30$.
Use the second line to obtain a similar expression for 6 in terms of 30 and 12.
Hence express 6 in the form $\mathrm { m } \times 30 - \mathrm { n } \times 42$, where m and n are integers.

OCR MEI D1 2005 January Q5

5 There is an insert for use in parts (iii) and (iv) of this question.
This question concerns the simulation of cars passing through two sets of pedestrian controlled traffic lights. The time intervals between cars arriving at the first set of lights are distributed according to Table 5.1. \begin{table}[h]

Time interval (seconds)	2	5	15	25
Probability	$\frac { 3 } { 7 }$	$\frac { 2 } { 7 }$	$\frac { 1 } { 7 }$	$\frac { 1 } { 7 }$

\captionsetup{labelformat=empty} \caption{Table 5.1}

\end{table}

Give an efficient rule for using two-digit random numbers to simulate arrival intervals.
Use two-digit random numbers from the list below to simulate the arrival times of five cars at the first lights. The first car arrives at the time given by the first arrival interval. Random numbers: $24,01,99,89,77,19,58,42$ The two sets of traffic lights are 23 seconds driving time apart. Moving cars are always at least 2 seconds apart. If there is a queue at a set of lights, then when the red light ends the first car in the queue moves off immediately, the second car 2 seconds later, the third 2 seconds after that, etc. In this simple model there is to be no consideration of accelerations or decelerations, and the lights are either red or green. Table 5.2 shows the times when the lights are red. \begin{table}[h]
\multirow{2}{*}{
first set
of lights
} red start time 14 50 105 155
\cline { 2 - 6 } red end time 29 65 120 170
\multirow{2}{*}{
second set
of lights
} red start time 10 55 105 150
\cline { 2 - 6 } red end time 25 70 120 165
\captionsetup{labelformat=empty} \caption{Table 5.2}
\end{table}
Complete the table in the insert to simulate the passage of 10 cars through both sets of traffic lights. Use the arrival times given there.
Find the mean delay experienced by these cars in passing through each set of lights.
How could the output from this simulation model be made more reliable?

OCR MEI D1 2005 January Q6

6 A recipe for jam states that the weight of sugar used must be between the weight of fruit used and four thirds of the weight of fruit used. Georgia has 10 kg of fruit available and 11 kg of sugar.

Define two variables and formulate inequalities in those variables to model this information.
Draw a graph to represent your inequalities.
Find the vertices of your feasible region and identify the points which would represent the best mix of ingredients under each of the following circumstances.
(A) There is to be as much jam as possible, given that the weight of jam produced is the sum of the weights of the fruit and the sugar.
(B) There is to be as much jam as possible, given that it is to have the lowest possible proportion of sugar.
(C) There is to be as much jam as possible, given that it is to have the highest possible proportion of sugar.
(D) Fruit costs $\pounds 1$ per kg, sugar costs 50 p per kg and the objective is to produce as much jam as possible within a budget of $\pounds 15$.

OCR MEI D1 2006 January Q1

1 Table 1 shows a precedence table for a project. \begin{table}[h]

Activity	Immediate predecessors	Duration (days)
A	-	5
B	-	3
C	A	3
D	A, B	4
E	A, B	5

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

\end{table}

Draw an activity-on-arc network to represent the precedences.
Find the early event time and late event time for each vertex of your network, and list the critical activities.
Extra resources become available which enable the durations of three activities to be reduced, each by up to two days. Which three activities should have their durations reduced so as to minimise the completion time of the project? What will be the new minimum project completion time?

OCR MEI D1 2006 January Q3

3 Fig. 3 shows a graph representing the seven bus journeys run each day between four rural towns. Each directed arc represents a single bus journey. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{ee39642f-f323-4614-a02a-4500199626de-4_317_515_392_772} \captionsetup{labelformat=empty} \caption{Fig. 3}

\end{figure}

Show that if there is only one bus, which is in service at all times, then it must start at one town and end at a different town. Give the start town and the end town.
Show that there is only one Hamilton cycle in the graph. Show that, if an extra journey is added from your end town to your start town, then there is still only one Hamilton cycle.
A tourist is staying in town B. Give a route for her to visit every town by bus, visiting each town only once and returning to B . Section B (48 marks)

OCR MEI D1 2006 January Q4

4 Table 4 shows the butter and sugar content in two recipes. The first recipe is for 1 kg of toffee and the second is for 1 kg of fudge. \begin{table}[h] \section*{Table 6.1} (ii) Specify an efficient rule for using one-digit random numbers to simulate the time taken at the till by customers purchasing fuel. Table 6.2 shows the distribution of time taken at the till by customers who are not buying fuel.

Time taken (mins)	1	1.5	2	2.5	3
Probability	$\frac { 1 } { 7 }$	$\frac { 2 } { 7 }$	$\frac { 2 } { 7 }$	$\frac { 1 } { 7 }$	$\frac { 1 } { 7 }$

\section*{Table 6.2} (iii) Specify an efficient rule for using two-digit random numbers to simulate the time taken at the till by customers not buying fuel. What is the advantage in using two-digit random numbers instead of one-digit random numbers in this part of the question? The table in the insert shows a partially completed simulation study of 10 customers arriving at the till.
(iv) Complete the table using the random numbers which are provided.
(v) Calculate the mean total time spent queuing and paying.

\(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

Time taken (mins)	1	1.5	2	2.5	3
Probability	\(\frac { 1 } { 7 }\)	\(\frac { 2 } { 7 }\)	\(\frac { 2 } { 7 }\)	\(\frac { 1 } { 7 }\)	\(\frac { 1 } { 7 }\)

	A	B	\(C\)	D	E	\(F\)
A	-	5	7	9	8	12
B	5	-	4	6	5	10
C	7	4	-	7	6	8
D	9	6	7	-	5	10
E	8	5	6	5	-	10
F	12	10	8	10	10	-

	\(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	-

Time interval (seconds)	2	5	15	25
Probability	\(\frac { 3 } { 7 }\)	\(\frac { 2 } { 7 }\)	\(\frac { 1 } { 7 }\)	\(\frac { 1 } { 7 }\)

\(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

Questions D1 (899 questions)

Browse by module

Browse by board

OCR D1 2015 June Q5

OCR D1 2015 June Q6

OCR D1 2016 June Q1

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 MEI D1 Q1

OCR MEI D1 Q3

OCR MEI D1 2005 January Q1

OCR MEI D1 2005 January Q3

OCR MEI D1 2005 January Q5

OCR MEI D1 2005 January Q6

OCR MEI D1 2006 January Q1

OCR MEI D1 2006 January Q3

OCR MEI D1 2006 January Q4