AQA D1 (Decision Mathematics 1) 2010 January

1 Six girls, Alfonsa (A), Bianca (B), Claudia (C), Desiree (D), Erika (E) and Flavia (F), are going to a pizza restaurant. The restaurant provides a special menu of six different pizzas: Margherita (M), Neapolitana (N), Pepperoni (P), Romana (R), Stagioni (S) and Viennese (V). The table shows the pizzas that each girl likes.

1. Show this information on a bipartite graph.
2. Each girl is to eat a different pizza. Initially, the waiter brings six different pizzas and gives Alfonsa the Pepperoni, Bianca the Romana, Claudia the Neapolitana and Erika the Stagioni. The other two pizzas are put in the middle of the table. From this initial matching, use the maximum matching algorithm to obtain a complete matching so that every girl gets a pizza that she likes. List your complete matching.

2

1. Use a bubble sort to rearrange the following numbers into ascending order. $$\begin{array} { l l l l l l l l } 13 & 16 & 10 & 11 & 4 & 12 & 6 & 7 \end{array}$$
2. State the number of comparisons and the number of swaps (exchanges) for each of the first three passes.

3 [Figure 1, printed on the insert, is provided for use in this question.]
The feasible region of a linear programming problem is represented by the following: $$\begin{aligned} x \geqslant 0 , y & \geqslant 0
x + 4 y & \leqslant 36
4 x + y & \leqslant 68
y & \leqslant 2 x
y & \geqslant \frac { 1 } { 4 } x \end{aligned}$$

1. On Figure 1, draw a suitable diagram to represent the inequalities and indicate the feasible region.
2. Use your diagram to find the maximum value of \(P\), stating the corresponding coordinates, on the feasible region, in the case where:
   1. \(P = x + 5 y\);
   2. \(\quad P = 5 x + y\).

4 In Paris, there is a park where there are statues of famous people; there are many visitors each day to this park. Lighting is to be installed at nine places, \(A , B , \ldots , I\), in the park. The places have to be connected either directly or indirectly by cabling, to be laid alongside the paths, as shown in the diagram. The diagram shows the length of each path, in metres, connecting adjacent places.
\includegraphics[max width=\textwidth, alt={}, center]{f99fad35-3304-4e8f-be02-1439dfdc10e1-4_1109_1120_612_459}

1. 1. Use Prim's algorithm, starting from \(A\), to find the minimum length of cabling required.
   2. State this minimum length.
   3. Draw the minimum spanning tree.
2. A security guard walks along all the paths before returning to his starting place. Find the length of an optimal Chinese postman route for the guard.

5 There is a one-way system in Manchester. Mia is parked at her base, \(B\), in Manchester and intends to visit four other places, \(A , C , D\) and \(E\), before returning to her base. The following table shows the distances, in kilometres, for Mia to drive between the five places \(A , B , C , D\) and \(E\). Mia wants to keep the total distance that she drives to a minimum.

1. Find the length of the tour \(B E C D A B\).
2. Find the length of the tour obtained by using the nearest neighbour algorithm starting from \(B\).
3. Write down which of your answers to parts (a) and (b) would be the better upper bound for the total distance that Mia drives.
4. On a particular day, the council decides to reverse the one-way system. For this day, find the length of the tour obtained by using the nearest neighbour algorithm starting from \(B\).

6 A student is finding a numerical approximation for the area under a curve.
The algorithm that the student is using is as follows:
Line 10 Input \(A , B , N\)
Line 20 Let \(T = 0\)
Line 30 Let \(D = A\)
Line \(40 \quad\) Let \(H = ( B - A ) / N\)
Line \(50 \quad\) Let \(E = H / 2\)
Line 60 Let \(T = T + A ^ { 3 } + B ^ { 3 }\)
Line \(70 \quad\) Let \(D = D + H\)
Line 80 If \(D = B\) then go to line 110
Line 90 Let \(T = T + 2 D ^ { 3 }\)
Line 100 Go to line 70
Line \(110 \quad\) Print 'Area \(=\), \(T \times E\)
Line 120 End
Trace the algorithm in the case where the input values are:

1. \(A = 1 , B = 5 , N = 2\);
2. \(A = 1 , B = 5 , N = 4\).

7 [Figure 2, printed on the insert, is provided for use in this question.]
The following network has 13 vertices and 24 edges connecting some pairs of vertices. The number on each edge is its weight. The weights on the edges \(G K\) and \(L M\) are functions of \(x\) and \(y\), where \(x > 0 , y > 0\) and \(10 < x + y < 27\).
\includegraphics[max width=\textwidth, alt={}, center]{f99fad35-3304-4e8f-be02-1439dfdc10e1-7_1218_1431_660_312} There are three routes from \(A\) to \(M\) of the same minimum total weight.

1. Use Dijkstra's algorithm on Figure 2 to find this minimum total weight.
2. Find the values of \(x\) and \(y\).

8 A factory packs three different kinds of novelty box: red, blue and green. Each box contains three different types of toy: \(\mathrm { A } , \mathrm { B }\) and C . Each red box has 2 type A toys, 3 type B toys and 4 type C toys.
Each blue box has 3 type A toys, 1 type B toy and 3 type C toys.
Each green box has 4 type A toys, 5 type B toys and 2 type C toys.
Each day, the maximum number of each type of toy available to be packed is 360 type A, 300 type B and 400 type C. Each day, the factory must pack more type A toys than type B toys.
Each day, the total number of type A and type B toys that are packed must together be at least as many as the number of type C toys that are packed. Each day, at least \(40 \%\) of the total toys that are packed must be type C toys.
Each day, the factory packs \(x\) red boxes, \(y\) blue boxes and \(z\) green boxes.
Formulate the above situation as 6 inequalities, in addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), simplifying your answers.