OCR Further Discrete (Further Discrete) 2021 November

1 Sam is packing for a holiday. The table shows the mass of each item to be packed. 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)	3	4	3.5	2.5	6	7.5	8	5
   Value	6	10	12	10	16	12	20	14

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.

2 A simply connected semi-Eulerian graph G has 6 vertices and 8 arcs. Two of the vertex degrees are 3 and 4.

1. 1. Determine the minimum possible vertex degree.
   2. Determine the maximum possible vertex degree.
2. Write down the two possible degree sequences (ordered lists of vertex degrees). The adjacency matrix for a digraph H is given below.

   \multirow{7}{*}{From}	\multirow{2}{*}{}	To
   		J	K	L	M	N
   	J	0	1	1	0	0
   	K	1	0	1	0	0
   	L	1	0	0	0	1
   	M	0	0	2	1	1
   	N	0	1	0	1	0

3. Write down the indegree and the outdegree of each vertex of H .
4. 1. Use the indegrees and outdegrees to determine whether graph H is Eulerian.
   2. Use the adjacency matrix to determine whether graph H is simply connected.

3 Six people play a game with 150 cards. Each player has a stack of cards in front of them and the remainder of the cards are in another stack on the table.

1. Use the pigeonhole principle to explain why at least one of the stacks must have at least 22 cards in it. The set of cards is numbered from 1 to 150 . Each digit '2', '3' and '5', whether as a units digit or a tens digit, is coloured red.
   So, for example
   • the card numbered 25 has two red digits,
   • the card numbered 26 has one red digit,
   • the card numbered 148 has no red digits.
   • By considering the cards with one digit, two digits and three digits, or otherwise, determine how many cards have no red digits.
   The cards are put into a Venn diagram with three intersecting sets:
   \(\mathrm { A } = \{\) cards with a number that is a multiple of \(2 \}\)
   \(\mathrm { B } = \{\) cards with a number that is a multiple of \(3 \}\)
   \(\mathrm { C } = \{\) cards with a number that is a multiple of \(5 \}\) For example
   • the card numbered 2 is in set A ,
   • the card numbered 15 is in sets B and C ,
   • the card numbered 23 is in none of the sets.
     \includegraphics[max width=\textwidth, alt={}, center]{133395d2-5020-4054-a229-70168f1d0f95-4_588_1150_1667_246}
   • By considering the cards with one digit, two digits and three digits, or otherwise, determine how many cards in set A have no red digits.
   • Given that, for the cards with no red digits, \(n ( B ) = 21 , n ( C ) = 9\) and \(n ( A \cap B ) = 12\), use the inclusion-exclusion principle to determine how many of the cards with no red digits are in none of the sets A, B or C.

4 One of these graphs is isomorphic to \(\mathrm { K } _ { 2,3 }\). \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Explain how you know that each of the other graphs is not isomorphic to \(\mathrm { K } _ { 2,3 }\). The arcs of the complete graph \(\mathrm { K } _ { 5 }\) can be partitioned as the complete bipartite graph \(\mathrm { K } _ { 2,3 }\) and a graph G.
2. Draw the graph G.
3. Explain carefully how you know that the graph \(\mathrm { K } _ { 5 }\) has thickness 2 . 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, \(\alpha\) and \(\beta\). STEP 1 Choose a vertex and assign it colour \(\alpha\).
   STEP 2 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour \(\beta\) to each vertex that is adjacent to a vertex with colour \(\alpha\). STEP 3 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour \(\alpha\) to each vertex that is adjacent to a vertex with colour \(\beta\). 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. Otherwise the graph is not bipartite. STEP 6 Stop.
4. Apply this algorithm to graph A, starting with the vertex in the top left corner, to determine whether graph A is bipartite or not. A measure of the efficiency of the colouring algorithm is given by the number of passes through STEP 4.
5. Write down how many passes through STEP 4 are needed for the bipartite graph \(\mathrm { K } _ { 2,3 }\). The worst case is when the graph is a path that starts at one vertex and ends at another, having passed through each of the other vertices once.
6. What can you deduce about the efficiency of the colouring algorithm in this worst case? The colouring algorithm is used on two graphs, X and Y . It takes 10 seconds to run for graph X and 60 seconds to run for graph Y. Graph X has 1000 vertices.
7. Estimate the number of vertices in graph Y . A different algorithm has efficiency \(\mathrm { O } \left( 2 ^ { n } \right)\). This algorithm takes 10 seconds to run for graph X .
8. Explain why you would expect this algorithm to take longer than 60 seconds to run for graph Y .

