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

A coach operator offers sightseeing tours of a city. The sightseeing tour starts and ends at stop A, and there are tourist attractions at B, C, D, E, F and G. The table below shows the distances in metres that the coach must travel between each of the seven stops.

The coach operator wants to find a route which starts and ends at A, visiting every tourist attraction once.

State the standard network problem that they must solve.

Use the nearest neighbour method to find an upper bound for the length of the coach

operator’s route starting at A.

Beginning by removing stop A to reduce the network, use an algorithm to determine a lower

bound for the length of the coach operator’s route.

By referring to your lower bound, comment on the length of the route found by the nearest

neighbour method.

Graph G is shown below

Show that graph G is not bipartite.

Use Kuratowski’s Theorem to show that graph G is not planar.

Determine whether graph G is simply connected.

Write down the indegree and outdegree of node L.

Determine whether digraph H is simply connected.

Hiro uses a sorting algorithm to sort the heights in cm of 8 people into ascending order.

At the end of the first pass through the algorithm, Hiro ends up with the list below:

142 165 152 135 171 154 172 182

If Hiro used the shuttle sort algorithm, write down the possibilities for the original list.

Hiro actually used the bubble sort algorithm starting at the left-hand side.

Complete the second and third passes using the bubble sort algorithm.

You should show the list that results at the end of each pass.

In total, Hiro needed 5 passes to complete the bubble sort algorithm.

In total, the shuttle sort algorithm would take 12 comparisons to sort the original list into ascending order.

Using the total number of comparisons for each algorithm, compare the efficiency of

bubble sort and shuttle sort for sorting the heights of the 8 people.

It takes a computer 2.4 × 10^-3 seconds to sort a list of 300 numbers into ascending order using the bubble sort algorithm.

Find the approximate length of a list the computer could sort in 1 minute. Give your answer

to 1 significant figure.

The table shows the activities involved in a project, together with the immediate predecessors and the duration of each activity in hours.

By constructing an activity network for the project, determine the minimum time in

which the project can be completed.

State the critical activities.

Calculate the interfering float for each non-critical activity.

Each activity requires one worker. When an activity is started it must be completed without interruption.

Use the diagram in the Printed Answer Booklet to determine the minimum number of workers needed to complete the project in the minimum completion time.

Each column in the diagram represents 1 hour. For each worker, write the letter of the activity they are doing in each box, or leave the box blank if the worker is resting for that hour. You

may not need to use all the rows or columns in the table.

Activity C takes an additional t hours, but all other timings are unchanged.

Determine the range of values of t that result in an increase in the minimum project

completion time.

Write down the maximum possible pay-off to Player B if Player A plays option P.

Determine whether or not the game is stable.

Show that there are no Nash Equilibrium points for the game.

The entry in one cell in the zero-sum game above can be increased so that there is a Nash Equilibrium point.

• Identify the cell that should be chosen.

• Write down the smallest value that it could take.

Show that the original game can be reduced to a game with a 3 × 2 pay-off matrix using

dominance.

The entry in cell (Q,Y) in the reduced game is changed to a number less than - 4. This new number is denoted by m. You are given that the value of the reduced game to Player B with this change is 0.4.

Determine the optimal mixed strategy for Player B.

Find the corresponding value of m.

A furniture company makes three types of wardrobes.

Each Type A wardrobe requires 4 hours of machine time, 6 hours of craftsman time and 2 hours of finishing time.

Each Type B wardrobe requires 3 hours of machine time, 5 hours of craftsman time and 11 hours of finishing time.

Each Type C wardrobe requires 5 hours of machine time, 4 hours of craftsman time and 4 hours of finishing time.

Each month, there is a maximum of 200 hours of machine time, 160 hours of craftsman time and 144 hours of finishing time.

The company makes £16 profit on each Type A wardrobe, £20 profit on each Type B wardrobe and £14 profit on each Type C wardrobe. The company wants to make as much profit P as possible.

Let x, y and z denote the number of Type A, Type B and Type C wardrobes made each month.

Write down the objective function for this problem.

Complete the table in the Printed Answer Booklet to represent the problem as an initial

simplex tableau. You should use the first blank row for your objective function.

Show the calculations used to find the pivot element for the first iteration of the simplex

algorithm.

Carry out one iteration of the simplex algorithm. You should give each entry in exact

form.

Determine the value of k.

Charlie has a set of 100 cards. On each card one of the integers from 1 to 100 is printed without any repeats.

Use the inclusion-exclusion principle to determine how many of Charlie’s cards show a

number that is a multiple of 2, 3 or 5.

Charlie then chooses one or more cards at random and arranges them next to each other to form a number with n digits where n ⩾ 1.

Determine the total number of different arrangements of cards that will produce a 3-digit

number.