Questions - OCR Further Discrete

		Card X	Card Y	Card Z
	Card P	$( 4,4 )$	$( 5,9 )$	$( 1,7 )$
\multirow[t]{2}{*}{Alix}	Card Q	$( 3,5 )$	$( 4,1 )$	$( 8,2 )$
	Card R	$( x , y )$	$( 2,2 )$	$( 9,4 )$

\end{table}

Explain why the table cannot be reduced through dominance no matter what values $x$ and $y$ have.
Show that the game is not stable no matter what values $x$ and $y$ have.
Find the Nash equilibrium solutions for the various values that $x$ and $y$ can have. \section*{OCR} \section*{Oxford Cambridge and RSA}

OCR Further Discrete 2018 September Q1

1 The design for the lines on a playing area for a game is shown below. The letters are not part of the design.
\includegraphics[max width=\textwidth, alt={}, center]{22571082-016b-409b-bfeb-e7ebf48ccac7-2_350_855_388_605} Priya paints the lines by pushing a machine. When she is pushing the machine she is about a metre behind the point being painted. She must not duplicate any line by painting it twice.

To relocate the machine, it must be stopped and then started again to continue painting the lines.
When the machine is being relocated it must still be pushed along the lines of the design, and not 'cut across' on a diagonal for example.
The machine can be turned through $90 ^ { \circ }$ without having to be stopped.
1. What is the minimum number of times that the machine will need to be started to paint the design?

The design is horizontally and vertically symmetric. $$\mathrm { AB } = 6 \text { metres, } \mathrm { AE } = 26 \text { metres, } \mathrm { AF } = 1.5 \text { metres and } \mathrm { AS } = 9 \text { metres. }$$

(a) Find the minimum distance that Priya needs to walk to paint the design. You should show enough working to make your reasoning clear but you do not need to use an algorithmic method.
(b) Why, in practice, will the distance be greater than this?
(c) What additional information would you need to calculate a more accurate shortest distance?

OCR Further Discrete 2018 September Q2

2 A list is used to demonstrate how different sorting algorithms work.
After two passes through shuttle sort the resulting list is $$\begin{array} { l l l l l l l } 17 & 23 & 84 & 21 & 66 & 35 & 12 \end{array}$$

How many different possibilities are there for the original list? Suppose, instead, that the same sort was carried out using bubble sort on the original list.
Write down the list after two passes through bubble sort. The number of comparisons made is used as a measure of the run-time for a sorting algorithm.
For a list of six values, what is the maximum total number of comparisons made in the first two passes of
(a) shuttle sort
(b) bubble sort? Steve used both shuttle sort and bubble sort on a list of five values. He says that shuttle sort is more efficient than bubble sort because it made fewer comparisons in the first two passes.
Comment on what Steve said. The number of comparisons made when shuttle sort and bubble sort are used to sort every permutation of a list of four values is shown in the table below.
Number of comparisons 3 4 5 6
Shuttle sort Number of permutations 2 6 8 8
Bubble sort Number of permutations 1 0 7 16
Use the information in the table to decide which algorithm you would expect to have the quicker run-time. Justify your answer with calculations.

OCR Further Discrete 2018 September Q3

3 The pay-off matrix for a zero-sum game is

	X	Y	Z
\cline { 2 - 4 } A	- 2	1	0
\cline { 2 - 4 } B	3	5	- 3
\cline { 2 - 4 } C	- 4	- 2	2
\cline { 2 - 4 } D	0	2	- 1
\cline { 2 - 4 }
\cline { 2 - 4 }

Show that the game does not have a stable solution.
Use a graphical technique to find the optimal mixed strategy for the player on columns.
Formulate an initial simplex tableau for the problem of finding the optimal mixed strategy for the player on rows.

OCR Further Discrete 2018 September Q4

4 A project is represented by the activity network below. The times are in days.
\includegraphics[max width=\textwidth, alt={}, center]{22571082-016b-409b-bfeb-e7ebf48ccac7-4_384_935_1110_566}

