OCR MEI D1 (Decision Mathematics 1) 2016 June

1 Pierre knows that, if he gambles, he will lose money in the long run. Nicolas tries to convince him that this is not the case. Pierre stakes a sum of money in a casino game. If he wins then he gets back his stake plus the same amount again. If he loses then he loses his stake. Nicolas says that Pierre can guarantee to win by repeatedly playing the game, even though the probability of winning an individual game is less than 0.5 . His idea is that Pierre should bet in the first game with a stake of \(\pounds 100\). If he wins then he stops, as he will have won \(\pounds 100\). If he loses then he plays again with a stake of \(\pounds 200\). If he wins then he has lost \(\pounds 100\) and won \(\pounds 200\). This gives a total gain of \(\pounds 100\), and he stops. If he loses then he plays again with a stake of \(\pounds 400\). If he wins this time he has lost \(\pounds 100\) and \(\pounds 200\) and won \(\pounds 400\). This gives a total gain of \(\pounds 100\), and he stops. Nicolas's advice is that Pierre simply has to continue in this way, doubling his stake every time that he loses, until he eventually wins. Nicolas says that this guarantees that Pierre will win \(\pounds 100\). You are to simulate what might happen if Pierre tries this strategy in a casino game in which the probability of him winning an individual game is 0.4 , and in which he has \(\pounds 1000\) available.

1. Give an efficient rule for using 1-digit random numbers to simulate the outcomes of individual games, given that the probability of Pierre winning an individual game is 0.4 .
2. Explain why at most three random digits are needed for one simulation of Nicolas's strategy, given that Pierre is starting with \(\pounds 1000\).
3. Simulate five applications of Nicolas's strategy, using the five sets of three 1-digit random numbers in your answer book.
4. Summarise the results of your simulations, giving your mean result.

2 A bag contains 26 cards. A different letter of the alphabet is written on each one. A card is chosen at random and its letter is written down. The card is returned to the bag. The bag is shaken and the process is repeated several times. Tania wants to investigate the probability of a letter appearing twice. She wants to know how many cards need to be chosen for this probability to exceed 0.5. Tania uses the following algorithm. Step 1 Set \(n = 1\)
Step 2 Set \(p = 1\)
Step 3 Set \(n = n + 1\)
Step 4 Set \(p = p \times \left( \frac { 27 - n } { 26 } \right)\)
Step 5 If \(p < 0.5\) then stop
Step 6 Go to Step 3

1. Run the algorithm.
2. Interpret your results. A well-known problem asks how many randomly-chosen people need to be assembled in a room before the probability of at least two of them sharing a birthday exceeds 0.5 (ignoring anyone born on 29 February).
3. Modify Tania's algorithm to answer the birthday problem. (Do not attempt to run your modified algorithm.)
4. Why have 29 February birthdays been excluded?

3 The adjacency graph of a cube
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_106_108_214_735}
is shown. Vertices on the graph represent faces of the cube. Two vertices are connected by an arc if the corresponding faces of the cube share an edge.
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_401_464_246_1334} The second graph is the complement of the adjacency graph, i.e. the graph that consists of the same vertices together with the arcs that are not in the adjacency graph.
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_403_464_737_1334} Throughout this question we wish to colour solids so that two faces that share an edge have different colours. The second graph shows that the minimum number of colours required for a cube is three, one colour for the top and base, one for the front and back, and one for the left and right.

1. Draw the adjacency graph for a square-based pyramid, and draw its complement. Hence find the minimum number of colours needed to colour a square-based pyramid.
   \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_161_202_1434_1548}
2. (A) Draw the adjacency graph for an octahedron, and draw its complement.
   (B) An octahedron can be coloured using just two colours. Explain how this relates to the complement of the adjacency graph.
   \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_227_205_1731_1548}

4 Two products are to be made from material that is supplied in a single roll, 20 m long and 1 m wide. The two products require widths of 47 cm and 32 cm respectively. Two ways of cutting lengths of material are shown in the plans below.
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-5_408_1538_520_269}
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-5_403_1533_952_274}

1. Given that there should be no unnecessary waste, draw one other cutting plan that might be used for a cut of length \(z\) metres.
2. Write down an expression for the total area that is wasted in terms of \(x , y\) and \(z\). All of the roll is to be cut, so \(x + y + z = 20\).
   There needs to be a total length of at least 20 metres of the material for the first product, the one requiring width 47 cm .
3. Write this as a linear constraint on the variables. There needs to be a total length of at least 24 metres of the material for the second product, the one requiring width 32 cm .
4. Write this as a linear constraint on the variables.
5. Formulate an LP in terms of \(x\) and \(y\) to minimise the area that is wasted. You will need to use the relationship \(x + y + z = 20\), together with your answers to parts (ii), (iii) and (iv).
6. Solve your LP graphically, and interpret the solution.

5 A village amateur dramatic society is planning its annual pantomime. Three rooms in the village hall have been booked for one evening per week for 12 weeks. The following activities must take place. Their durations are shown. Each activity needs a room except for activities G, I and J.
Choosing actors and dancers can be done in the same week. Rehearsals can begin after this. Rehearsing the dancers cannot begin until the music has been prepared. The scenery must be installed after rehearsals, but before dress rehearsals.
Making the costumes cannot start until after the actors and dancers have been chosen. Everything must be ready for the dress rehearsals in the final two weeks of the 12-week preparation period.

1. Complete the table in your answer book by showing the immediate predecessors for each activity.
2. Draw an activity on arc network for these activities.
3. Mark on your network the early time and the late time for each event. Give the critical activities. It is discovered that there is a double booking and that one of the rooms will not be available after week 6.
4. Using the space provided, produce a schedule showing how the pantomime can be ready in time for its first performance.

6 A mountain ridge separates two populated areas. Networks representing roads connecting the villages in each area are shown below. The numbers on the arcs represent distances in kilometres.
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-7_524_1429_340_319} There is also a mountain road of length 15 kilometres connecting C to Z .

1. A national bus company needs a route from A to X .
   1. Use Dijkstra's algorithm on the complete network, including CZ, to find the shortest route from A to X . Give the route and its corresponding distance.
   2. Would it need fewer computations to use Dijkstra's algorithm on the network for villages A to F to find the shortest route from A to C, and then use Dijkstra's algorithm on the network for villages U to Z to find the shortest route from Z to X? Give a brief justification for your answer.
2. The local council needs to discover which roads it should keep clear of snow during the winter to keep all the villages connected, and the corresponding total length of road.
   1. Use Kruskal's algorithm on the network for villages A to F to find a minimum connector for \(\{ \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } \}\). Show your use of the algorithm. Draw your minimum connector.
   2. Use Prim's algorithm on the network for villages U to Z to find a minimum connector for \(\{ \mathrm { U } , \mathrm { V } , \mathrm { W } , \mathrm { X } , \mathrm { Y } , \mathrm { Z } \}\), starting at U . Show your use of the algorithm. Draw your minimum connector.
   3. What is the total length of road that the council must keep clear of snow?