Questions — OCR (4619 questions)

Browse by module
All questions AEA AS Paper 1 AS Paper 2 AS Pure C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Extra Pure Further Mechanics Further Mechanics A AS Further Mechanics AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics Further Paper 4 Further Pure Core Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Pure with Technology Further Statistics Further Statistics A AS Further Statistics AS Further Statistics B AS Further Statistics Major Further Statistics Minor Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 H240/01 H240/02 H240/03 M1 M2 M3 M4 M5 Mechanics 1 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pure 1 S1 S2 S3 S4 Stats 1 Unit 1 Unit 2 Unit 3 Unit 4
Browse by board
AQA AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Paper 1 Further Paper 2 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics M1 M2 M3 Paper 1 Paper 2 Paper 3 S1 S2 S3 CAIE FP1 FP2 Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 4 M1 M2 P1 P2 P3 S1 S2 Edexcel AEA AS Paper 1 AS Paper 2 C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 OCR AS Pure C1 C2 C3 C4 D1 D2 FD1 AS FM1 AS FP1 FP1 AS FP2 FP3 FS1 AS Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Mechanics Further Mechanics AS Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Statistics Further Statistics AS H240/01 H240/02 H240/03 M1 M2 M3 M4 Mechanics 1 PURE Pure 1 S1 S2 S3 S4 Stats 1 OCR MEI AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further Extra Pure Further Mechanics A AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Pure Core Further Pure Core AS Further Pure with Technology Further Statistics A AS Further Statistics B AS Further Statistics Major Further Statistics Minor M1 M2 M3 M4 Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 WJEC Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 Unit 1 Unit 2 Unit 3 Unit 4
Sort by: Default | Easiest first | Hardest first
OCR Further Discrete 2022 June Q3
8 marks Challenging +1.2
3 A para relay team of 4 swimmers needs to be chosen from a group of 7 swimmers.
  1. How many ways are there to choose 4 swimmers from 7? There are no restrictions on how many men and how many women are in the team. The group of 7 swimmers consists of 5 men and 2 women.
  2. How many ways are there to choose a team with more men than women? The physical impairment of each swimmer is given a score.
    The scores for the swimmers are
    \(\begin{array} { l l l l l l l } 3 & 4 & 4 & 6 & 7 & 8 & 9 \end{array}\) The total score for the team must be 20 or less.
  3. How many different valid teams are possible? The order of the swimmers in the team is now taken into consideration.
  4. In total, how many different arrangements are there of valid teams?
  5. In how many of these valid teams are the scores of the swimmers in increasing order? For example, 3, 4, 4, 8 but not 4, 3, 4, 8 .