Explain the reason for each dummy activity.
Calculate the early and late event times.
Identify the critical activities.
Calculate the independent float and interfering float on activity A .
(a) Draw a cascade chart to represent the project, using the grid in the Printed Answer Booklet.
(b) Describe the effect on
- the project completion
- the critical activities
  if the duration of activity D is increased by 5 days.
The number of workers needed for each activity is shown below.
Activity A B C D E F G H
Workers 2 1 1 2 1 1 1 1
The project needs to be completed in at most 3 weeks ( 21 days).
The duration of activity D is 9 days.
Find the minimum number of workers needed. You should explain your reasoning carefully.

OCR Further Discrete 2018 September Q5

5 Consider the problem given below: $$\begin{array} { l l } \text { Minimise } & 4 \mathrm { AB } + 7 \mathrm { AC } + 8 \mathrm { BD } + 5 \mathrm { CD } + 5 \mathrm { CE } + 6 \mathrm { DF } + 3 \mathrm { EF }
\text { subject to } & \mathrm { AB } , \mathrm { AC } , \mathrm { BD } , \mathrm { CD } , \mathrm { CE } , \mathrm { DF } \text { and } \mathrm { EF } \text { are each either } 0 \text { or } 1
& \mathrm { AB } + \mathrm { AC } + \mathrm { BD } + \mathrm { CD } + \mathrm { CE } + \mathrm { DF } + \mathrm { EF } = 5
& \mathrm { AB } + \mathrm { AC } \geqslant 1 , \quad \mathrm { AB } + \mathrm { BD } \geqslant 1 , \quad \mathrm { AC } + \mathrm { CD } + \mathrm { CE } \geqslant 1 ,
& \mathrm { BD } + \mathrm { CD } + \mathrm { DF } \geqslant 1 , \quad \mathrm { CE } + \mathrm { EF } \geqslant 1 , \quad \mathrm { DF } + \mathrm { EF } \geqslant 1 \end{array}$$

Explain why this is not a standard LP formulation that could be set up as a Simplex tabulation. The variables $\mathrm { AB } , \mathrm { AC } , \ldots$ correspond to arcs in a network. The weight on each arc is the coefficient of the corresponding variable in the objective function.
Draw the network on the vertices in the Printed Answer Booklet. A variable that takes the value 1 corresponds to an arc that is used in the solution and a variable with the value 0 corresponds to an arc that is not used in the solution.
Explain what is ensured by the constraint $\mathrm { AB } + \mathrm { AC } \geqslant 1$. Julie claims that the solution to the problem will give the minimum spanning tree for the network.
Find the minimum spanning tree for the network.
- State the algorithm you have used.
- Show your method clearly.
- Draw the tree.
- State the total weight of the tree.
- Find the solution to the problem given at the start of the question.
- You do not need to use a formal method.
- Draw the arcs in the solution.
- State the minimum value of the objective function.
Kim has a different network, exactly one of the arcs in this network is a directed arc.
Kim wants to find a minimum weight set of arcs such that it is possible to get from any vertex to any other vertex.
Explain why, if Kim's problem has a solution, the directed arc cannot be part of it.

OCR Further Discrete 2018 September Q6

6 Kai mixes hot drinks using coffee and steamed milk.
The amounts ( ml ) needed and profit ( $\pounds$ ) for a standard sized cup of four different drinks are given in the table. The table also shows the amount of the ingredients available.

Type of drink	Coffee	Foamed milk	Profit
w Americano	80	0	1.20
$x$ Cappuccino	60	120	X
$y$ Flat White	60	100	1.40
$z$ Latte	40	120	1.50
Available	900	1500

Kai makes the equivalent of $w$ standard sized americanos, $x$ standard sized cappuccinos, $y$ standard sized flat whites and $z$ standard sized lattes. He can make different sized drinks so $w , x , y , z$ need not be integers. Kai wants to find the maximum profit that he can make, assuming that the customers want to buy the drinks he has made.

