OCR Further Discrete (Further Discrete) 2018 March

The masses, in kg, of ten bags are given below. 8 \quad 10 \quad 10 \quad 12 \quad 12 \quad 12 \quad 13 \quad 15 \quad 18 \quad 18

1. Use first-fit decreasing to pack the bags into crates that can hold a maximum of 50 kg each. [3]

Only two crates are available, so only some of the bags will be packed. Each bag is given a value.

Bag	A	B	C	D	E	F	G	H	I	J
Mass (kg)	8	10	10	12	12	12	13	15	18	18
Value	6	3	3	2	4	5	4	6	4	4

1. Find a packing into two crates so that the total value of the bags in the crates is at least 32. [3]

A linear programming problem is \begin{align} \text{Maximise } P &= 4x - y - 2z
\text{subject to } x + 5y + 3z &\leq 60
2x - 5y &\leq 80
2y + z &\leq 10
x \geq 0, y &\geq 0, z \geq 0 \end{align}

1. Use the simplex algorithm to solve the problem. [7]

In the case when \(z = 0\) the feasible region can be represented graphically. \includegraphics{figure_1} The vertices of the feasible region are \((0, 0)\), \((40, 0)\), \((46.67, 2.67)\), \((35, 5)\) and \((0, 5)\), where non-integer values are given to 2 decimal places. The linear programming problem is given the additional constraint that \(x\) and \(y\) are integers.

1. Use branch-and-bound, branching on \(x\) first, to show that the optimum solution with this additional constraint is \(x = 45, y = 2\). [7]

50 people are at a TV game show. 21 of the 50 are there to take part in the game show and the others are friends who are in the audience, 22 are women and 20 are from London, 2 are women from London who are there to take part in the game show and 15 are men who are not from London and are friends who are in the audience.

1. Deduce how many of the 50 people are in two of the categories 'there to take part in the game show', 'is a woman' and 'is from London', but are not in all three categories. [3]

The 21 people who are there to take part in the game show are moved to the stage where they are seated in two rows of seats with 20 seats in each row. Some of the seats are empty.

1. Show how the pigeonhole principle can be used to show that there must be at least one pair of these 21 people with no empty chair between them. [2]

The 21 people are split into three sets of 7. In each round of the game show, three of the people are chosen. The three people must all be from the same set of 7 but once two people have played in the same round they cannot play together in another round. For example, if A plays with B and C in round 1 then A cannot play with B or with C in any other round.

1. By first considering how many different rounds can be formed using the first set of seven people, deduce how many rounds there can be altogether. [3]

The graph below connects nine vertices A, B, \(\ldots\), H, I. \includegraphics{figure_2}

1. 1. Show that the minimum sum of the degrees of each pair of non-adjacent vertices is 9. [2]
   2. Explain what you can deduce from the result in part (a). [1]
2. Use Kuratowski's theorem to prove that the graph is non-planar. [3]
3. Prove that there is no subgraph of the graph that is isomorphic to \(K_4\), without using subdivision or contraction. [6]

The diagram represents a map of seven locations (A to G) and the direct road distances (km) between some of them. \includegraphics{figure_3} A delivery driver needs to start from his depot at D, make deliveries at each of A, B, F and G, and finish at D.

1. Write down a route from A to G of length 70 km. [1]

The table shows the length of the shortest path between some pairs of places.

	D	A	B	F	G
D	-
A		-			70
B			-	84
F			84	-
G		70			-

1. 1. Complete the table.
   2. Use the nearest neighbour method on the table, starting at D, to find the length of a cycle through D, A, B, F and G, ignoring possibly repeating E and C. [4]
2. By first considering the table with the row and column for D removed, find a lower bound for the distance that the driver must travel. [2]
3. What can you conclude from your previous answers about the distance that the driver must travel? [1]

A new road is constructed between D and F. Using this road the driver starts from D, makes the deliveries and returns to D having travelled just 172 km.

1. Find the length of the new road if
   1. the driver does not return to D until all the deliveries have been made,
   2. the driver uses the new road twice in making the deliveries. [4]

The activities involved in a project, their durations, immediate predecessors and the number of workers required for each activity are shown in the table.

Activity	Duration (hours)	Immediate predecessors	Number of workers
A	6	-	2
B	4	-	1
C	4	-	1
D	2	A	2
E	3	A, B	1
F	4	C	1
G	3	D	1
H	3	E, F	2

1. Model the project using an activity network.
2. Draw a cascade chart for the project, showing each activity starting at its earliest possible start time. [3]
3. Construct a schedule to show how three workers can complete the project in the minimum possible time. [4]

Each day Alix and Ben play a game. They each choose a card and use the table below to find the number of points they win. The table shows the cards available to each player. The entries in the cells are of the form \((a, b)\), where \(a =\) points won by Alix and \(b =\) points won by Ben. Each is trying to maximise the points they win.

1. Explain why the table cannot be reduced through dominance no matter what values \(x\) and \(y\) have. [2]
2. Show that the game is not stable no matter what values \(x\) and \(y\) have. [2]
3. Find the Nash equilibrium solutions for the various values that \(x\) and \(y\) can have. [4]