OCR Further Discrete 2022 June Q4
13 marks Challenging +1.2
4 A connected graph is shown below.
\includegraphics[max width=\textwidth, alt={}, center]{50697293-6cdc-475f-981f-71a351b0ff5a-4_442_954_296_246}
  1. Write down a path through exactly 7 of the vertices.
  2. Write down a cycle through exactly 6 of the vertices.
  3. Explain why Ore's theorem cannot be used to decide whether or not this graph is Hamiltonian.
  4. Prove that the graph is not Hamiltonian. The following colouring algorithm can be used to determine whether a connected graph is bipartite or not. The algorithm colours each vertex of a graph in one of two colours, (1) and (2). STEP 1 Choose a vertex and assign it colour (1).
    STEP 2 If any vertex is adjacent to another vertex of the same colour, stop. Otherwise assign colour (2) to each vertex that is adjacent to a vertex with colour (1).
    STEP 3 If any vertex is adjacent to another vertex of the same colour, stop. Otherwise assign colour (1) to each vertex that is adjacent to a vertex with colour (2).
    STEP 4 Repeat STEP 2 and STEP 3 until all vertices are coloured.
    STEP 5 If there are no adjacent vertices of the same colour then the graph is bipartite, output the word "bipartite".
    Otherwise the graph is not bipartite, output the words "not bipartite".
  5. Use this algorithm, starting at vertex A, to determine whether the graph is bipartite, or not. [2
  6. Explain what Kuratowski's theorem tells you about the graph.
  7. Show that the graph has thickness 2 .
OCR Further Discrete 2022 June Q5
12 marks Standard +0.8
5 In each turn of a game between two players they simultaneously each choose a strategy and then calculate the points won using the table below. They are each trying to maximise the number of points that they win. In each cell the first value is the number of points won by player 1 and the second value is the number of points won by player 2 .
\multirow{2}{*}{}Player 2
XYZ
\multirow{3}{*}{Player 1}A\(( 6,0 )\)\(( 1,7 )\)\(( 5,6 )\)
B\(( 9,4 )\)\(( 2,6 )\)\(( 8,1 )\)
C\(( 6,8 )\)\(( 1,3 )\)\(( 7,2 )\)
  1. Find the play-safe strategy for each player.
  2. Explain why player 2 would never choose strategy Z .
  3. Find the Nash equilibrium solution(s) or show that there is no Nash equilibrium solution. Player 2 chooses strategy X with probability \(p\) and strategy Y with probability \(1 - p\). You are given that when player 1 chooses strategy A, the expected number of points won by each player is the same.
    1. Calculate the value of \(p\).
    2. Determine which player expects to win the greater number of points when player 1 chooses strategy B.
OCR Further Discrete 2022 June Q6
15 marks Standard +0.3
6 A linear programming problem is
Maximise \(\mathrm { P } = 2 \mathrm { x } - \mathrm { y }\)
subject to $$\begin{aligned} 3 x + y - 4 z & \leqslant 24 \\ 5 x - 3 z & \leqslant 60 \\ - x + 2 y + 3 z & \leqslant 12 \end{aligned}$$ and \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\)
    1. Represent this problem as an initial simplex tableau.
    2. Carry out one iteration of the simplex algorithm. After two iterations the resulting tableau is
      \(P\)\(x\)\(y\)\(z\)\(s\)\(t\)\(u\)RHS
      10\(\frac { 5 } { 11 }\)0\(- \frac { 6 } { 11 }\)\(\frac { 8 } { 11 }\)0\(30 \frac { 6 } { 11 }\)
      01\(- \frac { 3 } { 11 }\)0\(- \frac { 3 } { 11 }\)\(\frac { 4 } { 11 }\)0\(15 \frac { 3 } { 11 }\)
      00\(- \frac { 5 } { 11 }\)1\(- \frac { 5 } { 11 }\)\(\frac { 3 } { 11 }\)0\(5 \frac { 5 } { 11 }\)
      00\(\frac { 34 } { 11 }\)0\(\frac { 12 } { 11 }\)\(- \frac { 5 } { 11 }\)1\(10 \frac { 10 } { 11 }\)
    1. Write down the basic variables after two iterations.
    2. Write down the exact values of the basic feasible solution for \(x , y\) and \(z\) after two iterations.
    3. State what you can deduce about the optimal value of the objective for the original problem. You are now given that, in addition to the constraints above, \(\mathrm { x } + \mathrm { y } + \mathrm { z } = 9\).
  3. Use the additional constraint to rewrite the original constraints in terms of \(x\) and \(y\) but not \(z\).
  4. Explain why the simplex algorithm cannot be applied to this new problem without some modification.