What is the minimum value of X for it to be worthwhile for Kai to make cappuccinos? Kai makes no cappuccinos.
Use the simplex algorithm to solve Kai's problem. The grids in the Printed Answer Booklet should have at least enough rows and columns and there should be at least enough grids to show all the iterations needed. Only record the output from each iteration, not any intermediate stages.
Interpret the solution and state the maximum profit that Kai can make.

OCR Further Discrete 2018 September Q7

7 A simply connected graph has 6 vertices and 10 arcs.

What is the maximum vertex degree? You are now given that the graph is also Eulerian.
Explaining your reasoning carefully, show that exactly two of the vertices have degree 2 .
Prove that the vertices of degree 2 cannot be adjacent to one another.
Use Kuratowski's theorem to show that the graph is planar.
Show that it is possible to make a non-planar graph by the addition of one more arc. A digraph is created from a simply connected graph with 6 vertices and $10 \operatorname { arcs }$ by making each arc into a single directed arc.
What can be deduced about the indegrees and outdegrees?
If a Hamiltonian cycle exists on the digraph, what can be deduced about the indegrees and outdegrees? \section*{OCR} \section*{Oxford Cambridge and RSA}

OCR Further Discrete 2018 December Q1

1 Arif and Bindiya play a game as follows.

They each secretly choose a positive integer from $\{ 2,3,4,5 \}$.
They then reveal their choices. Let Arif's choice be $A$ and Bindiya's choice be $B$.
If $A ^ { B } \geqslant B ^ { A }$, Arif wins $B$ points and Bindiya wins $- 4 - B$ points.
If $A ^ { B } < B ^ { A }$, Arif wins $- 4 - A$ points and Bindiya wins $A$ points.
1. Assuming that each of the 16 possible outcomes is equally likely to be chosen, show that the average amount won by Arif is 0 .
2. 1. Describe how to convert this game to a zero-sum game.
  2. Construct the pay-off matrix for this zero-sum game, with Arif on rows.

OCR Further Discrete 2018 December Q2

2 Two simply connected graphs are shown below. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{10ca0bf1-beaa-4460-8f28-08f0e4e44d5c-02_307_584_1151_301} \captionsetup{labelformat=empty} \caption{Graph 1}

\end{figure} \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{10ca0bf1-beaa-4460-8f28-08f0e4e44d5c-02_307_584_1151_1178} \captionsetup{labelformat=empty} \caption{Graph 2}

\end{figure}

1. Write down the orders of the vertices for each of these graphs.
2. How many ways are there to allocate these vertex degrees to a graph with vertices $\mathrm { P } , \mathrm { Q }$, $\mathrm { R } , \mathrm { S } , \mathrm { T }$ and U ?
3. Use the vertex degrees to deduce whether the graphs are Eulerian, semi-Eulerian or neither.
Show that graphs 1 and 2 are not isomorphic.
1. Write down a Hamiltonian cycle for graph 1.
2. Use Euler's formula to determine the number of regions for graph 1.
3. Identify each of these regions for graph 1 by listing the cycle that forms its boundary.

OCR Further Discrete 2018 December Q3

3 A set of ten cards have the following values:
$\begin{array} { l l l l l l l l l l } 13 & 8 & 4 & 20 & 12 & 15 & 3 & 2 & 10 & 8 \end{array}$ Kerenza wonders if there is a set of these cards with a total of exactly 50 .

Which type of problem (existence, construction, enumeration or optimisation) is this? The five cards $4,8,8,10$ and 20 have a total of 50.
How many ways are there to arrange three of these five cards (with the two 8 s being indistinguishable) so that the total of the numbers on the first two cards is less than the number on the third card?
How many ways are there to select (choose) three of the five cards so that the total of the numbers on the three cards is less than 25 ?
Show how quicksort works by using it to sort the original list of ten cards into increasing order.
You should indicate the pivots used and which values are already known to be in their correct position.

OCR Further Discrete 2018 December Q4

