Edexcel IAL Mathematics D1.5.3 integer solutions in linear programming

Practise integer linear-programming decisions by checking whole-number feasible points against constraints and the problem context.

[Maximum number: 2]

Figure 5

Figure 5 shows a weighted graph that contains 12 arcs and 8 vertices.

It is given that
- no two arcs have the same weight
- x and y are positive integers
- arc CD is not in the minimum spanning tree for the graph

Using Diagram 1 only, write down the possible pairs of values that x and y can take in the form (x, y).

The minimum spanning tree for the weighted graph in Figure 5 has total weight 73 Six of the seven arcs in the minimum spanning tree are AB, AD, BC, CE, EF and GH.

dentroom.
B1ft.Wordyrees
B1

B1ft

B1

)

Total weight of the MST is therefore 14 x+5 y-4

A1

14 x+5 y-4=73 and testing integer value points inside FR

M1dep

x=3 and y=7

A1

15 marks

Notes for Question 7

a1M1: Explaining that if CD is not in the tree than AD must be e.g. 'the MST must contain D so if CD is not in the tree then AD is'. Must explicitly mention arc AD for this mark, so as a minimum accept, 'AD must be in the MST'

a1A1: Correct reasoning and derivation of the given result ( $2 y+x>3 y-7 \Rightarrow y<x+7$ ) - as the answer is given we must see at least 2 y+x>3 y-7 or 3 y-7<2 y+x before the required answer

SC (Special Case) in (a): $2 y+x>3 y-7 \Rightarrow y<x+7$ without any explanation given (or if explanation is incorrect) can score M1A0

b1B1: CAO - must see at least 4 x+1<2 y+1 before the given answer of y>2 x and not just arc $\mathrm{AB}<\operatorname{arc}$ AC or 4 x<2 y

b2B1: CAO (x>1) - but allow equivalents, e.g., x-1>0,1<x, 4 x>4, etc. but must be two terms only b3B1: CAO (3 y>4 x+8) - but allow exact equivalents e.g. $y>\frac{4}{3} x+\frac{8}{3}, \quad 4 x-3 y<-8, \quad 4 x+8-3 y<0$ , or equivalent but must be three terms only

In (c), the lines can be drawn as either dashed or non-dashed lines (or a combination of the two). The lines must be long enough to define the correct feasible region and pass through one small square of the points stated below:

y=2 x must pass within one small square of (0,0) and (7,14)

y=x+7 must pass within one small square of (0,7) and (7,14)

x=1 must pass within one small square of (1,0) and (1,10)

3 y=4 x+8 must pass within one small square of (1,4) and (7,12)

c1B1: Any one line correctly drawn (ignore any shading)

c2B1: Any two lines correctly drawn (ignore any shading)

c3B1: Any three lines correctly drawn (ignore any shading)

c4B1: All four lines correctly drawn and shading which implies the correct region (but region need not be labelled)

Figure for Answer to Question D1.5.3 - Consideration of problems where solutions must have integer question 1 — Edexcel A-Level Mathematics AS

d1B1ft: At least 4 pairs of integer coordinates correctly stated for points inside their region. Thesy mark is dependent on scoring at least the first two marks in (c) (so must have drawn at least two lines corregtly) and the candidate must have drawn exactly four lines. The region must not be infinite but need not ncessaujly be bounded by all four lines. If the candidate's region does not contain 4 integer coordinates then B0. Notechat integer points on the lines that define the boundary of the region are not counted as being inside the regiorisss (regardless of if the candidate has strict inequalities or not)
d2B1: All 9 coordinates correct (and no others) - dependent on all four lines correctly drawn in (c)

All question bank results loaded

D1.5.3 - Consideration of problems where solutions must have integer question 1