GCE Further Mathematics A Y544/01: Discrete Mathematics Advanced GCE Mark Scheme for Autumn 2021

Document Content and Description Below

Oxford Cambridge and RSA Examinations GCE Further Mathematics A Y544/01: Discrete Mathematics Advanced GCE Mark Scheme for Autumn 2021Oxford Cambridge and RSA Examinations OCR (Oxford Cambridge ... and RSA) is a leading UK awarding body, providing a wide range of qualifications to meet the needs of candidates of all ages and abilities. OCR qualifications include AS/A Levels, Diplomas, GCSEs, Cambridge Nationals, Cambridge Technicals, Functional Skills, Key Skills, Entry Level qualifications, NVQs and vocational qualifications in areas such as IT, business, languages, teaching/training, administration and secretarial skills. It is also responsible for developing new specifications to meet national requirements and the needs of students and teachers. OCR is a not-for-profit organisation; any surplus made is invested back into the establishment to help towards the development of qualifications and support, which keep pace with the changing needs of today’s society. This mark scheme is published as an aid to teachers and students, to indicate the requirements of the examination. It shows the basis on which marks were awarded by examiners. It does not indicate the details of the discussions which took place at an examiners’ meeting before marking commenced. All examiners are instructed that alternative correct answers and unexpected approaches in candidates’ scripts must be given marks that fairly reflect the relevant knowledge and skills demonstrated. Mark schemes should be read in conjunction with the published question papers and the report on the examination. © OCR 2021Y544/01 Mark Scheme October 2021 2 Annotations and abbreviations Annotation in RM assessor Meaning ✓and  BOD Benefit of doubt FT Follow through ISW Ignore subsequent working M0, M1 Method mark awarded 0, 1 A0, A1 Accuracy mark awarded 0, 1 B0, B1 Independent mark awarded 0, 1 SC Special case ^ Omission sign MR Misread BP Blank Page Seen Highlighting Other abbreviations in mark scheme Meaning dep* Mark dependent on a previous mark, indicated by *. The * may be omitted if only one previous M mark cao Correct answer only oe Or equivalent rot Rounded or truncated soi Seen or implied www Without wrong working AG Answer given awrt Anything which rounds to BC By Calculator DR This question included the instruction: In this question you must show detailed reasoning.Y544/01 Mark Scheme October 2021 3 2. Subject-specific Marking Instructions for A Level Mathematics A a Annotations must be used during your marking. For a response awarded zero (or full) marks a single appropriate annotation (cross, tick, M0 or ^) is sufficient, but not required. For responses that are not awarded either 0 or full marks, you must make it clear how you have arrived at the mark you have awarded and all responses must have enough annotation for a reviewer to decide if the mark awarded is correct without having to mark it independently. It is vital that you annotate standardisation scripts fully to show how the marks have been awarded. Award NR (No Response) - if there is nothing written at all in the answer space and no attempt elsewhere in the script - OR if there is a comment which does not in any way relate to the question (e.g. ‘can’t do’, ‘don’t know’) - OR if there is a mark (e.g. a dash, a question mark, a picture) which isn’t an attempt at the question. Note: Award 0 marks only for an attempt that earns no credit (including copying out the question). If a candidate uses the answer space for one question to answer another, for example using the space for 8(b) to answer 8(a), then give benefit of doubt unless it is ambiguous for which part it is intended. b 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 always 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.Y544/01 Mark Scheme October 2021 4 c The following types of marks are available. 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. A method mark may usually be implied by a correct answer unless the question includes the DR statement, the command words “Determine” or “Show that”, or some other indication that the method must be given explicitly. 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. B Mark for a correct result or statement independent of Method marks. 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.Y544/01 Mark Scheme October 2021 5 f 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. • When a value is not given in the paper accept any answer that agrees with the correct value to 3 s.f. unless a different level of accuracy has been asked for in the question, or the mark scheme specifies an acceptable range. NB for Specification B (MEI) the rubric is not specific about the level of accuracy required, so this statement reads “2 s.f”. Follow through should be used so that only one mark in any question is lost for each distinct accuracy error. Candidates using a value of 9.80, 9.81 or 10 for g should usually be penalised for any final accuracy marks which do not agree to the value found with 9.8 which is given in the rubric. g Rules for replaced work and multiple attempts: • If one attempt is clearly indicated as the one to mark, or only one is left uncrossed out, then mark that attempt and ignore the others. • If more than one attempt is left not crossed out, then mark the last attempt unless it only repeats part of the first attempt or is substantially less complete. • if a candidate crosses out all of their attempts, the assessor should attempt to mark the crossed out answer(s) as above and award marks appropriately. 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 units. This is achieved by withholding one A or B mark in the question. Marks designated as cao may be awarded as long as there are no other errors. If a candidate corrects the misread in a later part, do not continue to follow through. 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 that there is nothing in the wording of the question specifying that analytical methods are required such as the bold “In this question you must show detailed reasoning”, or the command words “Show” or “Determine”. 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.Y544/01 Mark Scheme October 2021 6 Question Answer Mark AO Guidance 1 (a) Bag 1: A B D Bag 2: C E Bag 3: F Bag 4: G Bag 5: H M1* M1dep* A1 [3] 1.1 1.1 1.1 Bag 1 starts A B (or 3 4) and bag 2 starts C (or 3.5) D is in bag 1 and E is in bag 2 (using letters) All correct (using letters and in the correct order within bags) 1 (b) G must be in a bag on its own, since 8 + 2.5 > 10 The remaining seven items have total mass 31.5 kg > 310 kg M1 A1 3.4 2.3 G must be on its own Explaining why this means that 4 bags are not enough Alternative method 4 bags would mean 3 full bags and one with 9.5 kg G must be in a bag on its own, since 10 – 8 = 2 < 2.5 So cannot make a bag containing G with mass 9.5 or 10 kg G must be its own or identifying ways to make 10 or 9.5 [2] 1 (c) Leave A behind EB, FD, G, HC or EC, FD, G, HB Must leave out at least one. The value of A is the smallest so this is the best possibility. B1 B1ft B1 2.2a 3.1b 3.4 A A possible packing Value of A is lower than any other A has the lowest value SC B1 leave F because it has the lowest value per kg [3]Y544/01 Mark Scheme October 2021 7 Question Answer Mark AO Guidance 2 (a) (i) 1 because the graph is connected B1 1.1 ‘1’ and explaining why 0 is not possible [1] (ii) 4 because if there is a vertex of degree 5 then the other three vertices must all be even and have degree sum 16 – (3+4+5) = 4, which is not possible B1 1.1 ‘4’ and explaining why 5 is not possible [1] 2 (b) 1, 2, 2, 3, 4, 4 2, 2, 2, 3, 3, 4 M1 A1 1.1 1.2 Values in either list correct, given in any order Both lists correct, in this form, each in increasing order (allow decreasing order) and no others [2] 2 (c) J K L M N Indegree 2 2 4 2 2 Outdegree 2 2 2 4 2 M1 A1 1.1 1.2 Indegree = column total, outdegree = row total Both rows correct, although rows may be interchanged Completely correct [2] 2 (d) (i) Not Eulerian, for a digraph to be Eulerian the indegree must equal the outdegree for each vertex B1 1.1 Not Eulerian, indegree  outdegree for L (or M) Discussion of odd/even vertex degrees is wrong here, need to use indegrees and outdegrees for a digraph Saying ‘Eulerian since all even’ is also wrong [1] (ii) Connected but not simple, there are two arcs from M to L B1 1.1 Not simple with a valid reason Alternative method Not simple, there is a (directed) loop at M [1]Y544/01 Mark Scheme October 2021 8 Question Answer Mark AO Guidance 3 (a) 150 cards shared equally between 7 (= 6 players and stack) = 21.43 So at least one has 22 or more cards B1 2.2a Or 217 = 147 < 150 (conclusion may be implied, since given in question) [1] 3 (b) One-digit numbers: 1, 4, 6, 7, 8, 9 are not red = 6 cards Two-digit numbers: tens digit must be 1, 4, 6, 7, 8, 9 and units digit can be any of 0, 1, 4, 6, 7, 8, 9 = 67 = 42 cards Three-digit numbers: Hundreds digit is 1, tens digit must be 0, 1, 4 and units digit can be any of 0, 1, 4, 6, 7, 8, 9 = 37 = 21 cards 6 + 42 + 21 = 69 cards with no red digits M1 A1 1.1 1.1 Listing/describing 6 one-digit numbers with no red digits and making a good attempt at counting the number of two-digit numbers with no red digits Or appropriate sight of any two of 6, 42, 21 Or implied from final answer 69 Final answer 69 Alternative method One-digit numbers: 2, 3, 5 are red = 3 cards Two-digit numbers: 9 + 21 + 18 = 48 RR = 3×3 = 9; RN = 3×7 = 21; NR = 6×3 = 18 Three-digit numbers: 6 + 15 + 9 = 30 1RR = 2×3 = 6; 1RN = 2×7 + 1 = 15; 1NR = 3×3 = 9 3 + 48 + 30 = 81 cards with at least one red digit 150 – 81 = 69 cards with no red digits Listing/describing 3 one-digit numbers with a red digit and making a good attempt at counting the number of two-digit numbers with at least one red digit Or appropriate sight of any two of 3, 48, 30 Or implied from 81 or from final answer 69 Final answer 69 [2] 3 (c) Cards in set A are multiples of 2, so units digit is 0, 2, 4, 6 or 8 One-digit numbers: 4, 6, 8 are not red = 3 cards Two-digit numbers: tens digit can be any of 1, 4, 6, 7, 8, 9 and units digit can be any of 0, 4, 6, 8 = 64 = 24 cards Three-digit numbers: tens digit must be 0, 1, 4 = 34 = 12 cards 3+24+12 = 39 cards in A with no red digits M1 A1 3.1a 1.1 4, 6, 8 or 0, 4, 6, 8 as units digit Trying to count even cards (or odd cards) with no red digits (or with red digits) Or implied from final answer 39 Final answer 39 [2] 3 (d) Cards in C with no red digits must have units digit 0, so n(A  C) = 9 60 and 90 are both even, so n(A  B  C) = 2 69 – (39 + 21 + 9) + ( 12 + 9 + 2) – 2 = 21 cards M1* M1dep* A1 1.1 1.1 1.1 n(A  C) = 9 and n(A  B  C) = 2 seen or implied Using inclusion-exclusion Their 69 (from part (b)) – their 39 (from part(c)) – 9 21 from correct working seen [3]Y544/01 Mark Scheme October 2021 9 Question Answer Mark AO Guidance 4 (a) Graph A K2,3 is a bipartite graph with 2 vertices in one set and 3 in the other so the two vertices of degree 3 are not adjacent but in graph A the two vertices of degree 3 are adjacent B1 2.4 ‘A’ and an appropriate comment about adjacency of vertices with the same degree or cycle lengths in A Description of K2,3 may be implied Alternative method 1 Graph A K2,3 is a bipartite graph with 2 vertices in one set and 3 in the other so none of the three vertices of degree 2 are adjacent but in graph A the two of the vertices of degree 2 are adjacent Alternative method 2 Graph A K2,3 is a bipartite graph so cycles are of even length (length 4) but in graph A there is a cycle of length 3 (or of length 5) Graph C K2,3 has 5 vertices and 6 arcs but graph C has 8 arcs so not isomorphic to K2,3 B1 2.4 ‘C’ and an appropriate comment about number of arcs or degrees of vertices or cycle lengths Description of K2,3 may be implied Alternative method 1 Graph C Degree sequence for K2,3 is 2, 2, 2, 3, 3 but graph C has no vertices of degree 2 (or has a vertex of degree 4) Alternative method 2 Graph C K2,3 is a bipartite graph so cycles are of even length (length 4) but in graph C there are cycles of length 3 (or of length 5) [2] 4 (b) B1 1.1 A graph that is isomorphic to this [1] 4 (c) By Kuratowski’s theorem, K5 is non-planar, so thickness  2 K5 = K2, 3 + G from part (a), both of these are planar so thickness  2 Hence thickness = 2 B1 M1 A1 2.5 3.1a 2.1 Kuratowski, K5 is non-planar Partitioning K5 as two planar graphs, eg K2, 3 and G and attempt to explain that each of these is planar Complete reasoning [3]Y544/01 Mark Scheme October 2021 10 Question Answer Mark AO Guidance 4 (d) Not bipartite, two adjacent vertices both coloured  M1 A1 A1 1.1 1.1 1.1 If more than one diagram is used mark the final diagram Top left = , top right and bottom left =  Bottom right and centre =  Correct conclusion with reason (step 5 of algorithm) [3] 4 (e) 1 B1 1.1 cao [1] 4 (f) Linear or O(n) B1 2.2a Not n, n – 1, 1 2� or 1 2(� − 1) or similar (which is T(n)) [1] 4 (g) 1000  (60  10) = 6000 B1ft 2.2b correct or follow through order from part (f) [1] 4 (h) O(n)  O(2n) hierarchy of orders B1 2.4 26000 21000 > 6, or equivalent [1]Y544/01 Mark Scheme October 2021 11 Question Answer Mark AO Guidance 5 (a) (i) Row minima are min(x, 2), -2, -3 If x  2, row maximin = 2 and col minimax = 2  stable game M1 A1 1.1 1.1 Row minima (P = x, 2; Q = –2; R = –3) Stable when x  2 Allow x > 2 [2] (ii) Column maxima are max(x, 4), 3, 2 P is a play-safe strategy  x  -2 If -2  x < 2, row maximin = x and col minimax = 2 unstable M1 A1 1.1 1.1 Column maxima, or equivalent (or implied from part (a)(i)) Unstable when -2  x < 2 Accept -2 < x < 2 but not just x < 2 [2] 5 (b) X Y Z P x 3 2 Q 4 0 -2 B1 1.1 Row R deleted [1] 5 (c) If Beth plays X: Alex expects px + 4(1 – p) or 4 + (x – 4)p If Beth plays Y: Alex expects 3p If Beth plays Z: Alex expects 2p – 2(1 – p) or 4p – 2 4p – 2 = px + 4(1 – p)  p = 6 8−� M1 A1 M1 A1 3.1a 3.1a 3.2a 1.1 Calculating expressions for at least two of these All three correct in any form Graph is optional and carries no marks Setting their expression for X = 4p – 2 or = 3p Correct expression for p [4]Y544/01 Mark Scheme October 2021 12 Question Answer Mark AO Guidance 5 (d) Add 5 (or greater) throughout to make all entries non-negative 0 8 7 9 5 3 2 4 2 Choose row P with probability p, row Q with probability q and row R with probability r Maximise M = m – 5 Subject to m  9q + 2r m  8p + 5q + 4r m  7p + 3q + 2r p + q + r  1 and m, p, q, r  0 B1 B1 B1 3.3 3.4 3.4 Add a constant throughout to make all entries non-negative Or using reduced matrix Need not be stated, may use different notation e.g. p1, p2, p3 m  ap + bq + cr where a, b, c are the values from a column of their matrix (or the original matrix if no evidence of change to matrix) Or m  ap + bq using reduced matrix p + q + r  1 (not p + q + r = 1) Or p + q  1 using reduced matrix [3]Y544/01 Mark Scheme October 2021 13 Question Answer Mark AO Guidance 6 (a) Maximise P = –2x + 5y B1 3.3 –2x + 5y or 5y – 2x or either of these + a constant, but not 2x – 5y, and not for P + 2x – 5y = 0 (or a constant) Subject to 2x + y ≤ 25.8 –x + 3y ≤ 13.8 4x – 3y ≤ 18.8 B1 3.3 All three constraints in this form, or 2x + y – 25.8 ≤ 0 etc. Not for expressions that use the slack variables Non-negativity given in Printed Answer Booklet [2] 6 (b) An optimal solution to the constrained problem is P = 21 when x = 2 and y = 5 M1 A1 M1 A1 M1 A1 1.1 3.4 1.1 2.1 2.1 3.4 y ≤ 4 and y ≥ 5, or implied from values in next row Either of “P = 20 at x = 0, y = 4” or “P = 22.6 at x = 1.2, y = 5” Branching on x-values appropriately (x ≤ 1 and y ≥ 5 is) infeasible, or no solutions, or equivalent Values for third branching and branching on y-values appropriately P = 22.3 (221 3) at x = 2, y = 5.27 (515 4 ) and branching on yvalues appropriately P = 21 when x = 2 and y = 5 identified as solution [6] 6 (c) The boundary of the feasible region will change The line through (4.7, 0) will have the same gradient but will pass through (0, 0) The upper boundary (–x + 3y ≤ 13.8) is unchanged in the region of the solution, 4×2 – 3×5 < 0 Solution does not change, P = 21 when x = 2 and y = 5 B1 M1ft A1 3.5c 3.3 1.1 Answer may be given in space for 6(b), allow this Showing or describing change to feasible region Verifying that (2, 5) is still feasible or explaining why the change to the boundary does not affect the solution Saying that solution is unchanged or stating solution Correct solution only [3]Y544/01 Mark Scheme October 2021 14 Question Answer Mark AO Guidance 7 (a) (i) Original list 2.9 0.9 1.5 3.5 4.2 5.3 4.7 2.3 After 1st pass 0.9 1.5 2.9 3.5 4.2 4.7 2.3 5.3 After 2nd pass 0.9 1.5 2.9 3.5 4.2 2.3 4.7 (5.3) M1 A1 1.1 1.1 Substantially correct method, starting at left hand end of list, e.g. 1st pass correct Both passes correct, need not show 5.3 in small font If sorted into decreasing order: After 1st pass 2.9 1.5 3.5 4.2 5.3 4.7 2.3 0.9 After 2nd pass 2.9 3.5 4.2 5.3 4.7 2.3 1.5 (0.9) SC1 only Both passes correct, need not show 0.9 in small font [2] (ii) Original list 2.9 0.9 1.5 3.5 4.2 5.3 4.7 2.3 After 1st pass 0.9 2.9 (1.5) (3.5) (4.2) (5.3) (4.7) (2.3) After 2nd pass 0.9 1.5 2.9 (3.5) (4.2) (5.3) (4.7) (2.3) M1 A1 1.1 1.1 Substantially correct method, e.g. 0.9 jumps over 2.9 Both passes correct, need not show figures in small font [2] 7 (b) Bubble sort uses 7 + 6 + 14 = 27 comparisons Shuttle sort uses 1 + 2 + 11 = 14 comparisons Number of swaps is the same for both sorts, shuttle sort uses fewer comparisons, so shuttle sort is more efficient B1 B1 B1ft 1.1 1.1 2.4 27 comparisons for bubble 14 comparisons for shuttle (bubble = 4+1+3 = 8 swaps, shuttle = 1+1+6 = 8 swaps) Swaps same, shuttle more efficient (need both of these) [3] 7 (c) (i) 2.3 Must have 0.9 and 1.5 but then 2.3 may form a triangle B1 B1 3.1a 2.4 [2] (ii) e.g. e.g. Weight of MST = 9.5 M1 A1 B1 3.1a 2.4 1.1 Many possible solutions 0.9, 1.5 and 2.3 form a triangle 2.9, 3.5 and one lower weight arc form a triangle 0.9 + 1.5 + 2.9 + 4.2 = 9.5 [3] (iii) eg eg 2.3 + 4.7 = 7.0 0.9 + 4.2 = 5.1 2.9 + 5.3 = 8.2 2.9 + 5.3 = 8.2 (0.9+4.2) + (1.5+3.5) = 10.1 (0.9+2.9) + (0.9+5.3) = 10.0 Sum of weights = 25.3 Sum of weights = 25.3 25.3 + 7.0 = 32.3 25.3 + 5.1 = 30.4 M1 B1 A1ft 2.1 2.2a 1.1 Follow through their network from (c)(ii) Attempt to pair the four odd vertices Sum of arc weights = 25.3 seen Their seen 25.3 + their claimed least weight pairing [3]OCR (Oxford Cambridge and RSA Examinations) The Triangle Building Shaftesbury Road Cambridge CB2 8EA OCR Customer Contact Centre [Show More]

Last updated: 2 years ago

Preview 1 out of 16 pages