OCR Further Discrete 2022 June Q7
12 marks Challenging +1.2
7 A building has 7 CCTV cameras, A to G, at the junctions of some of the corridors.
The cameras at the junctions and the lengths of the 11 corridors between them, in metres, are shown in the table below.
ABCDEFG
A6460111
B6472103
C606658
D111726632127
E1033282
F5812775
G8275
  1. Model this information as a network.
  2. Use an appropriate algorithm to calculate the minimum distance from A to each of the other vertices. The run-time of an algorithm for finding this minimum distance is proportional to the total number of comparisons used. For a network with \(n\) vertices, the worst case is when the algorithm is applied to a network based on the complete graph \(\mathrm { K } _ { n }\). In each pass
    • A vertex is made permanent and the temporary label at all adjacent vertices that are not yet permanent are updated. This uses 1 comparison for every such vertex (adjacent to the permanent label) that previously already had a temporary label.
    • The best temporary labels at all vertices that do not yet have permanent labels are then compared to determine the next vertex to become permanent. If there are \(k\) such vertices this involves \(k - 1\) comparisons.
    • By considering the number of comparisons of each type in each iteration, show that the algorithm uses a total of 6 comparisons when it is applied to a network based on the complete graph \(\mathrm { K } _ { 4 }\).
    You are given that the total number of comparisons used when the algorithm is applied to a network based on \(\mathrm { K } _ { n }\) is \(( n - 1 ) ( n - 2 )\). A computer takes 0.03 seconds to apply this algorithm on a network based on \(\mathrm { K } _ { 7 }\).
  3. Calculate, to \(\mathbf { 1 }\) decimal place, how many seconds it will take the computer to apply the algorithm to a network based on \(\mathrm { K } _ { 70 }\). \section*{Question 7 continues on the next page} The manager wants to construct a tour (a closed route) that passes each camera.
    1. Find a lower bound for the length of this tour by initially deleting D .
    2. Find an upper bound for the length of this tour by using the nearest neighbour algorithm starting from D.
    3. Deduce the length of the shortest possible tour. Briefly explain your reasoning. \section*{END OF QUESTION PAPER}
OCR Further Discrete 2023 June Q1
7 marks Moderate -0.5
1 The table below shows the activities involved in a project together with the immediate predecessors and the duration of each activity.
ActivityImmediate predecessorsDuration (hours)
A-2
BA3
C-4
DC2
EB, C2
FD, E3
GE2
HF, G1
  1. Model the project using an activity network.
  2. Determine the minimum project completion time. The start of activity C is delayed by 2 hours.
  3. Determine the minimum project completion time with this delay.
OCR Further Discrete 2023 June Q2
8 marks Challenging +1.8
2 A graph is shown below.
\includegraphics[max width=\textwidth, alt={}, center]{c4755464-aa15-4720-8f33-5eb7169f4a20-2_522_810_1637_246}
  1. Write down a cycle through all six vertices.
  2. Write down a continuous route that uses every arc exactly once.
  3. Use Kuratowski's theorem to show that the graph is not planar.
  4. Show that the graph has thickness 2 .
OCR Further Discrete 2023 June Q3
12 marks Standard +0.3
3 An initial simplex tableau is given below.
\(P\)\(x\)\(y\)\(z\)\(s\)\(t\)RHS
1- 23- 1000
05- 411020
02- 10016
  1. Carry out two iterations of the simplex algorithm, choosing the first pivot from the \(x\) column. After three iterations the resulting tableau is as follows.
    \(P\)\(x\)\(y\)\(z\)\(s\)\(t\)RHS
    13- 101020
    05- 411020
    02- 10016
  2. State the values of \(P , x , y , z , s\) and \(t\) that result from these three iterations.
  3. Explain why no further iterations are possible. The initial simplex tableau is changed to the following, where \(k\) is a positive real value.
    \(P\)\(x\)\(y\)\(z\)\(s\)\(t\)RHS
    12- 31000
    05\(k\)11020
    02- 10016
    After one iteration of the simplex algorithm the value of \(P\) is 500 .
  4. Deduce the value of \(k\).
OCR Further Discrete 2023 June Q4
10 marks Challenging +1.2
4 The first 20 consecutive positive integers include the 8 prime numbers \(2,3,5,7,11,13,17\) and 19. Emma randomly chooses 5 distinct numbers from the first 20 consecutive positive integers. The order in which Emma chooses the numbers does not matter.
  1. Calculate the number of possibilities in which Emma's 5 numbers include exactly 2 prime numbers and 3 non-prime numbers.
  2. Calculate the number of possibilities in which Emma's 5 numbers include at least 2 prime numbers. The pairs \(\{ 3,13 \}\) and \(\{ 7,17 \}\) each consist of numbers with a difference of exactly 10 .
  3. Calculate the number of possibilities in which Emma's 5 numbers include at least one pair of prime numbers in which the difference between them is exactly 10 . A new set of 20 consecutive positive integers, each with at least two digits, is chosen. This set of 20 numbers contains 5 prime numbers.
  4. Use the pigeonhole principle to show that there is at least one pair of these prime numbers for which the difference between them is exactly 10 .
