Question 9 - A-Level Maths

AQA D1 2011 January — Question 9 13 marks

Exam Board	AQA
Module	D1 (Decision Mathematics 1)
Year	2011
Session	January
Marks	13
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Linear Programming
Type	Three-variable constraint reduction
Difficulty	Moderate -0.3 This is a standard linear programming question requiring formulation of constraints from a word problem, substitution to reduce variables, graphical representation, and optimization. While it involves multiple steps (13 marks total), each step follows routine D1 procedures with no novel insights required. The arithmetic is straightforward and the graphical method is a core textbook technique, making it slightly easier than average A-level difficulty overall.
Spec	7.06a LP formulation: variables, constraints, objective function 7.06d Graphical solution: feasible region, two variables

Herman is packing some hampers. Each day, he packs three types of hamper: basic, standard and luxury. Each basic hamper has 6 tins, 9 packets and 6 bottles. Each standard hamper has 9 tins, 6 packets and 12 bottles. Each luxury hamper has 9 tins, 9 packets and 18 bottles. Each day, Herman has 600 tins and 600 packets available, and he must use at least 480 bottles. Each day, Herman packs \(x\) basic hampers, \(y\) standard hampers and \(z\) luxury hampers.

In addition to \(x \geqslant 0\), \(y \geqslant 0\) and \(z \geqslant 0\), find three inequalities in \(x\), \(y\) and \(z\) that model the above constraints, simplifying each inequality. [4]
On a particular day, Herman packs the same number of standard hampers as luxury hampers.
1. Show that your answers in part (a) become \(x + 3y \leqslant 100\) \(3x + 5y \leqslant 200\) \(x + 5y \geqslant 80\) [2]
2. On the grid opposite, draw a suitable diagram to represent Herman's situation, indicating the feasible region. [4]
3. Use your diagram to find the maximum total number of hampers that Herman can pack on that day. [2]
4. Find the number of each type of hamper that Herman packs that corresponds to your answer to part (b)(iii). [1]

Show mark scheme Show mark scheme source

Question 9:

9

TOTAL

Answer all questions in the spaces provided.

1 Six people, A, B, C, D, E and F, are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6.

The following bipartite graph shows the tasks that each of the people is able to

undertake.

A 1

B 2

C 3

D 4

E 5

F 6

(a) Represent this information in an adjacency matrix. (2 marks)

(b) Initially, B is assigned to task 5, D to task 2, E to task 4 and F to task 3.

Demonstrate, by using an algorithm from this initial matching, how each person can

be allocated to a task. (5 marks)

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

2 A student is using a quicksort algorithm to rearrange a set of numbers into ascending

order. She uses the first number in each list (or sublist) as the pivot.

Her correct solution for the first three passes is as follows.

Initial list 10 7 4 22 13 16 19 5

After 1st pass 7 4 5 10 22 13 16 19

After 2nd pass 4 5 7 10 13 16 19 22

After 3rd pass 4 5 7 10 13 16 19 22

(a) State the pivots used for the 2nd pass. (2 marks)

(b) Write down the number of comparisons on each of the three passes. (3 marks)

(c) Explain whether the student has completed the algorithm. (1 mark)

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

3 The following network shows the lengths, in miles, of roads connecting nine villages,

A, B, …,I .

A 8 B 15 C

10 14 5 13 6

17 12

D F

E

11 16

4 7 14

G 11 H 9 I

(a) (i) Use Prim’s algorithm starting from E, showing the order in which you select the

edges, to find a minimum spanning tree for the network. (4 marks)

(ii) State the length of your minimum spanning tree. (1 mark)

(iii) Draw your minimum spanning tree. (2 marks)

(b) On a particular day, village B is cut off, so its connecting roads cannot be used.

Find the length of a minimum spanning tree for the remaining eight villages.

(2 marks)

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

14

Answer	Marks
17	5 13

12 E

Answer	Marks
11	16

7 QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

4 The network below shows some paths on an estate. The number on each edge

represents the time taken, in minutes, to walk along a path.

(a) (i) Use Dijkstra’s algorithm on the network to find the minimum walking time from

A to J. (6 marks)

(ii) Write down the corresponding route. (1 mark)

(b) A new subway is constructed connecting C to G directly. The time taken to walk

along this subway is x minutes. The minimum time taken to walk from A to G is

now reduced, but the minimum time taken to walk from A to J is not reduced.

Find the range of possible values for x. (3 marks)

QUESTION

PART

REFERENCE

Answer	Marks
(a)(i)	B 3 G

2.5 10.5

E

9 9

3

4.5 7.5 C 6 H 6

A J

6 4.5

10.5 3

F

1.5 3

D 7.5 I

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

PMT

Donotwrite