4 An algorithm is represented by the flow diagram below.
\includegraphics[max width=\textwidth, alt={}, center]{10ca0bf1-beaa-4460-8f28-08f0e4e44d5c-04_1871_1719_293_173} The algorithm is applied with $n = 4$ and the table of inputs $\mathrm { d } ( i , j )$ : $$j = 1 \quad j = 2 \quad j = 3 \quad j = 4$$ $$\begin{aligned} & i = 1
& i = 2
& i = 3
& i = 4 \end{aligned}$$

0	3	5	2
3	0	4	3
5	4	0	1
2	3	1	0

An incomplete trace through the algorithm is shown below.

$n$	$i$	$j$	$\mathrm { d } ( i , j )$	A	$t$	$m$
4
					1
	1
				1		100
		1
			0
		2
			3
					2	3
		3
			5
		4
			2
					4	2
	4
				1, 4		100
		1
			2
		2
			3
					2	3
		3
			1
					3	1
		4
			0

The next box to be used is the box 'Let $i = t$ '.

Complete the trace in the Printed Answer Booklet. The table of inputs represents a weighted matrix for a network, where the weights represent distances.
1. State how the output of the algorithm relates to the network represented by the matrix.
2. How can the list A be used in the solution of the travelling salesperson problem on the network represented by the matrix?
3. Write down a limitation on the distances $\mathrm { d } ( i , j )$ for this algorithm.
Explain why the algorithm is finite for any table of inputs. Suppose that, for a problem with $n$ vertices, the run-time for the algorithm is given by $\alpha D + \beta T$, where $\alpha$ and $\beta$ are constants, $D$ is the number of times that a value of $\mathrm { d } ( i , j )$ is looked up and $T$ is the number of times that $t$ is updated.
Show how this means that the algorithm has $\mathrm { O } \left( n ^ { 2 } \right)$ complexity. A computer takes 3 seconds to run the algorithm for a problem with $n = 35$.
Use the complexity to calculate an approximate run-time for a problem with $n = 100$. The run-time using a second algorithm has $\mathrm { O } ( n ! )$ complexity.
A computer takes 2.8 seconds to run the second algorithm for a problem with $n = 35$.
Without performing any further calculations, give a reason why the first algorithm is likely to be more efficient than the second for a problem with $n = 100$.

OCR Further Discrete 2018 December Q5

5 A rapid transport system connects 8 stations using three railway lines.
The blue line connects A to B to C to D .

From	to	Travel time
A	B	5
B	C	3
C	D	9

The red line connects $B$ to $F$ to $E$ to $D$.

From	to	Travel time
B	F	2
F	E	3
E	D	2

The green line connects E to G to H to A .

From	to	Travel time
E	G	5
G	H	6
H	A	4

The travel times for the return journeys are the same as for the outward journeys (so, for example, the travel time from B to A is 5 minutes, the same as the time from A to B ).
All travel times include time spent stopped at stations.
No trains are delayed so the travel times are all correct.
1. (i) Model the blue, red and green lines, and the travel times above, as a network.
  (ii) Use Dijkstra's algorithm to find the quickest travel times from C to each of the other stations.
2. 1. Write down a route from A to D with travel time 12 minutes.
  2. Construct a table of quickest travel times.
3. Give a reason why the quickest journey from A to D may take longer than 12 minutes.

OCR Further Discrete 2018 December Q6

6 Jack is making pizzas for a party. He can make three types of pizza:

	Suitable for vegans	Suitable for vegetarians	Suitable for meat eaters
Type X			✓
Type Y		✓	✓
Type Z	✓	✓	✓

There is enough dough to make 30 pizzas.
Type Z pizzas use vegan cheese. Jack only has enough vegan cheese to make 2 type Z pizzas.
At least half the pizzas made must be suitable for vegetarians.
Jack has enough onions to make 50 type X pizzas or 20 type Y pizzas or 20 type Z pizzas or some mixture of the three types.

Suppose that Jack makes $x$ type X pizzas, $y$ type Y pizzas and $z$ type Z pizzas.

Formulate the constraints above in terms of the non-negative, integer valued variables $x , y$ and $z$, together with non-negative slack variables $s , t , u$ and $v$. Jack wants to find out the maximum total number of pizzas that he can make.

Set up an initial simplex tableau for Jack's problem.