OCR Further Discrete 2023 June Q5
12 marks Moderate -0.5
5 A list of 8 values is given below.
324814203018
The list is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
  1. Carry out the first two passes of the sort. A different list of 8 values is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
    1. State the maximum number of passes that could be required.
    2. Find the minimum number of passes that could be required. The run-time for quick sort could be measured by counting the number of comparisons used. In the worst case, the run time for quick sort is \(\mathrm { O } \left( n ^ { 2 } \right)\). A computer takes at most 0.03 seconds to sort a list of 100 values into increasing order using quick sort.
  3. Calculate an estimate for the time taken, in the worst case, to sort a list of 500 values using quick sort. A list of \(n\) values (where \(n > 10\) ) is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
  4. Explain why, in the best case, \(n - 3\) comparisons are used in the second pass.
OCR Further Discrete 2023 June Q6
14 marks Standard +0.3
6 A graph is shown in Fig. 1.1.
The graph is weighted to form the network represented by the weighted matrix in Fig. 1.2. The weights represent distances in km.
A dash (-) means that there is no direct arc between that pair of vertices. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Fig. 1.1} \includegraphics[alt={},max width=\textwidth]{c4755464-aa15-4720-8f33-5eb7169f4a20-6_439_728_557_248}
\end{figure} \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Fig. 1.2}
ABCDEF
A-5328-
B5-3476
C33-165
D241---
E876--6
F-65-6-
\end{table} The shortest path from D to F has total weight 6.
  1. Write down a path from D to F of total weight 6. The total weight of the 12 arcs in the network is 56.
  2. Use the route inspection algorithm to calculate the total weight of the least weight route that covers every arc at least once, starting at vertex A.
  3. Determine the total weight of the least weight route that covers every arc at least once, starting at vertex B but finishing at any vertex. Sasha wants to find a continuous route through every vertex, starting and finishing at vertex A, with the least total weight.
    1. Use an appropriate algorithm to find a lower bound for the total weight of Sasha's route.
    2. Use the Nearest Neighbour Algorithm, starting at vertex A, to find an upper bound for the total weight of Sasha's route. Sasha decides to use the route \(A - B - F - E - C - D - A\).
  5. Comment on the suitability of this route as a solution to Sasha's problem.
OCR Further Discrete 2023 June Q7
12 marks Challenging +1.8
7 Player 1 and player 2 are playing a two-person zero-sum game.
In each round of the game the players each choose a strategy and simultaneously reveal their choice. The number of points won in each round by player 1 for each combination of strategies is shown in the table below. Each player is trying to maximise the number of points that they win.
Player 2 Player 1
ABC
X2- 3- 4
Y013
Z- 224
    1. Determine play-safe strategies for each player.
    2. Show that the game is not stable.
  2. Show that the number of strategies available to player 1 cannot be reduced by dominance. You must make it clear which values are being compared. Player 1 intends to make a random choice between strategies \(\mathrm { X } , \mathrm { Y } , \mathrm { Z }\), choosing strategy X with probability \(x\), strategy Y with probability \(y\) and strategy Z with probability \(z\).
    Player 1 formulates the following LP problem so they can find the optimal values of \(x , y\) and \(z\) using the simplex algorithm. Maximise \(M = m - 4\)
    subject to \(m \leqslant 6 x + 4 y + 2 z\) $$\begin{aligned} & m \leqslant x + 5 y + 6 z \\ & m \leqslant 7 y + 8 z \\ & x + y + z \leqslant 1 \end{aligned}$$ and \(m \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0\)
  3. Explain how the inequality \(m \leqslant 6 x + 4 y + 2 z\) was formed. The problem is solved by running the simplex algorithm on a computer.
    The printout gives a solution in which \(\mathrm { x } + \mathrm { y } = 1\).
    This means that the LP problem can be reduced to the following formulation.
    Maximise \(M = m - 4\)
    subject to \(m \leqslant 4 + 2 x\)
    \(\mathrm { m } \leqslant 5 - 4 \mathrm { x }\)
    \(m \leqslant 7 - 7 x\)
    and \(m \geqslant 0 , x \geqslant 0\)
  4. Solve this problem to find the optimal values of \(x , y\) and \(z\) and the corresponding value of the game to player 1.