10 outsidethe

box

5 Norris delivers newspapers to houses on an estate. The network shows the streets on

the estate. The number on each edge shows the length of the street, in metres.

Norris starts from the newsagents located at vertex A, and he must walk along all the

streets at least once before returning to the newsagents.

A 30 D 60 G

105 90 30 90

195 C F 165

75 30 15 90

B 120 E 120 H

The total length of the streets is 1215 metres.

(a) Give a reason why it is not possible to start at A, walk along each street once only,

and return to A. (1 mark)

(b) Find the length of an optimal Chinese postman route around the estate, starting and

finishing at A. (5 marks)

(c) For an optimal Chinese postman route, state:

(i) the number of times that the vertex F would occur; (1 mark)

(ii) the number of times that the vertex H would occur. (1 mark)

(10)

P38264/Jan11/MD01

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

6 (a) The complete graph K has every one of its n vertices connected to each of the other

n

vertices by a single edge.

(i) Find the total number of edges in the graph K . (1 mark)

5 (ii) State the number of edges in a minimum spanning tree for the graph K . (1 mark)

5 (iii) State the number of edges in a Hamiltonian cycle for the graph K . (1 mark)

5 (b) A simple graph G has six vertices and nine edges, and G is Eulerian. Draw a sketch

to show a possible graph G. (2 marks)

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

7 Fred delivers bread to five shops, A, B, C, D and E. Fred starts his deliveries at

shop B, and travels to each of the other shops once before returning to shop B. Fred

wishes to keep his travelling time to a minimum.

The table shows the travelling times, in minutes, between the shops.

A B C D E

A – 3 11 15 5

B 3 – 18 12 4

C 11 18 – 5 16

D 15 12 5 – 10

E 5 4 16 10 –

(a) Find the travelling time for the tour BACDEB. (1 mark)

(b) Use the nearest neighbour algorithm, starting at B, to find another upper bound for

the travelling time for Fred’s tour. (3 marks)

(c) By deleting C, find a lower bound for the travelling time for Fred’s tour. (4 marks)

(d) Sketch a network showing the edges that give you the lower bound in part (c) and

comment on its significance. (2 marks)

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

Answer	Marks	Guidance
A	B	C
A	–	3
B	3	–
C	11	18
D	15	12
E	5	4

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

8 A student is tracing the following algorithm with positive integer values of A and B.

The function INT gives the integer part of a number, eg INT(2.3) ¼ 2 and

INT(3.8) ¼ 3.

Line 10 Let X ¼ 0

Line 20 Input A, B

Line 30 If INT(A/2) ¼ A/2 then go to Line 50

Line 40 Let X ¼ X þB

Line 50 If A ¼ 1 then go to Line 90

Line 60 Let A ¼ INT(A/2)

Line 70 Let B ¼ 2(cid:2)B

Line 80 Go to Line 30

Line 90 Print X

Line 100 End

(a) Trace the algorithm in the case where the input values are A ¼ 20 and B ¼ 8.

(4 marks)

(b) State the purpose of the algorithm. (1 mark)

(c) Another student changed Line 50 to

Line 50 If A ¼ 1 then go to Line 80

Explain what would happen if this algorithm were traced. (2 marks)

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

9 Herman is packing some hampers. Each day, he packs three types of hamper: basic,

standard and luxury.

Each basic hamper has 6 tins, 9 packets and 6 bottles.

Each standard hamper has 9 tins, 6 packets and 12 bottles.

Each luxury hamper has 9 tins, 9 packets and 18 bottles.

Each day, Herman has 600 tins and 600 packets available, and he must use at least

480 bottles.

Each day, Herman packs x basic hampers, y standard hampers and z luxury

hampers.

(a) In addition to x50, y50 and z50, find three inequalities in x, y and z that

model the above constraints, simplifying each inequality. (4 marks)

(b) On a particular day, Herman packs the same number of standard hampers as luxury

hampers.

(i) Show that your answers in part (a) become

xþ3y4100

3xþ5y4200

xþ5y580 (2 marks)

(ii) On the grid opposite, draw a suitable diagram to represent Herman’s situation,

indicating the feasible region. (4 marks)

(iii) Use your diagram to find the maximum total number of hampers that Herman can

pack on that day. (2 marks)

(iv) Find the number of each type of hamper that Herman packs that corresponds to your

answer to part (b)(iii). (1 mark)

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

QUESTION

PART

REFERENCE

(b)(ii)

..........

Answer	Marks
..........	~ y

50–

40–

30–

20–

10–

0– ~

– – – – – – – x

0 20 40 60 80 100 120

.......................................................................................................................................................

PMT

Donotwrite

20 outsidethe

box

QUESTION

PART

REFERENCE