Carry out one iteration of the simplex algorithm, choosing your pivot so that $x$ becomes a basic variable. When Jack carries out the simplex algorithm his final tableau is:

$P$	$x$	$y$	$z$	$s$	$t$	$u$	$v$	RHS
1	0	0	0	0	0	$\frac { 3 } { 7 }$	$\frac { 2 } { 7 }$	$28 \frac { 4 } { 7 }$
0	0	0	0	1	0	$- \frac { 3 } { 7 }$	$- \frac { 2 } { 7 }$	$1 \frac { 3 } { 7 }$
0	0	0	1	0	1	0	0	2
0	1	0	0	0	0	$\frac { 5 } { 7 }$	$\frac { 1 } { 7 }$	$14 \frac { 2 } { 7 }$
0	0	1	1	0	0	$- \frac { 2 } { 7 }$	$\frac { 1 } { 7 }$	$14 \frac { 2 } { 7 }$

Use this final tableau to deduce how many pizzas of each type Jack should make. Jack knows that some of the guests are vegans. He decides to make 2 pizzas of type $Z$.
1. Plot the feasible region for $x$ and $y$.
2. Complete the branch-and-bound formulation in the Printed Answer Booklet to find the number of pizzas of each type that Jack should make.
  You should branch on $x$ first. \section*{END OF QUESTION PAPER}

OCR Further Discrete 2017 Specimen Q1

1 Fiona is a mobile hairdresser. One day she needs to visit five clients, A to E, starting and finishing at her own house at F . She wants to find a suitable route that does not involve her driving too far.

Which standard network problem does Fiona need to solve? The shortest distances between clients, in km, are given in the matrix below.
A B C D E
A - 12 8 6 4
B 12 - 10 8 10
C 8 10 - 13 10
D 6 8 13 - 10
E 4 10 10 10 -
Use the copy of the matrix in the Printed Answer Booklet to construct a minimum spanning tree for these five client locations.
State the algorithm you have used, show the order in which you build your tree and give its total weight. Draw your minimum spanning tree. The distance from Fiona's house to each client, in km, is given in the table below.
A B C D E
F 2 11 9 7 5
Use this information together with your answer to part (ii) to find a lower bound for the length of Fiona's route.
(a) Find all the cycles that result from using the nearest neighbour method, starting at F .
(b) Use these to find an upper bound for the length of Fiona's route.
Fiona wants to drive less than 35 km . Using the information in your answers to parts (iii) and (iv) explain whether or not a route exists which is less than 35 km in length.

OCR Further Discrete 2017 Specimen Q2

2 Kirstie has bought a house that she is planning to renovate. She has broken the project into a list of activities and constructed an activity network, using activity on arc.

Activity
$A$	Structural survey
$B$	Replace damp course
$C$	Scaffolding
$D$	Repair brickwork
$E$	Repair roof
$F$	Check electrics
$G$	Replaster walls

Activity
$H$	Planning
$I$	Build extension
$J$	Remodel internal layout
$K$	Kitchens and bathrooms
$L$	Decoration and furnishing
$M$	Landscape garden

\includegraphics[max width=\textwidth, alt={}, center]{27438ff9-40d5-415e-b054-2007ea4dd6b8-03_876_1739_1037_212}

Construct a cascade chart for the project, showing the float for each non-critical activity.
Calculate the float for remodelling the internal layout stating how much of this is independent float and how much is interfering float. Kirstie needs to supervise the project. This means that she cannot allow more than three activities to happen on any day.
Describe how Kirstie should organise the activities so that the project is completed in the minimum project completion time and no more than three activities happen on any day.

OCR Further Discrete 2017 Specimen Q4

4 The table shows the pay-off matrix for player $A$ in a two-person zero-sum game between $A$ and $B$. \begin{table}[h]

\captionsetup{labelformat=empty} \caption{Player $A$}

	Strategy $X$	Strategy $Y$	Strategy $Z$
Strategy $P$	4	5	- 4
Strategy $Q$	3	- 1	2
Strategy $R$	4	0	2