OCR Further Discrete 2024 June Q1
7 marks Standard +0.3
1 At the end of each year the workers at an office take part in a gift exchange.
Each worker randomly chooses the name of one other worker and buys a small gift for that person. Each worker's name is chosen by exactly one of the others.
A worker cannot choose their own name. In the first year there were four workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D .
There are 9 ways in which A, B, C and D can choose the names for the gift exchange. One of these is already given in the table in the Printed Answer Booklet.
  1. Complete the table in the Printed Answer Booklet to show the remaining 8 ways in which the names can be chosen. During the second year, worker D left and was replaced with worker E.
    The organiser of the gift exchange wants to know whether it is possible for the event to happen for another 3 years (starting with the second year) with none of the workers choosing a name they have chosen before, assuming that there are no further changes in the workers.
  2. Classify the organiser's problem as an existence, construction, enumeration or optimisation problem. After the second year, the organiser drew a graph showing who each worker chose in the first two years of the gift exchange.
    None of the workers chose the same name in the first and second years.
    The vertices of the graph represented the workers, A, B, C, D and E, and the arcs showed who had been chosen by each worker.
  3. Explain why the graph must be a digraph.
  4. State the number of arcs in the digraph that shows the choices for the first two years.
  5. Assuming that the digraph created in part (d) is planar, use Euler's formula to calculate how many regions it has.
OCR Further Discrete 2024 June Q2
9 marks Standard +0.3
2 A linear programming problem is Maximise \(\mathrm { P } = 2 \mathrm { x } - \mathrm { y } + \mathrm { z }\)
subject to
\(3 x - 4 y - z \leqslant 30\)
\(x - y \leqslant 6\)
\(x - 3 y + 2 z \geqslant - 2\)
and \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\)
  1. Complete the table in the Printed Answer Booklet to represent the problem as an initial simplex tableau.
  2. Carry out one iteration of the simplex algorithm.
  3. State the values of \(x , y\) and \(z\) that result from your iteration. After two iterations the resulting tableau is
    \(P\)\(x\)\(y\)\(z\)\(s\)\(t\)\(u\)RHS
    100-202.50.516
    000-21-2.50.516
    010-101.50.510
    001-100.50.54
    The boundaries of the feasible region are planes, with edges each defined by two of \(x , y , z , s , t , u\) being zero.
    At each vertex of the feasible region there are three basic variables and three non-basic variables.
  4. Interpret the second iteration geometrically by stating which edge of the feasible region is being moved along. As part of your geometrical interpretation, you should state the beginning vertex and end vertex of the second iteration.
OCR Further Discrete 2024 June Q3
9 marks Challenging +1.8
3 Amir and Beth play a zero-sum game.
The table shows the pay-off for Amir for each combination of strategies, where these values are known. \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Beth}
XYZ
\cline { 3 - 5 } AmirP2- 3\(c\)
\cline { 3 - 5 }Q- 3\(b\)4
\cline { 3 - 5 }R\(a\)- 1- 2
\cline { 3 - 5 }
\cline { 3 - 5 }
\end{table} You are given that \(\mathrm { a } < 0 < \mathrm { b } < \mathrm { c }\).
Amir's play-safe strategy is R.
  1. Determine the range of possible values of \(a\). Beth's play-safe strategy is Y.
  2. Determine the range of possible values of \(b\).
  3. Determine whether or not the game is stable.
