Transcript Jan 11 Model Answers File

AS Maths
Decision Paper
January 2011
Model Answers
It is important students
have a copy of the
questions as you go
through the model
answers.
Grade Boundaries
Grade
A
B
C
D
E
Marks
61
55
49
43
37
1a)
1
2
3
4
5
6
A
0
0
0
1
1
0
B
0
0
1
0
1
1
C
D
0
0
0
1
0
0
1
0
0
0
0
1
E
0
1
0
1
0
0
F
1
0
1
0
1
0
This is an adjacency
matrix
Initial Matchings
A
1
B
2
C
3
D
4
E
5
F
6
There are
alternate
ways to
find the
final
matchings
One potential matching is
A - 5 / B - 6 then
C-4
/ E -2 / D -6 / B -3 / F -1
You must show your Final Matchings Match A5, B3, C4, D6, E2, F1
a) The pivots used after the first pass and therefore
for the second pass are 7 and 22
b) First Pass
7
Second Pass 5
Third Pass 3
c) No, because 16 and 19 have
not been compared
EB = 5
EH = 7
AB = 8
HI = 9
AD = 10
DG = 4
EF = 12
FC = 6
Length of spanning tree = 5 + 7 + 8 + 9 + 10 + 4 + 12 + 6 =
61
aiii)
A
b)
B
A
8
B
C
C
5
E
D
F
E
D
F
11
G
H
I
G
H
I
Original Spanning tree = 61
AB and BE dropped = -13
GE added= 11
New Spanning tree = (61 – 13 + 11) = 59
A–D–F–I–J
12
9
11.5
12
7.5
13.5
0
21 19.5
18
13.5
12
10.5
18 15
The minimum time from A to G
is 12 minutes
If you use the subway (CG) this
time is reduced. You must use
AC = 7.5 + the subway
Therefore the subway (CG) must
be < 4.5 (12 – 7.5)
The minimum time from A to J is
not reduced . The time taken
from A to J is 18 minutes (last
question)
The time taken for CG must be 1.5 ≤ x < 4.5
If you use the subway, then to get
to J you must use AC and GJ =
16.5 minutes (7.5 + 9)
As the minimum time is not
reduced then CG ≥ 1.5
The graph is neither
Eulerian or semi
Eulerian as it has 4
odd vertices
These are the ODD vertices
AB + GH
AB (180) + GH (165) = 345
AG + BH
AG (90) + BH (210) = 300
AH + BG
AH (150) + BG (210) = 360
Repeat AG + BH = 300
Length of route =
1215 + 300 =
1515 metres
Repeated edges
AG (90) +
BH (210) =
300
F now has 6 edges so
will be visited 6 ÷ 2
times = 3
H now has 4 edges so
will be visited 4 ÷ 2
times = 2
Add the repeated edges
on to your graph
A complete graph for k 5 is shown
A
Starting at A there are 4 unused edges
E
B
From B there are 3 unused edges
From C there are 2 unused edges
From D there is 1 unused edge
D
C
From E there are 0 unused edges
Total number of edges is 4 + 3 + 2 + 1 = 10 Edges
aii) The number of edges in a minimum
spanning tree for graph k5 is n – 1
vertices = 5 – 1 = 4
A
E
B
D
C
aiii) As a HAMILTONIAN cycle visits each
vertex once, returning to the start vertex,
then
5 Edges (An example is shown)
A
b) A simple graph has six vertices.
B
F
C
E
D
It also has 9 edges an is Eulerian
which means every vertex will have
an even number of edges leaving
them
A has 4 edges, B has 2 edges, C has 4
edges, D has 2 edges, E has 4 edges
and F has 2 edges
B
B
A
C
3 + 11 + 5
A
3 +
E
5 + 10
D
E
+ 10 + 4
D
C
+ 5 +
B
= 33
B
18
= 41
You are left with A, B, D, E the nearest neighbour produces a
spanning tree like this
Now add the two shortest
neighbours to C which are A
3
A
B
CD = 5 and
CA = 11
4
= 17
11
Total is 17 + 16
D
E
C
10
= 33
5
D
3
A
B
4
11
E
C
10
5
D
It is an optimal journey
KEY INFORMATION
Ques 8
A
B
Line 20
20
8
Line 60
10
Line 10
Line 70
Line 60
Line 70
Line 40
X
0
16
5
32
32
Line 60
Line 70
Line 60
Line 70
Line 40
Line 90
Print
2
1
64
128
160
160
The algorithm defines the MULTIPLICATION of A and B
If Line 50 read If A = 1, then go to Line 80 it would create
A CONTINUOUS LOOP as it will never reach LINE 90
Tins
6x + 9y + 9z ≤ 600
Simplified
2x + 3y + 3z ≤ 200
Packets
9x + 6y + 9z ≤ 600
Simplified
3x + 2y + 3z ≤ 200
Bottles
6x + 12y + 18z ≥ 480
Simplified
x + 2y + 3z ≥ 80
So z = y
As z = y, then put the z
and y values together
as y’s
2x + 3y + 3z ≤ 200 → 2x + 6y ≤ 200 → x + 3y ≤ 100
3x + 2y + 3z ≤ 200 → 3x + 5y ≤ 200
x + 2y + 3z ≥ 80 →
x + 5y ≤ 80
Write each inequality as an equation
Also
x + 3y ≤ 100 becomes x + 3y = 100
remember
that x, y and z
3x + 5y ≤ 200 becomes 3x + 5y = 200
are also ≥ 0
x + 5y = 80
x + 5y ≤ 80 becomes
Now plot the graph See next slide
ii)
iii) Maximum is when x = 25 and y = 25
3x + 5y =
200
x + 3y = 100
x + 5y = 80
Remember
x + 2y as
there are 3
variables,
x, y and z
and z = y
So
x + 2y =
25 + 50 = 75
Feasible
Region
iv)
25 basic
25 standard
25 luxury
x≤0
y≤0