\end{table}

Find the play-safe strategy for player $A$ and the play-safe strategy for player $B$. Use the values of the play-safe strategies to determine whether the game is stable or unstable.
If player $B$ knows that player $A$ will use their play-safe strategy, which strategy should player $B$ use?
Suppose that the value in the cell where both players use their play-safe strategies can be changed, but all other entries are unchanged. Show that there is no way to change this value that would make the game stable.
Suppose, instead, that the value in one cell can be changed, but all other entries are unchanged, so that the game becomes stable. Identify a suitable cell and write down a new pay-off value for that cell which would make the game stable.
Show that the zero-sum game with the new pay-off value found in part (iv) has a Nash equilibrium and explain what this means for the players.

		Card X	Card Y	Card Z
	Card P	\(( 4,4 )\)	\(( 5,9 )\)	\(( 1,7 )\)
\multirow[t]{2}{*}{Alix}	Card Q	\(( 3,5 )\)	\(( 4,1 )\)	\(( 8,2 )\)
	Card R	\(( x , y )\)	\(( 2,2 )\)	\(( 9,4 )\)

\(n\)	\(i\)	\(j\)	\(\mathrm { d } ( i , j )\)	A	\(t\)	\(m\)
4
					1
	1
				1		100
		1
			0
		2
			3
					2	3
		3
			5
		4
			2
					4	2
	4
				1, 4		100
		1
			2
		2
			3
					2	3
		3
			1
					3	1
		4
			0

\(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	\(v\)	RHS
1	0	0	0	0	0	\(\frac { 3 } { 7 }\)	\(\frac { 2 } { 7 }\)	\(28 \frac { 4 } { 7 }\)
0	0	0	0	1	0	\(- \frac { 3 } { 7 }\)	\(- \frac { 2 } { 7 }\)	\(1 \frac { 3 } { 7 }\)
0	0	0	1	0	1	0	0	2
0	1	0	0	0	0	\(\frac { 5 } { 7 }\)	\(\frac { 1 } { 7 }\)	\(14 \frac { 2 } { 7 }\)
0	0	1	1	0	0	\(- \frac { 2 } { 7 }\)	\(\frac { 1 } { 7 }\)	\(14 \frac { 2 } { 7 }\)

	Strategy \(X\)	Strategy \(Y\)	Strategy \(Z\)
Strategy \(P\)	4	5	- 4
Strategy \(Q\)	3	- 1	2
Strategy \(R\)	4	0	2

	Number of comparisons	3	4	5	6
Shuttle sort	Number of permutations	2	6	8	8
Bubble sort	Number of permutations	1	0	7	16

Activity
\(A\)	Structural survey
\(B\)	Replace damp course
\(C\)	Scaffolding
\(D\)	Repair brickwork
\(E\)	Repair roof
\(F\)	Check electrics
\(G\)	Replaster walls

Activity
\(H\)	Planning
\(I\)	Build extension
\(J\)	Remodel internal layout
\(K\)	Kitchens and bathrooms
\(L\)	Decoration and furnishing
\(M\)	Landscape garden

Activity	A	B	C	D	E	F	G	H
Workers	2	1	1	2	1	1	1	1

Questions — OCR Further Discrete (67 questions)

Browse by module

Browse by board

OCR Further Discrete 2018 March Q7

OCR Further Discrete 2018 September Q1

OCR Further Discrete 2018 September Q2

OCR Further Discrete 2018 September Q3

OCR Further Discrete 2018 September Q4

OCR Further Discrete 2018 September Q5

OCR Further Discrete 2018 September Q6

OCR Further Discrete 2018 September Q7

OCR Further Discrete 2018 December Q1

OCR Further Discrete 2018 December Q2

OCR Further Discrete 2018 December Q3

OCR Further Discrete 2018 December Q4

OCR Further Discrete 2018 December Q5

OCR Further Discrete 2018 December Q6

OCR Further Discrete 2017 Specimen Q1

OCR Further Discrete 2017 Specimen Q2

OCR Further Discrete 2017 Specimen Q4