OCR Further Discrete 2024 June Q4
16 marks Moderate -0.3
4 A project is represented by the activity network below. The activity durations are given in hours.
\includegraphics[max width=\textwidth, alt={}, center]{f20391b2-e3c1-4021-9a87-47fd4ea7c490-5_346_1033_351_244}
  1. By carrying out a forward pass, determine the minimum project completion time.
  2. By carrying out a backward pass, determine the (total) float for each activity.
  3. For each non-critical activity, determine the independent float and the interfering float.
  4. Construct a cascade chart showing all the critical activities on one row and each non-critical activity on a separate row, starting at its earliest start time, and using dashed lines to indicate (total) float. You may not need to use all the grid. Each activity requires exactly one worker.
  5. Construct a schedule to show how exactly two workers can complete the project as quickly as possible. You may not need to use all the grid. Issues with deliveries delay the earliest possible start of activity D by 3 hours.
  6. Construct a schedule to show how exactly two workers can complete the project with this delay as quickly as possible. You may not need to use all the grid.
OCR Further Discrete 2024 June Q5
18 marks Moderate -0.3
5
  1. Write down a way in which the nearest neighbour method can fail to solve the problem of finding a least weight cycle through all the vertices of a network.
  2. Explain why, when trying to find a least weight cycle through all the vertices of a network, an ad hoc method may be preferable to an algorithmic approach. The distance matrix below represents a network connecting six viewpoints \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F . The distance matrix shows the direct distances between each pair of viewpoints where a direct route exists.
    The distances are measured in km.
    A blank shows that there is no direct route between the two viewpoints.
    ABCDEF
    A64
    B6529
    C51576
    D42155
    E975
    F6
  3. Draw the network on the vertices given in the Printed Answer Booklet.
  4. Apply the nearest neighbour method, starting from A. A hiker wants to travel between the six viewpoints, starting and finishing at A.
    The hiker must visit every viewpoint at least once, but may visit a viewpoint more than once.
  5. Show that the hiker does not need to travel as far as 50 km .
  6. Use an appropriate algorithm to find the shortest distance from F to each of the other viewpoints.
  7. Complete the table in the Printed Answer Book to show the shortest distance between each pair of viewpoints.
  8. Use your answer to part (g) to find a lower bound for the distance the hiker must travel by initially deleting vertex A.
OCR Further Discrete 2024 June Q6
16 marks Challenging +1.2
6 Sasha is making three identical bead bracelets using amber, brown and red coloured beads. Sasha has 20 amber beads, 12 brown beads and 10 red beads. Each bracelet must use exactly 12 beads.
The profit from selling a bracelet is 6 pence for each amber bead used plus 2 pence for each brown bead used plus 3 pence for each red bead used. Sasha wants to maximise the total profit from selling the three bracelets.
  1. Express Sasha's problem as a linear programming formulation in two variables \(a\) and \(b\), where \(a\) represents the number of amber beads in each bracelet and \(b\) represents the number of brown beads in each bracelet.
  2. Determine how many beads of each colour will be used in each bracelet.
  3. By listing all the feasible solutions, identify an aspect of the optimal solution, other than the profit, that is different from all the other feasible solutions. The beads that are not used in making the bracelets can be sold. The profit from selling each amber bead is \(k\) pence, where \(k\) is an integer, but nothing for each brown or red bead sold. All the previous constraints still apply. Instead of maximising the profit from the bracelets, Sasha wants to maximise the total profit from selling the bracelets and any left over beads. You are given that the optimal solution to the earlier problem does not maximise the total profit from selling the bracelets and any left over beads.
  4. Determine the least possible value of Sasha’s maximum total profit.
  5. Why might Sasha not achieve this maximum profit?
