OCR A Level Further Maths A Discrete Mathematics (optional - choose any two of Y542/Y543/Y544/Y545) November 2021 question paper Y544

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.

Use first - fit to show a possible packing that Sam could use. Indicate the items by using the

letters A, B, … 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.

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.

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.

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

Determine the minimum possible vertex degree.

Determine the maximum possible vertex degree.

Write down the two possible degree sequences (ordered lists of vertex degrees).

The adjacency matrix for a digraph H is given below.

Write down the indegree and the outdegree of each vertex of H.

Use the indegrees and outdegrees to determine whether graph H is Eulerian.

Use the adjacency matrix to determine whether graph H is simply connected.

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.

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.

Given that, for the cards with no red digits, n (B) = 21, n (C) = 9 and n (A ∩ 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.

Explain carefully how you know that the graph K₅ 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, α and β.

STEP 1 Choose a vertex and assign it colour α.

STEP 2 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour β to each vertex that is adjacent to a vertex with colour α.

STEP 3 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour α to each vertex that is adjacent to a vertex with colour β.

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.

Apply this algorithm to graph A, starting with the vertex in the top left corner, to determine

whether graph A is bipartite or not.

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.

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.

Estimate the number of vertices in graph Y.

A different algorithm has efficiency O(2ⁿ). This algorithm takes 10 seconds to run for graph X.

Explain why you would expect this algorithm to take longer than 60 seconds to run for graph Y.

Alex and Beth play a zero-sum game. Alex chooses a strategy P, Q or R and Beth chooses a strategy X, Y or Z. The table shows the number of points won by Alex for each combination of strategies. The entry for cell (P, X) is x, where x is an integer.

Suppose that P is a play-safe strategy.

Determine the values of x for which the game is stable.

Determine the values of x for which the game is unstable.

The game can be reduced to a 2 × 3 game using dominance.

Write down the pay-off matrix for the reduced game.

When the game is unstable, Alex plays strategy P with probability p.

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.

Show how to set up a linear programming formulation that could be used to find the optimal

mixed strategy for Alex.

An initial simplex tableau is shown below.

The variables s, t and u are slack variables.

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).

The optimal solution is P = 23, when x = 0 and y = 4.6.

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 2 decimal places.

The tableau entry 18.8 is reduced to 0.

Describe carefully what changes, if any, this makes to the following.

• The graph of the feasible region.

• The optimal integer valued solution.

A network is formed by weighting the graph below using the listed arc weights.

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.

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.

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.

0.9 1.5 2.3 2.9 3.5 4.2 4.7 5.3

These weights can be given to the arcs of the graph in several ways to form different networks.

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.

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.

Determine the total weight of an optimal solution of the route inspection problem for the

network found in part (c)(ii).