OCR Further Discrete AS (Further Discrete AS) 2019 June

1 Alfie has a set of 15 cards numbered consecutively from 1 to 15.
He chooses two of the cards.

1. How many different sets of two cards are possible? Alfie places the two cards side by side to form a number with 2,3 or 4 digits.
2. Explain why there are fewer than \({ } ^ { 15 } \mathrm { P } _ { 2 } = 210\) possible numbers that can be made.
3. Explain why, with these cards, 1 is the lead digit more often than any other digit. Alfie makes the number 113, which is a 3-digit prime number. Alfie says that the problem of working out how many 3-digit prime numbers can be made using two of the cards is a construction problem, because he is trying to find all of them.
4. Explain why Alfie is wrong to say this is a construction problem.

2 Two graphs are shown below. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. List the vertex degrees for each graph.
2. Prove that the graphs are non-isomorphic. The two graphs are joined together by adding an arc connecting J and T .
3. 1. Explain how you know that the resulting graph is not Eulerian.
   2. Describe how the graph can be made Eulerian by adding one more arc. The vertices of the graph \(K _ { 3 }\) are connected to the vertices of the graph \(K _ { 4 }\) to form the graph \(K _ { 7 }\).
4. Explain why 12 arcs are needed connecting \(K _ { 3 }\) to \(K _ { 4 }\).

3

1. Give an example of a standard sorting algorithm that can be used when some of the values are not known until after the sorting has been started. Becky needs to sort a list of numbers into increasing order.
   She uses the following algorithm:
   STEP 1: Let \(L\) be the first value in the input list.
   Write this as the first value in the output list and delete it from the input list.
   STEP 2: If the input list is empty go to STEP 7.
   Otherwise let \(N\) be the new first value in the input list and delete this value from the input list. STEP 3: \(\quad\) Compare \(N\) with \(L\).
   STEP 4: If \(N\) is less than or equal to \(L\)
   • write the value of \(N\) immediately before \(L\) in the output list,
   • replace \(L\) with the first value in the new output list,
   • then go to STEP 2.
   STEP 5: If \(N\) is greater than \(L\)
   • if \(L\) is the value of the last number in the output list, go to STEP 6;
   • otherwise, replace \(L\) with the next value in the output list and then go to STEP 3.
   STEP 6: \(\quad\) Write the value of \(N\) immediately after \(L\) in the output list. Let \(L\) be the first value in the new output list and then go to STEP 2. STEP 7: Print the output list and STOP.
2. Trace through Becky's algorithm when the input list is $$\begin{array} { l l l l l l } 6 & 9 & 5 & 7 & 6 & 4 \end{array}$$ Complete the table in the Printed Answer Booklet, starting a new row each time that STEP 3 or STEP 7 is used.
   You should not need all the lines in the Answer Booklet. Becky measures the efficiency of her sort by counting using the number of times that STEP 3 is used.
3. 1. How many times did Becky use STEP 3 in sorting the list from part (b)?
   2. What is the greatest number of times that STEP 3 could be used in sorting a list of 6 values? A computer takes 15 seconds to sort a list of 60 numbers using Becky's algorithm.
4. Approximately how long would you expect it to take the computer to sort a list of 300 numbers using the algorithm?

4 The table shows the activities involved in a project, their durations in hours and their immediate predecessors. The activities can be represented as an activity network.

1. Use standard algorithms to find the activities that form
   • the longest path(s)
   • the shortest path(s)
     through the activity network.
   You must show working to demonstrate the use of the algorithms. Only one of the paths from part (a) has a practical interpretation.
2. What is the practical interpretation of the total weight of that path? The duration of activity E can be changed. No other durations change.
3. What is the smallest increase to the duration of E that will make activity E become part of a longest path through the network?

5 Corey is training for a race that starts in 18 hours time. He splits his training between gym work, running and swimming.

• At most 8 hours can be spent on gym work.
• At least 4 hours must be spent running.
• The total time spent on gym work and swimming must not exceed the time spent running.

Corey thinks that time spent on gym work is worth 3 times the same time spent running or 2 times the same time spent swimming. Corey wants to maximise the worth of the training using this model.

1. Formulate a linear programming problem to represent Corey's problem. Your formulation must include defining the variables that you are using. Suppose that Corey spends the maximum of 8 hours on gym work.
2. 1. Use a graphical method to determine how long Corey should spend running and how long he should spend swimming.
   2. Describe why this solution is not practical.
   3. Describe how Corey could refine the LP model to make the solution more realistic.

6 Drew and Emma play a game in which they each choose a strategy and then use the tables below to determine the pay-off that each receives.

1. Convert the game into a zero-sum game, giving the pay-off matrix for Drew.
2. Determine the optimal mixed strategy for Drew.
3. Determine the optimal mixed strategy for Emma.