OCR FD1 AS (Further Decision 1 AS) 2018 March

1

1. (a) Show that the number of arrangements of 25 distinct objects is an integer multiple of \(5 ^ { 6 }\).
   (b) Explain how this shows that the number of arrangements of 25 distinct objects is a whole number of millions.
2. (a) Calculate the values of
   • INT(720 \(\div 25\) )
   • INT(720 \(\div 125\) ).
     (b) Deduce the largest power of 10 that is a factor of 720!
   • Use the inclusion-exclusion principle to find the number of integers from 1 to 720 that are not divisible by either 2 or 5 .

2 The diagram shows an incomplete solution to the problem of using Dijkstra's algorithm to find a shortest path from \(A\) to \(F\). Any cell that has values in it is complete.
\includegraphics[max width=\textwidth, alt={}, center]{a51b112d-1f3f-4214-94c1-8b9cd7eb831c-2_650_1246_1107_411}

1. (a) Find the missing weight on \(\operatorname { arc } B E\).
   (b) What can you deduce about the missing weight on arc \(C D\) ? You are now given that the weight of arc \(C E\) is not 3 .
2. (a) What can you deduce about the missing weight on arc \(C E\) ?
   (b) Complete the labelling of the boxes at \(E\) and \(F\) on the diagram in the Printed Answer Booklet. [2] Suppose that there are two shortest routes from \(A\) to \(F\).
3. Show how trace back is used to find the shortest routes from \(A\) to \(F\).

3 Lee and Maria are playing a strategy game. The tables below show the points scored by Lee and the points scored by Maria for each combination of strategies. Points scored by Lee Lee's choice \begin{table}[h] \end{table} Points scored by Maria Lee's choice
\includegraphics[max width=\textwidth, alt={}, center]{a51b112d-1f3f-4214-94c1-8b9cd7eb831c-3_335_481_392_1139}

1. Show how this game can be reformulated as a zero-sum game.
2. By first using dominance to eliminate one of Lee's choices, use a graphical method to find the optimal mixed strategy for Lee.

4 Deva is having some work done on his house. The table shows the activities involved, their durations and their immediate predecessors.

1. Model this information as an activity network.
2. Find the minimum time in which the work can be completed.
3. Describe the effect on the minimum project completion time of each of the following happening individually.
   (a) The duration of activity A is increased to 3.5 hours.
   (b) The duration of activity D is increased to 4 hours.
   (c) The duration of activity F is decreased to 2 hours. The decorators working on activity H cannot work for 3 hours without a break.
4. How would you adapt your model to incorporate the break?

5

1. How many arcs does the complete bipartite graph \(K _ { 5,5 }\) have? A subgraph of \(K _ { 5,5 }\) contains 5 arcs joining each of the elements of the set \(\{ 1,2,3,4,5 \}\) to an element in a permutation of the set \(\{ 1,2,3,4,5 \}\). Suppose that \(r\) is connected to \(p ( r )\) for \(r = 1,2,3,4,5\).
2. How many permutations would have \(p ( 1 ) \neq 1\) ?
3. Using the pigeonhole principle, show that for every permutation of \(\{ 1,2,3,4,5 \}\), the product \(\Pi _ { r = 1 } ^ { 5 } ( r - p ( r ) )\) is even (i.e. an integer multiple of 2, including 0 ).
4. Is the result in part (iii) true when the permutation is of the set \(\{ 1,2,3,4,5,6 \}\) ? Give a reason for your answer.

6 An online magazine consists of an editorial, articles, reviews and advertisements.
The magazine must have a total of at least 12 pages. The editorial always takes up exactly half a page. There must be at least 3 pages of articles and at most 1.5 pages of reviews. At least a quarter but fewer than half of the pages in the magazine must be used for advertisements. Let \(x\) be the number of pages used for articles, \(y\) be the number of pages used for reviews and \(z\) be the number of pages used for advertisements. The constraints on the values of \(x , y\) and \(z\) are: $$\begin{aligned} & x + y + z \geqslant 11.5
& x \geqslant 3
& y \leqslant 1.5
& 2 x + 2 y - 2 z + 1 \geqslant 0
& 2 x + 2 y - 6 z + 1 \leqslant 0
& y \geqslant 0 \end{aligned}$$

1. (a) Explain why \(x + y + z \geqslant 11.5\).
   (b) Explain why only one non-negativity constraint is needed.
   (c) Show that the requirement that at least one quarter of the pages in the magazine must be used for advertisements leads to the constraint \(2 x + 2 y - 6 z + 1 \leqslant 0\). Advertisements bring in money but are not popular with the subscribers. The editor decides to limit the number of pages of advertisements to at most four.
2. Graph the feasible region in the case when \(z = 4\) using the axes in the Printed Answer Booklet. To be successful the magazine needs to maximise the number of subscribers.
   The editor has found that when \(z \leqslant 4\) the expected number of subscribers is given by \(P = 300 x + 400 y\).
3. (a) What is the maximum expected number of subscribers when \(z = 4\) ?
   (b) By first considering the feasible region for \(z = k\), where \(k \leqslant 4\), find an expression for the maximum number of subscribers in terms of \(k\). \section*{END OF QUESTION PAPER} \section*{OCR} \section*{Oxford Cambridge and RSA}