OCR Further Discrete 2020 November Q1
9 marks Challenging +1.2
1 This question is about the planar graph shown below.
\includegraphics[max width=\textwidth, alt={}, center]{cc58fb7a-efb6-4548-a8e1-e40abe1eb722-2_567_1317_395_374}
    1. Apply Kuratowski's theorem to verify that the graph is planar.
    2. Use Euler's formula to calculate the number of regions in a planar representation of the graph.
    1. Write down a Hamiltonian cycle for the graph.
    2. By finding a suitable pair of vertices, show that Ore's theorem cannot be used to prove that the graph, as shown above, is Hamiltonian.
    1. Draw the graph formed by using the contractions AB and CF .
    2. Use Ore's theorem to show that this contracted graph is Hamiltonian.
OCR Further Discrete 2020 November Q2
14 marks Challenging +1.2
2 Annie and Brett play a two-person, simultaneous play game. The table shows the pay-offs for Annie and Brett in the form ( \(a , b\) ). So, for example, if Annie plays strategy K and Brett plays strategy S, Annie wins 2 points and Brett wins 6 points.
Brett
RST
\cline { 3 - 5 } \multirow{3}{*}{Annie}K\(( 7,3 )\)\(( 2,6 )\)\(( 5,3 )\)
\cline { 3 - 5 }L\(( 1,5 )\)\(( 8,2 )\)\(( 2,5 )\)
\cline { 3 - 5 }M\(( 3,2 )\)\(( 1,5 )\)\(( 4,6 )\)
\cline { 3 - 5 }
\cline { 3 - 5 }
    1. Determine the play-safe strategy for Annie.
    2. Show that the play-safe strategy for Brett is T.
    1. If Annie knows that Brett is planning on playing strategy T, which strategy should Annie play to maximise her points?
    2. If Brett knows that Annie is planning on playing the strategy identified in part (b)(i), which strategy should Brett play to maximise his points?
  3. Show that, for Brett, strategy R is weakly dominated.
  4. Using a graphical method, determine the optimal mixed strategy for Brett.
  5. Show that the game has no Nash equilibrium points.
OCR Further Discrete 2020 November Q3
12 marks Standard +0.3
3 An initial simplex tableau is shown below.
\(P\)\(x\)\(y\)\(z\)\(s\)\(t\)RHS
1-310000
02011018
0-1230120
  1. Write down the objective for the problem that is represented by this initial tableau. Variables \(s\) and \(t\) are slack variables.
  2. Use the final row of the initial tableau to explain what a slack variable is.
  3. Carry out one iteration of the simplex algorithm and hence:
    • give the pivot column used and the value of the pivot element
    • write down the value of \(P\) after this iteration
    • find the values of \(x , y\) and \(z\) after this iteration
    • describe the effect of the iteration geometrically.
OCR Further Discrete 2020 November Q4
10 marks Challenging +1.2
4
  1. Show that there are 127 ways to partition a set of 8 distinct elements into two non-empty subsets. A group of 8 people ( \(\mathrm { A } , \mathrm { B } , \ldots\) ) have 8 reserved seats ( \(1,2 , \ldots\) ) on a coach. Seat 1 is reserved for person A , seat 2 for person B , and so on. The reserved seats are labelled but the individual people do not know which seat has been reserved for them. The first 4 people, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , choose their seats at random from the 8 reserved seats.
  2. Determine how many different arrangements there are for the seats chosen by \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D . The group organiser moves \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D to their correct seats (A in seat \(1 , \mathrm {~B}\) in seat \(2 , \mathrm { C }\) in seat 3 and D in seat 4).
    The other 4 people ( \(\mathrm { E } , \mathrm { F } , \mathrm { G }\) and H ) then choose their seats at random from the remaining 4 reserved seats ( \(5,6,7\) and 8 ).
  3. List the 9 derangements of \(\{ \mathrm { E } , \mathrm { F } , \mathrm { G } , \mathrm { H } \}\), where none of these four people is in the seat that has been reserved for them. Suppose, instead, that the 8 people had chosen their seats at random from the 8 reserved seats, without the organiser intervening.
  4. Determine the total number of ways in which the seats can be chosen so that 4 of the people are in their correct seats and 4 are not in their correct seats.
