Questions — OCR FD1 AS (16 questions)

1
\includegraphics[max width=\textwidth, alt={}, center]{a7bca340-6947-42b5-bc35-e6d429d6bed7-2_953_559_347_753}

1. Trace through the flowchart above using the input \(N = 97531\). You only need to record values when they change.
2. Explain why the process in the flowchart is finite.

2 Rahul is decorating a room. He needs to decorate at least \(30 \mathrm {~m} ^ { 2 }\) of the walls using paint, panelling or wallpaper. The cost ( \(\pounds\) ) and the time required (hours) to decorate \(1 \mathrm {~m} ^ { 2 }\) of wall are shown in the table. Rahul wants to complete decorating the walls in no more than 8 hours and wants to minimise the cost.
Set up an LP formulation for Rahul's problem, defining your variables. You are not required to solve this LP problem.

3 The activities involved in a project and their durations are represented in the activity network below.
\includegraphics[max width=\textwidth, alt={}, center]{a7bca340-6947-42b5-bc35-e6d429d6bed7-3_494_700_306_683}

1. Carry out a forward pass and a backward pass through the network.
2. Find the float for each activity. A delay means that the duration of activity E increases to \(x\).
3. Find the values of \(x\) for which activity E is not a critical activity.

4 Tom is planning a day out walking. He wants to start from his sister's house ( S ), then visit three places \(\mathrm { A } , \mathrm { B }\) and C (once each, in any order) and then finish at his own house (T).

1. Complete the graph in the Printed Answer Booklet showing all possible arcs that could be used to plan Tom's walk. Tom needs to keep the total distance that he walks to a minimum, so he weights his graph.
2. (a) Why would finding the shortest path from S to T , on Tom's network, not necessarily solve Tom's problem?
   (b) Why would finding a minimum spanning tree, on Tom's network, not necessarily solve Tom's problem? The distance matrix below shows the direct distances, in km , between places.

   	S	A	B	C	T
   n S	0	3	2	5	4
   nA	3	0	2	2.5	2
   nB	2	2	0	3.2	2.5
   n	5	2.5	3.2	0	2
   \cline { 2 - 6 } T	4	2	2.5	2	0
   \cline { 2 - 6 }
   \cline { 2 - 6 }

3. - Use an appropriate algorithm to find a minimum spanning tree for Tom's network.
   • Give the total weight of the minimum spanning tree.
   • - Find the route that solves Tom's problem.
   • Give the minimum distance that Tom must walk.

5 In each round of a card game two players each have four cards. Every card has a coloured number.

• Player A's cards are red 1 , blue 2 , red 3 and blue 4.
• Player B's cards are red 1 , red 2 , blue 3 and blue 4 .

Each player chooses one of their cards. The players then show their choices simultaneously and deduce how many points they have won or lost as follows:

• If the numbers are the same both players score 0 .
• If the numbers are different but are the same colour, the player with the lower value card scores the product of the numbers on the cards.
• If the numbers are different and are different colours, the player with the higher value card scores the sum of the numbers on the cards.
• The game is zero-sum.
  1. Complete the pay-off matrix for this game, with player A on rows.
  2. Determine the play-safe strategy for each player.
  3. Use dominance to show that player A should not choose red 3 . You do not need to identify other rows or columns that are dominated.
  4. Determine, with a reason, whether the game is stable or unstable.

6 This list is to be sorted into decreasing order, ending up with 31 in the first position and 4 in the last position.
15
4
12
23
14
16
27
31 Initially bubble sort is used.

1. Record the list at the end of the first, second and third passes. You do not need to show the individual swaps in each pass. After the fourth pass the list is:
   23
   15
   16
   27
   31
   14
   12

15
4
12
23
14

16
27
31 Initially bubble sort is used.

1. Record the list at the end of the first, second and third passes. You do not need to show the individual swaps in each pass. After the fourth pass the list is:
   23
   15
   16
   27
   31
   14
   12
   9
   4 The sorting is then continued using shuttle sort on this list.
2. Record the list at the end of each of the first, second and third passes of shuttle sort. You do not need to show the individual swaps in each pass.
3. How many passes through shuttle sort are needed to complete the sort? Explain your reasoning.
4. A digraph is represented by the adjacency matrix below. $$\begin{gathered}
   
   
   
   
   
   \text { from } \end{gathered} \begin{gathered}
   \mathrm { A }
   \mathrm {~B}
   \mathrm { C } \end{gathered} \quad \quad \left( \begin{array} { c c c } 1 & \mathrm {~B} & \mathrm { C }
   1 & 1 & 0
   0 & 0 & 0
   0 & 1 & 0 \end{array} \right)$$ (a) For each vertex, write down
   • the indegree,
   • the outdegree.
     (b) Explain how the indegrees and outdegrees show that the digraph is semi-Eulerian.
   • A graph is represented by the adjacency matrix below.
   $$\left. \begin{array} { c }
   \mathrm { D }
   \mathrm { E }
   \mathrm {~F} \end{array} \quad \begin{array} { c c c } \mathrm { D } & \mathrm { E } & \mathrm {~F}
   2 & 1 & 0
   1 & 0 & 2
   0 & 2 & 0 \end{array} \right)$$ (a) Explain how the numerical entries in the matrix show that this can be drawn as an undirected graph.
   (b) Explain how the adjacency matrix shows that this graph is semi-Eulerian.