5 Alex and Beth play a zero-sum game. Alex chooses a strategy P, Q or R and Beth chooses a strategy \(\mathrm { X } , \mathrm { Y }\) or Z . The table shows the number of points won by Alex for each combination of strategies. The entry for cell \(( \mathrm { P } , \mathrm { X } )\) is \(x\), where \(x\) is an integer. \begin{table}[h] \end{table} Suppose that P is a play-safe strategy.

1. 1. Determine the values of \(x\) for which the game is stable.
   2. Determine the values of \(x\) for which the game is unstable. The game can be reduced to a \(2 \times 3\) game using dominance.
2. Write down the pay-off matrix for the reduced game. When the game is unstable, Alex plays strategy P with probability \(p\).
3. Determine, as a function of \(x\), the value of \(p\) for the optimal mixed strategy for Alex. Suppose, instead, that P is not a play-safe strategy and the value of \(x\) is - 5 .
4. Show how to set up a linear programming formulation that could be used to find the optimal mixed strategy for Alex.

6 An initial simplex tableau is shown below. The variables \(s , t\) and \(u\) are slack variables.

1. For the LP problem that this tableau represents, write down the following, in terms of \(x\) and \(y\) only.
   • The objective function, \(P\), to be maximised.
   • The constraints as inequalities.
   The graph below shows the feasible region for the problem (as the unshaded region, and its boundaries), and objective lines \(P = 10\) and \(P = 20\) (shown as dotted lines).
   \includegraphics[max width=\textwidth, alt={}, center]{133395d2-5020-4054-a229-70168f1d0f95-7_883_1043_1272_244} The optimal solution is \(P = 23\), when \(x = 0\) and \(y = 4.6\).
2. Complete the first three rows of branch-and-bound in the Printed Answer Booklet, branching on \(y\) first, to determine an optimal solution when \(x\) and \(y\) are constrained to take integer values. In your working, you should show non-integer values to \(\mathbf { 2 }\) decimal places. The tableau entry 18.8 is reduced to 0 .
3. Describe carefully what changes, if any, this makes to the following.
   • The graph of the feasible region.
   • The optimal integer valued solution.

7 A network is formed by weighting the graph below using the listed arc weights.
\includegraphics[max width=\textwidth, alt={}, center]{133395d2-5020-4054-a229-70168f1d0f95-8_168_190_310_258}
\(\begin{array} { l l l l l l l l } 2.9 & 0.9 & 1.5 & 3.5 & 4.2 & 5.3 & 4.7 & 2.3 \end{array}\)

1. 1. Show the result after the first pass and after the second pass, when the list of weights is sorted into increasing order using bubble sort.
   2. Show the result after the first pass and after the second pass, when the list of weights is sorted into increasing order using shuttle sort. In the remaining passes of bubble sort another 14 comparisons are made.
      In the remaining passes of shuttle sort another 11 comparisons are made.
      The total number of swaps needed is the same for both sorting methods.
2. Use the total number of comparisons and the total number of swaps to compare the efficiency of bubble sort and shuttle sort for sorting this list of weights. The sorted list of arc weights for the network is as follows.
   \(\begin{array} { l l l l l l l l } 0.9 & 1.5 & 2.3 & 2.9 & 3.5 & 4.2 & 4.7 & 5.3 \end{array}\) These weights can be given to the arcs of the graph in several ways to form different networks.
3. 1. What is the smallest weight that does not have to appear in a minimum spanning tree for any of these networks? You must explain your reasoning.
   2. Show a way of weighting the arcs, using the weights in the list, that results in the largest possible total for a minimum spanning tree. You should state the total weight of your minimum spanning tree.
   3. Determine the total weight of an optimal solution of the route inspection problem for the network found in part (c)(ii). \section*{END OF QUESTION PAPER}