Questions Further Discrete (67 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 SPS ASFM SPS ASFM Mechanics SPS ASFM Pure SPS ASFM Statistics SPS FM SPS FM Mechanics SPS FM Pure SPS FM Statistics SPS SM SPS SM Mechanics SPS SM Pure SPS SM Statistics 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 SPS SPS ASFM SPS ASFM Mechanics SPS ASFM Pure SPS ASFM Statistics SPS FM SPS FM Mechanics SPS FM Pure SPS FM Statistics SPS SM SPS SM Mechanics SPS SM Pure SPS SM Statistics 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
OCR Further Discrete 2019 June Q1
1 Two graphs are shown below. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{7717b4ca-45ab-4111-9f59-5a3abb04b388-2_396_351_397_246} \captionsetup{labelformat=empty} \caption{Graph G1}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{7717b4ca-45ab-4111-9f59-5a3abb04b388-2_394_343_397_932} \captionsetup{labelformat=empty} \caption{Graph G2}
\end{figure}
    1. Prove that the graphs are isomorphic.
    2. Verify that Euler's formula holds for graph G1.
  2. Describe how it is possible to add 4 arcs to graph G1 to make a non-planar graph with 5 vertices.
  3. Describe how it is possible to add a vertex U and 4 arcs to graph G 2 to make a connected nonplanar graph with 6 vertices.
OCR Further Discrete 2019 June Q2
2 A project is represented by the activity network and cascade chart below. The table showing the number of workers needed for each activity is incomplete. Each activity needs at least 1 worker.
\includegraphics[max width=\textwidth, alt={}, center]{7717b4ca-45ab-4111-9f59-5a3abb04b388-2_202_565_1605_201}
\includegraphics[max width=\textwidth, alt={}, center]{7717b4ca-45ab-4111-9f59-5a3abb04b388-2_328_560_1548_820}
ActivityWorkers
A2
BX
C
D
E
F
  1. Complete the table in the Printed Answer Booklet to show the immediate predecessors for each activity.
  2. Calculate the latest start time for each non-critical activity. The minimum number of workers needed is 5 .
  3. What type of problem (existence, construction, enumeration or optimisation) is the allocation of a number of workers to the activities? There are 8 workers available who can do activities A and B .
    1. Find the number of ways that the workers for activity A can be chosen.
    2. When the workers have been chosen for activity A , find the total number of ways of choosing the workers for activity B for all the different possible values of x , where \(\mathrm { x } \geqslant 1\).
OCR Further Discrete 2019 June Q3
3 A problem is represented as the initial simplex tableau below.
\(\mathbf { P }\)\(\mathbf { x }\)\(\mathbf { y }\)\(\mathbf { z }\)\(\mathbf { s }\)\(\mathbf { t }\)RHS
1- 201000
01111060
02340160
  1. Write the problem as a linear programming formulation in the standard algebraic form with no slack variables.
  2. Carry out one iteration of the simplex algorithm.
  3. Show algebraically how each row of the tableau found in part (b) is calculated.
OCR Further Discrete 2019 June Q4
4 An algorithm must have an input, an output, be deterministic and finite.
  1. Why is a counter sometimes used in an algorithm? A computer takes 0.2 seconds to sort a list of 500 numbers.
  2. How long would you expect the computer to take to sort a list of 5000 numbers? Simon says that he can sort a list of numbers 'just by looking at them'.
  3. Explain to Simon why sorting algorithms are needed.
  4. Demonstrate how quick sort works by using it to sort the following list into increasing order. You should indicate the pivots used and which values are already known to be in their correct position.
    \(\begin{array} { l l l l l } 41 & 17 & 8 & 33 & 29 \end{array}\) For an average case the efficiency of quick sort is O (nlogn), where n is the number of items in the list.
  5. Explain why quick sort is typically quicker than bubble sort and shuttle sort. When the number of comparisons made is used as a measure of the efficiency, the worst case for quick sort is no more efficient than the worst case for bubble sort. An arrangement of the five numbers from part (d) makes up a new list that is to be sorted using the bubble sort or the quick sort.
  6. Without writing out all the passes, determine
    • the worst case list
    • the total number of comparisons for the worst case list
      for each of the algorithms in turn.
OCR Further Discrete 2019 June Q5
5 A network is represented by the distance matrix below. For this network a direct connection between two vertices is always shorter than an indirect connection.
ABCDEFGH
A-130100--250--
B130--50--170100
C100---80170-90
D-50----120-
E--80--140-120
F250-170-140---
G-170-120---90
H-10090-120-90-
  1. How does the distance matrix show that the arcs are undirected? The shortest distance from A to E is 180 .
  2. Write down the shortest route from A to E .
  3. Use Dijkstra's algorithm on the distance matrix to find the length of the shortest route from \(\mathbf { G }\) to each of the other vertices. The arcs represent roads and the weights represent distances in metres. The total length of all the roads is 1610 metres. Emily and Stephen have set up a company selling ice-creams from a van.
  4. Emily wants to deliver leaflets to the houses along each side of each road. Find the length of the shortest continuous route that Emily can use.
  5. Stephen wants to drive along each road in the ice-cream van.
    1. Determine the length of the shortest route for Stephen if he starts at B.
    2. Stephen wants to use the shortest possible route.
      • Find the length of the shortest possible route.
  6. Write down the start and end vertices of this route.
OCR Further Discrete 2019 June Q6
6 The pay-off matrix for a game between two players, Sumi and Vlad, is shown below. If Sumi plays A and Vlad plays X then Sumi gets X points and Vlad gets 1 point. Sumi
Vlad
\cline { 2 - 4 } \multicolumn{1}{c}{}\(X\)\(Y\)\(Z\)
A\(( x , 1 )\)\(( 4 , - 2 )\)\(( 2,0 )\)
B\(( 3 , - 1 )\)\(( 6 , - 4 )\)\(( - 1,3 )\)
You are given that cell ( \(\mathrm { A } , \mathrm { X }\) ) is a Nash Equilibrium solution.
  1. Find the range of possible values of X .
  2. Explain what the statement 'cell (A, X) is a Nash Equilibrium solution' means for each player.
  3. Find a cell where each player gets their maximin pay-off. Suppose, instead, that the game can be converted to a zero-sum game.
  4. Determine the optimal strategy for Sumi for the zero-sum game.
    • Record the pay-offs for Sumi when the game is converted to a zero-sum game.
    • Describe how Sumi should play using this strategy.
OCR Further Discrete 2019 June Q7
7 Sam is making pies.
There is exactly enough pastry to make 7 large pies or 20 medium pies or 36 small pies, or some mixture of large, medium and small pies. This is represented as a constraint \(180 x + 63 y + 35 z \leqslant 1260\).
  1. Write down what \(\mathrm { X } , \mathrm { Y }\) and Z represent. There is exactly enough filling to make 5 large pies or 12 medium pies or 18 small pies, or some mixture of large, medium and small pies.
  2. Express this as a constraint of the form \(a x + b y + c z \leqslant d\), where \(a , b , c\) and \(d\) are integers. The number of small pies must equal the total number of large and medium pies.
  3. Show that making exactly 9 small pies is inconsistent with the constraints.
  4. Determine the maximum number of large pies that can be made.
    • Your reasoning should be in the form of words, calculations or algebra.
    • You must check that your solution is feasible.
OCR Further Discrete 2022 June Q1
1 Four children, A, B, C and D, discuss how many of the 23 birthday parties held by their classmates they had gone to. Each party was attended by at least one of the four children. The results are shown in the Venn diagram below.
\includegraphics[max width=\textwidth, alt={}, center]{50697293-6cdc-475f-981f-71a351b0ff5a-2_387_618_589_246}
  1. Construct a complete graph \(\mathrm { K } _ { 4 }\), with vertices representing the four children and arcs weighted to show the number of parties each pair of children went to.
  2. State a piece of information about the number of parties the children went to that is shown in the Venn diagram but is not shown in the graph. A fifth child, E, also went to some of the 23 parties shown in the Venn diagram.
    Every party that E went to was also attended by at least one of \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D .
    • A was at 8 of these parties, B at 7, C at 5 and D at 8 .
    • These include 5 parties attended by both A and \(\mathrm { B } , 2\) by both A and \(\mathrm { C } , 3\) by both A and \(\mathrm { D } , 3\) by both B and D and 4 by both C and D .
    • These include 1 party attended by \(\mathrm { A } , \mathrm { B }\) and D and 1 party attended by \(\mathrm { A } , \mathrm { C }\) and D .
    • Use the inclusion-exclusion principle to determine the number of parties that E went to.
OCR Further Discrete 2022 June Q2
2 The table below shows the activities involved in a project together with the immediate predecessors and the duration of each activity.
ActivityImmediate predecessorsDuration (minutes)
A-4
B-1
CA2
DA, B5
ED1
FB, C2
GD, F5
HE, F4
  1. Model the project using an activity network.
  2. Determine the minimum project completion time.
  3. Calculate the total float for each non-critical activity.
OCR Further Discrete 2022 June Q3
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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.