.................................................................................................................................................................

END OF QUESTIONS

Copyright(cid:2)2011AQAanditslicensors. Allrightsreserved.

(20)

P38264/Jan11/MD01

Question 9:
9
TOTAL
Answer all questions in the spaces provided.
1 Six people, A, B, C, D, E and F, are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6.
The following bipartite graph shows the tasks that each of the people is able to
undertake.
A 1
B 2
C 3
D 4
E 5
F 6
(a) Represent this information in an adjacency matrix. (2 marks)
(b) Initially, B is assigned to task 5, D to task 2, E to task 4 and F to task 3.
Demonstrate, by using an algorithm from this initial matching, how each person can
be allocated to a task. (5 marks)
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
2 A student is using a quicksort algorithm to rearrange a set of numbers into ascending
order. She uses the first number in each list (or sublist) as the pivot.
Her correct solution for the first three passes is as follows.
Initial list 10 7 4 22 13 16 19 5
After 1st pass 7 4 5 10 22 13 16 19
After 2nd pass 4 5 7 10 13 16 19 22
After 3rd pass 4 5 7 10 13 16 19 22
(a) State the pivots used for the 2nd pass. (2 marks)
(b) Write down the number of comparisons on each of the three passes. (3 marks)
(c) Explain whether the student has completed the algorithm. (1 mark)
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
3 The following network shows the lengths, in miles, of roads connecting nine villages,
A, B, …,I .
A 8 B 15 C
10 14 5 13 6
17 12
D F
E
11 16
4 7 14
G 11 H 9 I
(a) (i) Use Prim’s algorithm starting from E, showing the order in which you select the
edges, to find a minimum spanning tree for the network. (4 marks)
(ii) State the length of your minimum spanning tree. (1 mark)
(iii) Draw your minimum spanning tree. (2 marks)
(b) On a particular day, village B is cut off, so its connecting roads cannot be used.
Find the length of a minimum spanning tree for the remaining eight villages.
(2 marks)
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
14
17 | 5 13
12
E
11 | 16
7
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
4 The network below shows some paths on an estate. The number on each edge
represents the time taken, in minutes, to walk along a path.
(a) (i) Use Dijkstra’s algorithm on the network to find the minimum walking time from
A to J. (6 marks)
(ii) Write down the corresponding route. (1 mark)
(b) A new subway is constructed connecting C to G directly. The time taken to walk
along this subway is x minutes. The minimum time taken to walk from A to G is
now reduced, but the minimum time taken to walk from A to J is not reduced.
Find the range of possible values for x. (3 marks)
QUESTION
PART
REFERENCE
(a)(i) | B 3 G
2.5 10.5
E
9 9
3
4.5
7.5 C 6 H 6
A J
6 4.5
10.5 3
F
1.5 3
D 7.5 I
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
PMT
Donotwrite
10 outsidethe
box
5 Norris delivers newspapers to houses on an estate. The network shows the streets on
the estate. The number on each edge shows the length of the street, in metres.
Norris starts from the newsagents located at vertex A, and he must walk along all the
streets at least once before returning to the newsagents.
A 30 D 60 G
105 90 30 90
195 C F 165
75 30 15 90
B 120 E 120 H
The total length of the streets is 1215 metres.
(a) Give a reason why it is not possible to start at A, walk along each street once only,
and return to A. (1 mark)
(b) Find the length of an optimal Chinese postman route around the estate, starting and
finishing at A. (5 marks)
(c) For an optimal Chinese postman route, state:
(i) the number of times that the vertex F would occur; (1 mark)
(ii) the number of times that the vertex H would occur. (1 mark)
(10)
P38264/Jan11/MD01
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
6 (a) The complete graph K has every one of its n vertices connected to each of the other
n
vertices by a single edge.
(i) Find the total number of edges in the graph K . (1 mark)
5
(ii) State the number of edges in a minimum spanning tree for the graph K . (1 mark)
5
(iii) State the number of edges in a Hamiltonian cycle for the graph K . (1 mark)
5
(b) A simple graph G has six vertices and nine edges, and G is Eulerian. Draw a sketch
to show a possible graph G. (2 marks)
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
7 Fred delivers bread to five shops, A, B, C, D and E. Fred starts his deliveries at
shop B, and travels to each of the other shops once before returning to shop B. Fred
wishes to keep his travelling time to a minimum.
The table shows the travelling times, in minutes, between the shops.
A B C D E
A – 3 11 15 5
B 3 – 18 12 4
C 11 18 – 5 16
D 15 12 5 – 10
E 5 4 16 10 –
(a) Find the travelling time for the tour BACDEB. (1 mark)
(b) Use the nearest neighbour algorithm, starting at B, to find another upper bound for
the travelling time for Fred’s tour. (3 marks)
(c) By deleting C, find a lower bound for the travelling time for Fred’s tour. (4 marks)
(d) Sketch a network showing the edges that give you the lower bound in part (c) and
comment on its significance. (2 marks)
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
A | B | C | D | E
A | – | 3 | 11 | 15 | 5
B | 3 | – | 18 | 12 | 4
C | 11 | 18 | – | 5 | 16
D | 15 | 12 | 5 | – | 10
E | 5 | 4 | 16 | 10 | –
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
8 A student is tracing the following algorithm with positive integer values of A and B.
The function INT gives the integer part of a number, eg INT(2.3) ¼ 2 and
INT(3.8) ¼ 3.
Line 10 Let X ¼ 0
Line 20 Input A, B
Line 30 If INT(A/2) ¼ A/2 then go to Line 50
Line 40 Let X ¼ X þB
Line 50 If A ¼ 1 then go to Line 90
Line 60 Let A ¼ INT(A/2)
Line 70 Let B ¼ 2(cid:2)B
Line 80 Go to Line 30
Line 90 Print X
Line 100 End
(a) Trace the algorithm in the case where the input values are A ¼ 20 and B ¼ 8.
(4 marks)
(b) State the purpose of the algorithm. (1 mark)
(c) Another student changed Line 50 to
Line 50 If A ¼ 1 then go to Line 80
Explain what would happen if this algorithm were traced. (2 marks)
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
9 Herman is packing some hampers. Each day, he packs three types of hamper: basic,
standard and luxury.
Each basic hamper has 6 tins, 9 packets and 6 bottles.
Each standard hamper has 9 tins, 6 packets and 12 bottles.
Each luxury hamper has 9 tins, 9 packets and 18 bottles.
Each day, Herman has 600 tins and 600 packets available, and he must use at least
480 bottles.
Each day, Herman packs x basic hampers, y standard hampers and z luxury
hampers.
(a) In addition to x50, y50 and z50, find three inequalities in x, y and z that
model the above constraints, simplifying each inequality. (4 marks)
(b) On a particular day, Herman packs the same number of standard hampers as luxury
hampers.
(i) Show that your answers in part (a) become
xþ3y4100
3xþ5y4200
xþ5y580 (2 marks)
(ii) On the grid opposite, draw a suitable diagram to represent Herman’s situation,
indicating the feasible region. (4 marks)
(iii) Use your diagram to find the maximum total number of hampers that Herman can
pack on that day. (2 marks)
(iv) Find the number of each type of hamper that Herman packs that corresponds to your
answer to part (b)(iii). (1 mark)
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
QUESTION
PART
REFERENCE
(b)(ii)
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | ~ y
50–
40–
30–
20–
10–
0– ~
– – – – – – – x
0 20 40 60 80 100 120
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
PMT
Donotwrite
20 outsidethe
box
QUESTION
PART
REFERENCE
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
END OF QUESTIONS
Copyright(cid:2)2011AQAanditslicensors. Allrightsreserved.
(20)
P38264/Jan11/MD01

