OCR Further Discrete (Further Discrete) 2018 December

1 Arif and Bindiya play a game as follows.

• They each secretly choose a positive integer from \(\{ 2,3,4,5 \}\).
• They then reveal their choices. Let Arif's choice be \(A\) and Bindiya's choice be \(B\).
• If \(A ^ { B } \geqslant B ^ { A }\), Arif wins \(B\) points and Bindiya wins \(- 4 - B\) points.
• If \(A ^ { B } < B ^ { A }\), Arif wins \(- 4 - A\) points and Bindiya wins \(A\) points.
  1. Assuming that each of the 16 possible outcomes is equally likely to be chosen, show that the average amount won by Arif is 0 .
  2. 1. Describe how to convert this game to a zero-sum game.
     2. Construct the pay-off matrix for this zero-sum game, with Arif on rows.

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

1. 1. Write down the orders of the vertices for each of these graphs.
   2. How many ways are there to allocate these vertex degrees to a graph with vertices \(\mathrm { P } , \mathrm { Q }\), \(\mathrm { R } , \mathrm { S } , \mathrm { T }\) and U ?
   3. Use the vertex degrees to deduce whether the graphs are Eulerian, semi-Eulerian or neither.
2. Show that graphs 1 and 2 are not isomorphic.
3. 1. Write down a Hamiltonian cycle for graph 1.
   2. Use Euler's formula to determine the number of regions for graph 1.
   3. Identify each of these regions for graph 1 by listing the cycle that forms its boundary.

3 A set of ten cards have the following values:
\(\begin{array} { l l l l l l l l l l } 13 & 8 & 4 & 20 & 12 & 15 & 3 & 2 & 10 & 8 \end{array}\) Kerenza wonders if there is a set of these cards with a total of exactly 50 .

1. Which type of problem (existence, construction, enumeration or optimisation) is this? The five cards \(4,8,8,10\) and 20 have a total of 50.
2. How many ways are there to arrange three of these five cards (with the two 8 s being indistinguishable) so that the total of the numbers on the first two cards is less than the number on the third card?
3. How many ways are there to select (choose) three of the five cards so that the total of the numbers on the three cards is less than 25 ?
4. Show how quicksort works by using it to sort the original list of ten cards into increasing order.
   You should indicate the pivots used and which values are already known to be in their correct position.

4 An algorithm is represented by the flow diagram below.
\includegraphics[max width=\textwidth, alt={}, center]{10ca0bf1-beaa-4460-8f28-08f0e4e44d5c-04_1871_1719_293_173} The algorithm is applied with \(n = 4\) and the table of inputs \(\mathrm { d } ( i , j )\) : $$j = 1 \quad j = 2 \quad j = 3 \quad j = 4$$ $$\begin{aligned} & i = 1
& i = 2
& i = 3
& i = 4 \end{aligned}$$ An incomplete trace through the algorithm is shown below. The next box to be used is the box 'Let \(i = t\) '.

1. Complete the trace in the Printed Answer Booklet. The table of inputs represents a weighted matrix for a network, where the weights represent distances.
2. 1. State how the output of the algorithm relates to the network represented by the matrix.
   2. How can the list A be used in the solution of the travelling salesperson problem on the network represented by the matrix?
   3. Write down a limitation on the distances \(\mathrm { d } ( i , j )\) for this algorithm.
3. Explain why the algorithm is finite for any table of inputs. Suppose that, for a problem with \(n\) vertices, the run-time for the algorithm is given by \(\alpha D + \beta T\), where \(\alpha\) and \(\beta\) are constants, \(D\) is the number of times that a value of \(\mathrm { d } ( i , j )\) is looked up and \(T\) is the number of times that \(t\) is updated.
4. Show how this means that the algorithm has \(\mathrm { O } \left( n ^ { 2 } \right)\) complexity. A computer takes 3 seconds to run the algorithm for a problem with \(n = 35\).
5. Use the complexity to calculate an approximate run-time for a problem with \(n = 100\). The run-time using a second algorithm has \(\mathrm { O } ( n ! )\) complexity.
   A computer takes 2.8 seconds to run the second algorithm for a problem with \(n = 35\).
6. Without performing any further calculations, give a reason why the first algorithm is likely to be more efficient than the second for a problem with \(n = 100\).

5 A rapid transport system connects 8 stations using three railway lines.
The blue line connects A to B to C to D . The red line connects \(B\) to \(F\) to \(E\) to \(D\). The green line connects E to G to H to A .

• The travel times for the return journeys are the same as for the outward journeys (so, for example, the travel time from B to A is 5 minutes, the same as the time from A to B ).
• All travel times include time spent stopped at stations.
• No trains are delayed so the travel times are all correct.
  1. (i) Model the blue, red and green lines, and the travel times above, as a network.
     (ii) Use Dijkstra's algorithm to find the quickest travel times from C to each of the other stations.
  2. 1. Write down a route from A to D with travel time 12 minutes.
     2. Construct a table of quickest travel times.
  3. Give a reason why the quickest journey from A to D may take longer than 12 minutes.

6 Jack is making pizzas for a party. He can make three types of pizza:

• There is enough dough to make 30 pizzas.
• Type Z pizzas use vegan cheese. Jack only has enough vegan cheese to make 2 type Z pizzas.
• At least half the pizzas made must be suitable for vegetarians.
• Jack has enough onions to make 50 type X pizzas or 20 type Y pizzas or 20 type Z pizzas or some mixture of the three types.

Suppose that Jack makes \(x\) type X pizzas, \(y\) type Y pizzas and \(z\) type Z pizzas.

1. Formulate the constraints above in terms of the non-negative, integer valued variables \(x , y\) and \(z\), together with non-negative slack variables \(s , t , u\) and \(v\). Jack wants to find out the maximum total number of pizzas that he can make.
2. 1. Set up an initial simplex tableau for Jack's problem.
   2. Carry out one iteration of the simplex algorithm, choosing your pivot so that \(x\) becomes a basic variable. When Jack carries out the simplex algorithm his final tableau is:

      \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	\(v\)	RHS
      1	0	0	0	0	0	\(\frac { 3 } { 7 }\)	\(\frac { 2 } { 7 }\)	\(28 \frac { 4 } { 7 }\)
      0	0	0	0	1	0	\(- \frac { 3 } { 7 }\)	\(- \frac { 2 } { 7 }\)	\(1 \frac { 3 } { 7 }\)
      0	0	0	1	0	1	0	0	2
      0	1	0	0	0	0	\(\frac { 5 } { 7 }\)	\(\frac { 1 } { 7 }\)	\(14 \frac { 2 } { 7 }\)
      0	0	1	1	0	0	\(- \frac { 2 } { 7 }\)	\(\frac { 1 } { 7 }\)	\(14 \frac { 2 } { 7 }\)

3. Use this final tableau to deduce how many pizzas of each type Jack should make. Jack knows that some of the guests are vegans. He decides to make 2 pizzas of type \(Z\).
4. 1. Plot the feasible region for \(x\) and \(y\).
   2. Complete the branch-and-bound formulation in the Printed Answer Booklet to find the number of pizzas of each type that Jack should make.
      You should branch on \(x\) first. \section*{END OF QUESTION PAPER}