5. By referring to the vertex degrees, explain why the loop from A to itself is shown as a 1 in the adjacency matrix in part (i) but the loop from \(D\) to itself is shown as 2 in the adjacency matrix in part (ii).
6. List the 15 partitions of the set \(\{ \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } \}\). Amy, Bao, Cal and Dana want to travel by taxi from a meeting to the railway station. They book taxis but only two taxis turn up. Each taxi must have a minimum of one passenger and can carry a maximum of four passengers. Dana jumps into one of the taxis.
7. Find the number of ways that Amy, Bao and Cal can be split between the two taxis. Amy does not want to travel in the same taxi as Bao.
8. Determine the number of ways that Amy, Bao and Cal can be split between taxis with this additional restriction. Six people want to travel by taxi from a hotel to the railway station using taxis. There must be a minimum of one passenger and a maximum of four passengers in each taxi. The taxis may be regarded as being indistinguishable.
9. Calculate how many ways there are of splitting the six people between taxis. \section*{END OF QUESTION PAPER} \section*{OCR} Oxford Cambridge and RSA

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}

4 Two graphs are shown below. Each has exactly five vertices with vertex orders 2, 3, 3, 4, 4 . \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Write down a semi-Eulerian route for graph 1.
2. Explain how the vertex orders show that graph 2 is also semi-Eulerian.
3. By referring to specific vertices, explain how you know that these graphs are not simple.
4. By referring to specific vertices, explain how you know that these graphs are not isomorphic.

8 A sweet shop sells three different types of boxes of chocolate truffles. The cost of each type of box and the number of truffles of each variety in each type of box are given in the table below. \section*{2. Subject-specific Marking Instructions for AS Level Further Mathematics A} Annotations should be used whenever appropriate during your marking. The A, M and B annotations must be used on your standardisation scripts for responses that are not awarded either 0 or full marks. It is vital that you annotate standardisation scripts fully to show how the marks have been awarded. For subsequent marking you must make it clear how you have arrived at the mark you have awarded. An element of professional judgement is required in the marking of any written paper. Remember that the mark scheme is designed to assist in marking incorrect solutions. Correct solutions leading to correct answers are awarded full marks but work must not be judged on the answer alone, and answers that are given in the question, especially, must be validly obtained; key steps in the working must always be looked at and anything unfamiliar must be investigated thoroughly. Correct but unfamiliar or unexpected methods are often signalled by a correct result following an apparently incorrect method. Such work must be carefully assessed. When a candidate adopts a method which does not correspond to the mark scheme, escalate the question to your Team Leader who will decide on a course of action with the Principal Examiner.
If you are in any doubt whatsoever you should contact your Team Leader.
The following types of marks are available. \section*{M} A suitable method has been selected and applied in a manner which shows that the method is essentially understood. Method marks are not usually lost for numerical errors, algebraic slips or errors in units. However, it is not usually sufficient for a candidate just to indicate an intention of using some method or just to quote a formula; the formula or idea must be applied to the specific problem in hand, e.g. by substituting the relevant quantities into the formula. In some cases the nature of the errors allowed for the award of an M mark may be specified. \section*{A} Accuracy mark, awarded for a correct answer or intermediate step correctly obtained. Accuracy marks cannot be given unless the associated Method mark is earned (or implied). Therefore M0 A1 cannot ever be awarded. \section*{B} Mark for a correct result or statement independent of Method marks. \section*{E} Mark for explaining a result or establishing a given result. This usually requires more working or explanation than the establishment of an unknown result.
Unless otherwise indicated, marks once gained cannot subsequently be lost, e.g. wrong working following a correct form of answer is ignored. Sometimes this is reinforced in the mark scheme by the abbreviation isw. However, this would not apply to a case where a candidate passes through the correct answer as part of a wrong argument.
d When a part of a question has two or more 'method' steps, the M marks are in principle independent unless the scheme specifically says otherwise; and similarly where there are several B marks allocated. (The notation 'dep*' is used to indicate that a particular mark is dependent on an earlier, asterisked, mark in the scheme.) Of course, in practice it may happen that when a candidate has once gone wrong in a part of a question, the work from there on is worthless so that no more marks can sensibly be given. On the other hand, when two or more steps are successfully run together by the candidate, the earlier marks are implied and full credit must be given.
e The abbreviation FT implies that the A or B mark indicated is allowed for work correctly following on from previously incorrect results. Otherwise, A and B marks are given for correct work only - differences in notation are of course permitted. A (accuracy) marks are not given for answers obtained from incorrect working. When A or B marks are awarded for work at an intermediate stage of a solution, there may be various alternatives that are equally acceptable. In such cases, what is acceptable will be detailed in the mark scheme. If this is not the case please, escalate the question to your Team Leader who will decide on a course of action with the Principal Examiner.
Sometimes the answer to one part of a question is used in a later part of the same question. In this case, A marks will often be 'follow through'. In such cases you must ensure that you refer back to the answer of the previous part question even if this is not shown within the image zone. You may find it easier to mark follow through questions candidate-by-candidate rather than question-by-question.
f Unless units are specifically requested, there is no penalty for wrong or missing units as long as the answer is numerically correct and expressed either in SI or in the units of the question (e.g. lengths will be assumed to be in metres unless in a particular question all the lengths are in km , when this would be assumed to be the unspecified unit.) We are usually quite flexible about the accuracy to which the final answer is expressed; over-specification is usually only penalised where the scheme explicitly says so. When a value is given in the paper only accept an answer correct to at least as many significant figures as the given value. This rule should be applied to each case. When a value is not given in the paper accept any answer that agrees with the correct value to 2 s .f. Follow through should be used so that only one mark is lost for each distinct accuracy error, except for errors due to premature approximation which should be penalised only once in the examination. There is no penalty for using a wrong value for \(g\). E marks will be lost except when results agree to the accuracy required in the question.
g Rules for replaced work: if a candidate attempts a question more than once, and indicates which attempt he/she wishes to be marked, then examiners should do as the candidate requests; if there are two or more attempts at a question which have not been crossed out, examiners should mark what appears to be the last (complete) attempt and ignore the others. NB Follow these maths-specific instructions rather than those in the assessor handbook.
h For a genuine misreading (of numbers or symbols) which is such that the object and the difficulty of the question remain unaltered, mark according to the scheme but following through from the candidate's data. A penalty is then applied; 1 mark is generally appropriate, though this may differ for some papers. This is achieved by withholding one A mark in the question. Marks designated as cao may be awarded as long as there are no other errors. E marks are lost unless, by chance, the given results are established by equivalent working. 'Fresh starts' will not affect an earlier decision about a misread. Note that a miscopy of the candidate's own working is not a misread but an accuracy error.
i If a calculator is used, some answers may be obtained with little or no working visible. Allow full marks for correct answers (provided, of course, that there is nothing in the wording of the question specifying that analytical methods are required). Where an answer is wrong but there is some evidence of method, allow appropriate method marks. Wrong answers with no supporting method score zero. If in doubt, consult your Team Leader.
j If in any case the scheme operates with considerable unfairness consult your Team Leader. \end{table} PS = Problem Solving
M = Modelling \section*{Accredited} \section*{AS Level Further Mathematics A} \section*{Unit Y534 Discrete Mathematics} \section*{Printed Answer Booklet} \section*{Date - Morning/Afternoon} \section*{Time allowed: 1 hour 15 minutes} OCR supplied materials:

• Printed Answer Booklet
• Formulae AS Level Further Mathematics A

You must have:

• Printed Answer Booklet
• Formulae AS Level Further Mathematics A
• Scientific or graphical calculator
  \includegraphics[max width=\textwidth, alt={}, center]{da50ab63-a6f5-4533-ba6d-f9941b71038f-25_321_1552_1320_246}

\section*{INSTRUCTIONS}

• Use black ink. HB pencil may be used for graphs and diagrams only.
• Complete the boxes provided on the Printed Answer Booklet with your name, centre number and candidate number.
• Answer all the questions.
• Write your answer to each question in the space provided in the Printed Answer Booklet.
• Additional paper may be used if necessary but you must clearly show your candidate number, centre number and question number(s).
• Do not write in the bar codes.
• You are permitted to use a scientific or graphical calculator in this paper.
• Final answers should be given to a degree of accuracy appropriate to the context.
• The acceleration due to gravity is denoted by \(g \mathrm {~m} \mathrm {~s} ^ { - 2 }\). Unless otherwise instructed, when a numerical value is needed, use \(g = 9.8\).

\section*{INFORMATION}

• You are reminded of the need for clear presentation in your answers.
• The Printed Answer Booklet consists of \(\mathbf { 1 2 }\) pages. The Question Paper consists of \(\mathbf { 8 }\) pages.

5(iv) 6(i) \section*{PLEASE DO NOT WRITE ON THIS PAGE} \section*{Copyright Information:} OCR is committed to seeking permission to reproduce all third-party content that it uses in the assessment materials. OCR has attempted to identify and contact all copyright holders whose work is used in this paper. To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced in the OCR Copyright Acknowledgements booklet. This is produced for each series of examinations and is freely available to download from our public website (\href{http://www.ocr.org.uk}{www.ocr.org.uk}) after the live examination series. If OCR has unwittingly failed to correctly acknowledge or clear any third-party content in this assessment material, OCR will be happy to correct its mistake at the earliest possible opportunity. For queries or further information please contact the Copyright Team, First Floor, 9 Hills Road, Cambridge CB2 1GE.
OCR is part of the Cambridge Assessment Group; Cambridge Assessment is the brand name of University of Cambridge Local Examinations Syndicate (UCLES), which is itself a department of the University of Cambridge