Show LaTeX source

Herman is packing some hampers. Each day, he packs three types of hamper: basic, standard and luxury.

Each basic hamper has 6 tins, 9 packets and 6 bottles.

Each standard hamper has 9 tins, 6 packets and 12 bottles.

Each luxury hamper has 9 tins, 9 packets and 18 bottles.

Each day, Herman has 600 tins and 600 packets available, and he must use at least 480 bottles.

Each day, Herman packs $x$ basic hampers, $y$ standard hampers and $z$ luxury hampers.

\begin{enumerate}[label=(\alph*)]
\item In addition to $x \geqslant 0$, $y \geqslant 0$ and $z \geqslant 0$, find three inequalities in $x$, $y$ and $z$ that model the above constraints, simplifying each inequality. [4]
\item On a particular day, Herman packs the same number of standard hampers as luxury hampers.
\begin{enumerate}[label=(\roman*)]
\item Show that your answers in part (a) become

$x + 3y \leqslant 100$

$3x + 5y \leqslant 200$

$x + 5y \geqslant 80$ [2]

\item On the grid opposite, draw a suitable diagram to represent Herman's situation, indicating the feasible region. [4]
\item Use your diagram to find the maximum total number of hampers that Herman can pack on that day. [2]
\item Find the number of each type of hamper that Herman packs that corresponds to your answer to part (b)(iii). [1]
\end{enumerate}
\end{enumerate}

\hfill \mbox{\textit{AQA D1 2011 Q9 [13]}}

This paper (9 questions)

View full paper

Q1 7 Q2 6 Q3 9 Q4 10 Q5 8 Q6 5 Q7 10 Q8 7 Q9 13