OCR Further Discrete 2020 November Q5
17 marks Moderate -0.3
5 The manager of a farm shop wants to pave routes on the farm so that, after visiting the shop, customers can visit the animals in fields A, B, C, D and E.
The table shows the cost, in \(\pounds\), of making a paved path between each pair of fields.
A river means that it is not possible to make a paved path between C and E .
\(\mathrm { A } , \mathrm { B }\)\(\mathrm { A } , \mathrm { C }\)\(\mathrm { A } , \mathrm { D }\)\(\mathrm { A } , \mathrm { E }\)\(\mathrm { B } , \mathrm { C }\)\(\mathrm { B } , \mathrm { D }\)\(\mathrm { B } , \mathrm { E }\)\(\mathrm { C } , \mathrm { D }\)\(\mathrm { C } , \mathrm { E }\)\(\mathrm { D } , \mathrm { E }\)
300500900700200600400500-100
  1. Determine the minimum cost of connecting the fields.
    1. By applying the lower bound algorithm to each vertex in turn, determine a best lower bound for \(P\), the minimum cost of making a circular tour (cycle) of paved paths that visits each field once.
    2. By applying the nearest neighbour algorithm, starting at each vertex in turn, find a best upper bound for \(P\). You do not need to attempt any route improvements.
    3. Give the order in which the fields are visited in a circular tour of paved paths that corresponds to the best upper bound found in part (b)(ii).
  3. Give a practical reason why the total cost of paving for the project might be more than the best upper bound found in part (b)(ii). It becomes possible to use an existing bridge to make a paved route between C and E . Using this bridge, there is a new indirect route from A to D that costs less than \(\pounds 900\) to pave.
  4. When this bridge is used, what can be determined about the minimum cost of
    1. paving the route between C and E
    2. connecting all the fields?
OCR Further Discrete 2020 November Q6
13 marks Standard +0.3
6 A project is represented by the activity on arc network below.
\includegraphics[max width=\textwidth, alt={}, center]{cc58fb7a-efb6-4548-a8e1-e40abe1eb722-7_410_1095_296_486} The duration of each activity (in minutes) is shown in brackets, apart from activity I.
  1. Suppose that the minimum completion time for the project is 15 minutes.
    1. By calculating the early event times, determine the range of values for \(x\).
    2. By calculating the late event times, determine which activities must be critical. The table shows the number of workers needed for each activity.
      ActivityABCDEFGHIJK
      Workers2112\(n\)121114
  2. Determine the maximum possible value for \(n\) if 5 workers can complete the project in 15 minutes. Explain your reasoning. The duration of activity F is reduced to 1.5 minutes, but only 4 workers are available. The minimum completion time is no longer 15 minutes.
  3. Determine the minimum project completion time in this situation.
  4. Find the maximum possible value for \(x\) for this minimum project completion time.
  5. Find the maximum possible value for \(n\) for this minimum project completion time.
OCR Further Discrete 2021 November Q1
8 marks Moderate -0.3
1 Sam is packing for a holiday. The table shows the mass of each item to be packed.
Item\(A\)\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)\(H\)
Mass (kg)343.52.567.585
Sam's bags can each carry 10 kg , but no more.
  1. Use first-fit to show a possible packing that Sam could use. Indicate the items by using the letters \(A , B , \ldots\) rather than their masses. The total mass of the 8 items is 39.5 kg . Sam says that this means they can be packed using just 4 bags.
  2. Explain why Sam cannot pack the items using just 4 bags. Sam is only allowed to take 4 bags. Each item is given a value out of 20 representing how important it is to Sam.
    Item\(A\)\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)\(H\)
    Mass (kg)343.52.567.585
    Value610121016122014
  3. Sam wishes to pack items with a large total value.
    • State which item Sam should leave behind to maximise the total value.
    • Write down a possible packing with this item omitted.
    • Explain why no larger total is possible.