Questions D1 - A-Level Maths

Name	Activities
Fatima	Windsurfing, Sailing
Gavin	Climbing, Orienteering
Hassan	Windsurfing, Climbing
Iain	Sailing, Diving
Jane	Diving, Sailing, Orienteering

Draw a bipartite graph to model this situation. Initially the manager allocates Fatima, Gavin, Iain and Jane to supervise the first sport listed against their names in the table.
Starting from this matching, use the maximum matching algorithm to find a complete matching. Indicate clearly how you have applied the algorithm.
(6 marks)

Edexcel D1 Q5

5. This question should be answered on the sheet provided. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-05_834_1436_306_280} \captionsetup{labelformat=empty} \caption{Fig. 3}

\end{figure} Figure 3 shows a weighted network. The number on each arc indicates the weight of that arc.

Use Dijkstra's algorithm to find a path of least weight from $A$ to $J$ and state the weight of the path. Your solution must show clearly how you have applied the algorithm including:
1. the order in which the vertices were labelled,
2. how you determined the path of least weight.
Find if there are any other paths of least weight and explain your answer.
Describe a practical problem that could be modelled by the above network.

Edexcel D1 Q6

6. This question should be answered on the sheet provided. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-06_723_1292_276_349} \captionsetup{labelformat=empty} \caption{Fig. 4}

\end{figure} Figure 4 above shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.

Calculate the values of cut $C _ { 1 }$ and $C _ { 2 }$.
Find the minimum cut and state its value.
(2 marks) \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-06_647_1303_1430_347} \captionsetup{labelformat=empty} \caption{Fig. 5}
\end{figure} Figure 5 shows a feasible flow through the same network.
State the values of $x , y$ and $z$.
Using this as your initial flow pattern, use the labelling procedure to find a maximal flow. You should list each flow-augmenting route you use together with its flow. State how you know that you have found a maximal flow.
(8 marks)

Edexcel D1 Q7

7. A leisure company owns boats of each of the following types: 2-person boats which are 4 metres long and weigh 50 kg .
4-person boats which are 3 metres long and weigh 20 kg .
8-person boats which are 14 metres long and weigh 100 kg .
The leisure company is willing to donate boats to a local sports club to accommodate up to 40 people at any one time. However, storage facilities mean that a maximum combined length of the boats must not be more than 75 metres. Also, it must be possible to transport all the boats on a single trailer which has a maximum load capacity of 600 kg . The club intends to hire the boats out to help with the cost of maintaining them. It plans to charge $\pounds 10 , \pounds 12$ and $\pounds 8$ per day, for the 2 -, 4 - and 8 -person boats respectively and wishes to maximise its daily revenue ( $\pounds R$ ). Let $x , y$ and $z$ represent the number of 2-, 4- and 8-person boats respectively given to the club.

Model this as a linear programming problem simplifying your expressions so that they have integer coefficients.
(4 marks)
Show that the initial tableau, when using the simplex algorithm, can be written as:
Basic Variable $x$ $y$ $z$ $s$ $t$ $u$ Value
$s$ 1 2 4 1 0 0 20
$t$ 4 3 14 0 1 0 75
$u$ 5 2 10 0 0 1 60
$R$ ${ } ^ { - } 10$ ${ } ^ { - } 12$ ${ } ^ { - } 8$ 0 0 0 0
Explain the purpose of the variables $s$, $t$ and $u$.
By increasing the value of $y$ first, work out the next two complete tableaus.
Explain how you know that your final tableau gives an optimal solution and state this solution in practical terms. Sheet for answering question 3
NAME \section*{Please hand this sheet in for marking}
\includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-08_2017_1051_462_244}
\section*{Please hand this sheet in for marking}
$F \quad \bullet$
- $W$
  $G \quad \bullet$
- $S$
H •
- $C$
I •
- $O$
J •
- $D$
- Initial matching:
  $\begin{array} { l l l l } F & \bullet & \bullet & W
  G & \bullet & \bullet & S
  H & \bullet & \bullet & C
  I & \bullet & \bullet & O
  J & \bullet & \bullet & D \end{array}$ $\_\_\_\_$
Complete matching:
F •
- $W$
  $G \quad \bullet$
- $S$
  H •
- $C$
  I •
- $O$
  J •
- $D$
\section*{Sheet for answering question 5} NAME \section*{Please hand this sheet in for marking}
\includegraphics[max width=\textwidth, alt={}]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-10_2398_643_248_1224}
Sheet for answering question 6
NAME \section*{Please hand this sheet in for marking}
$\_\_\_\_$
$\_\_\_\_$
$\_\_\_\_$
\includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-11_592_1292_1078_312}
Sheet for answering question 6 (cont.)
\includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-12_595_1299_351_312}
\includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-12_597_1298_1409_308}

Edexcel D1 Q1

This question should be answered on the sheet provided.

A College wants to connect the computerised registration equipment at its six sites, $A$ to $F$. The table below shows the cost, in pounds, of connecting any two of the sites.

	A	B	C	D	$E$	$F$
A	-	130	190	155	140	125
B	130	-	215	200	190	170
C	190	215	-	110	180	100
D	155	200	110	-	70	45
E	140	190	180	70	-	75
F	125	170	100	45	75	-

Starting at $D$, use Prim's algorithm to find a minimum connector and draw the minimum spanning tree. Hence, state the lowest cost of connecting all the sites.
(5 marks)

Edexcel D1 Q2

2. This question should be answered on the sheet provided. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{acc09687-11a3-4392-af17-3d4d331d5ab4-03_1239_1442_306_283} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure} The data $$x _ { 1 } = 8 , \quad x _ { 2 } = 2 , \quad x _ { 3 } = 4 , \quad x _ { 4 } = 3 , \quad x _ { 5 } = 5 , \quad x _ { 6 } = 1 , \quad x _ { 7 } = 7 ,$$ is to be used in the algorithm given in Figure 1.

Complete the table on the answer sheet recording the results of each instruction as the algorithm is applied and state the final output using the given data.
Explain what the algorithm achieves for any set of data $x _ { 1 }$ to $x _ { n }$.

Edexcel D1 Q3

3. This question should be answered on the sheet provided. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{acc09687-11a3-4392-af17-3d4d331d5ab4-04_883_1317_317_315} \captionsetup{labelformat=empty} \caption{Fig. 2}

\end{figure} Figure 2 shows a capacitated, directed network.
The numbers in bold denote the capacities of each arc.
The numbers in circles show a feasible flow of 48 through the network.

Find the values of $x$ and $y$.
1. Use the labelling procedure to find the maximum flow through this network, listing each flow-augmenting route you use together with its flow.
2. Show your maximum flow pattern and state its value.
1. Find a minimum cut, listing the arcs through which it passes.
2. Explain why this proves that the flow found in part (b) is a maximum.
  (2 marks)

Edexcel D1 Q4

4. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{acc09687-11a3-4392-af17-3d4d331d5ab4-05_501_493_196_529} \captionsetup{labelformat=empty} \caption{Fig. 3}

\end{figure} Figure 3 shows the graph $K _ { 4 }$.

State the features of the graph that identify it as $K _ { 4 }$.
In $K _ { 4 }$, the Hamiltonian cycles $A B C D A , B C D A B , C D A B C$ and $D A B C D$ are usually regarded as being the same cycle. Find the number of distinct Hamiltonian cycles in
1. $\quad K _ { 4 }$,
2. $K _ { 5 }$,
3. $K _ { 10 }$.
In a weighted network, 8 possible routes must be placed in ascending order according to their lengths. The routes have the following lengths in kilometres: $$\begin{array} { l l l l l l l l } 27 & 25 & 29 & 32 & 19 & 24 & 17 & 26 \end{array}$$ Use a quick sort to obtain the sorted list, giving the state of the list after each comparison and indicating the pivot elements used.

Edexcel D1 Q5

5. A clothes manufacturer has a trademark "VE" which it wants to embroider on all its garments. The stitching must be done continuously but stitching along the same line twice is allowed. Logo 1:
\includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-06_524_1338_495_296} Logo 2: \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{acc09687-11a3-4392-af17-3d4d331d5ab4-06_531_1342_1155_299} \captionsetup{labelformat=empty} \caption{Fig. 4}

\end{figure} The weighted networks in Figure 4 represent two possible Logos.
The weights denote lengths in millimetres.

Calculate the shortest length of stitch required to embroider Logo 1 .
Calculate the shortest length of stitch required to embroider Logo 2.
Hence, determine the difference in the length of stitching required for the two Logos.

Edexcel D1 Q6

6. A company makes lighting sets to be sold to stores for use during the Christmas period. As the product is only required at this time of year, all manufacturing takes place during September, October and November. The sets are delivered to stores at the end of each of these months. Any sets that have been made but do not need to be delivered at the end of each of September and October are put into storage which the company must pay for. Let $x , y$ and $z$ be the number of sets manufactured in September, October and November respectively. The demand for lighting sets and the relevant costs are shown in the table below.

Month	September	October	November
Manufacturing costs per set during each month (£)	500	800	600
Demand for sets at the end of each month	800	1000	700
Cost of storing sets during each month ( £ )	-	100	150

The company must be able to meet the demand at the end of each month and there must be no unsold articles at the end of November.

1. Express $z$ in terms of $x$ and $y$.
2. Hence, find an expression for the total costs incurred in terms of $x$ and $y$. The company wishes to minimise its total costs by modelling this situation as a linear programming problem.
Find as inequalities the constraints that apply in addition to $x \geq 800$ and $y \geq 0$.
(2 marks)
On graph paper, illustrate these inequalities and label clearly the feasible region.
(4 marks)
Use your graph to solve the problem. You must state how many sets should be produced in each month and the total costs incurred by the company.
(3 marks)

Edexcel D1 Q7

7. This question should be answered on the sheet provided. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{acc09687-11a3-4392-af17-3d4d331d5ab4-08_586_1372_333_303} \captionsetup{labelformat=empty} \caption{Fig. 5}

\end{figure} The activity network in Figure 5 models the work involved in laying the foundations and putting in services for an industrial complex. The activities are represented by the arcs and the numbers in brackets give the time, in days, to complete each activity. Activity $C$ is a dummy.

Execute a forward scan to calculate the early times and a backward scan to calculate the late times, for each event.
Determine which activities lie on the critical path and list them in order.
State the minimum length of time needed to complete the project. The contractor is committed to completing the project in this minimum time and faces a penalty of $\pounds 50000$ for each day that the project is late. Unfortunately, before any work has begun, flooding means that activity $F$ will take 3 days longer than the 7 days allocated.
Activity $N$ could be completed in 1 day at an extra cost of $\pounds 90000$. Explain why doing this is not economical.
(3 marks)
If the time taken to complete any one activity, other than $F$, could be reduced by 2 days at an extra cost of $\pounds 80000$, for which activities on their own would this be profitable. Explain your reasoning.
(3 marks) END \section*{Please hand this sheet in for marking}
A B C D E $F$
A - 130 190 155 140 125
B 130 - 215 200 190 170
C 190 215 - 110 180 100
D 155 200 110 - 70 45
E 140 190 180 70 - 75
$F$ 125 170 100 45 75 -
\section*{Please hand this sheet in for marking}
$n$ $x _ { n }$ $а$ Any more data? $x _ { n + 1 }$ $b$ $( b - a ) > 0$ ? $a$
1 8 8 Yes 2 2 No 2
2 - -
Final output
$\_\_\_\_$
Sheet for answering question 3
NAME \section*{Please hand this sheet in for marking}
1. \includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-11_716_1218_502_331}
2. \includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-11_709_1214_1498_333} Maximum flow =
1. $\_\_\_\_$
2. $\_\_\_\_$
  \section*{Please hand this sheet in for marking}
\includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-12_764_1612_402_255}
$\_\_\_\_$
$\_\_\_\_$
$\_\_\_\_$
$\_\_\_\_$

Edexcel D1 Q1

(a) Draw the complete graph $K _ { 5 }$.
(b) Demonstrate that no planar drawing is possible for $K _ { 5 }$.
(c) Draw the complete graph $K _ { 3,3 }$.
(d) Demonstrate that no planar drawing is possible for $K _ { 3,3 }$.
A project consists of 11 activities, some of which are dependent on others having been completed. The following precedence table summarises the relevant information.

Activity	Depends on	Duration (hours)
A	-	5
B	A	4
C	A	2
D	B, C	11
E	C	4
$F$	D	3
$G$	D	8
$H$	D, E	2
I	$F$	1
J	$F , G , H$	7
$K$	$I , J$	2

Draw an activity network for the project. You should number the nodes and use as few dummies as possible.
(7 marks)

Edexcel D1 Q3

3. A machinist has to cut the following seven lengths (in centimetres) of steel tubing. $$\begin{array} { l l l l l l l } 150 & 104 & 200 & 60 & 184 & 84 & 120 \end{array}$$

Perform a quick sort to put the seven lengths in descending order. The machinist is to cut the lengths from rods that are each 240 cm long. You may assume that no waste is incurred during the cutting process.
Explain how to use the first-fit decreasing bin-packing algorithm to find the minimum number of rods required. Show that, using this algorithm, five rods are needed.
(4 marks)
Find if it is possible to cut additional pieces with a total length of 300 cm from the five rods.
(1 mark)

Edexcel D1 Q4

4. This question should be answered on the sheet provided. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{64203218-06e8-46f8-8aa9-7841ee2096c8-03_807_1402_1201_278} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure} Figure 1 above shows distances in miles between 10 cities.
Use Dijkstra's algorithm to determine the shortest route, and its length, between Liverpool and Hull. You must indicate clearly:

the order in which you labelled the vertices,
how you used your labelled diagram to find the shortest route.

Edexcel D1 Q5

5. This question should be answered on the sheet provided. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{64203218-06e8-46f8-8aa9-7841ee2096c8-04_794_1315_280_296} \captionsetup{labelformat=empty} \caption{Fig. 2}

\end{figure} In Figure 2 the weight on each arc represents the cost in pounds of translating a certain document between the two languages at the nodes that it joins. You may assume that the cost is the same for translating in either direction.

Use Kruskal's algorithm to find the minimum cost of obtaining a translation of the document from English into each of the other languages on the network. You must show the order in which the arcs were selected.
(4 marks)
It is decided that a Greek translation is not needed. Find the minimum cost if:
1. translations to and from Greek are not available,
2. translations to and from Greek are still available.
Comment on your findings. Another document is to be translated into 60 languages. It is now also necessary to take into account the fact that the cost of a translation between two languages depends on which language you start from.
How would you overcome the problem of having different costs for reverse translations?
What algorithm would be suitable to find a computerised solution.
State another assumption you have made in answering this question and comment on its validity.
(2 marks) \section*{6. This question should be answered on the sheet provided.} There are 5 computers in an office, each of which must be dedicated to a single application. The computers have different specifications and the following table shows which applications each computer is capable of running.
Computer Applications
E Animation
F Office, Data
G Simulation
H Animation, Office
I Data, CAD, Simulation

Edexcel D1 Q7

7. An engineer makes three components $X , Y$ and $Z$. Relevant details are as follows: Component $X$ requires 6 minutes turning, 3 minutes machining and 1 minute finishing. Component $Y$ requires 15 minutes turning, 3 minutes machining and 4 minutes finishing. Component $Z$ requires 12 minutes turning, 1 minute machining and 4 minutes finishing. The engineer gets access to 185 minutes turning, 30 minutes machining and 60 minutes finishing each day. The profits from selling components $X , Y$ and $Z$ are $\pounds 40 , \pounds 90$ and $\pounds 60$ respectively and the engineer wishes to maximise the profit from her work each day. Let the number of components $X , Y$ and $Z$ the engineer makes each day be $x , y$ and $z$ respectively.

Write down the 3 inequalities that apply in addition to $x \geq 0 , y \geq 0$ and $z \geq 0$.
Explain why it is not appropriate to use a graphical method to solve the problem. It is decided to use the simplex algorithm to solve the problem.
Show that a possible initial tableau is: Workings:
Workings:
$E$ $\bullet$ $\bullet$ $O$
$F$ $\bullet$ $\bullet$ $D$
$G$ $\bullet$ $\bullet$ $C$
$H$ $\bullet$ $\bullet$ $A$
$I$ $\bullet$ $\bullet$ $S$
Alternative matching:
$E$ $\bullet$ $\bullet$ $O$
$F$ $\bullet$ $\bullet$ $D$
$G$ $\bullet$ $\bullet$ $C$
$H$ $\bullet$ $\bullet$ $A$
$I$ $\bullet$ $\bullet$ $S$

Edexcel D1 Q1

This question should be answered on the sheet provided.

A cable TV company wishes to link 5 villages in the Scottish Highlands. The table below shows the shortest distances, in kilometres, between these 5 villages.

	Durness	Helmsdale	Inverness	Thurso	Wick
Durness	-	68	123	81	92
Helmsdale	68	-	102	72	64
Inverness	123	102	-	148	127
Thurso	81	72	148	-	48
Wick	92	64	127	48	-

Starting at Thurso, use Prim's algorithm to find a minimum spanning tree. You should make your method clear, indicating the order in which you selected the arcs in your final tree.
Calculate the minimum total length of cable required.

Edexcel D1 Q2

2. In a television gameshow the names of 100 celebrities are listed in alphabetical order. A name is chosen at random from the list and a contestant has to guess which celebrity has been chosen. If the contestant is not correct, the host indicates whether the chosen name comes before or after the contestant's answer in the list and the contestant makes another guess. Each contestant knows all the names on the list and has to find the chosen name in as few guesses as possible.

Describe a strategy which would enable the contestant to find the chosen name in as few guesses as possible.
A large database with up to one million ordered entries is to be interrogated in the same way using appropriate software. Find the maximum number of interrogations that would be required for the software to find a particular entry and explain your answer.

Edexcel D1 Q3

3. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{63f3ba38-8bca-4684-957f-aca7104f2f3e-03_734_1353_196_317} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure} Figure 1 shows a graph in which $y \geq 0$.
Given that the graph is a weighted network,

find the range of values for the path of lowest weight from $S$ to $T$. Given instead, that the graph is a capacitated network with the numbers representing the capacity along each arc,
find the range of values for the maximum flow from $S$ to $T$.
Give an example of a practical problem which could be solved by using:
1. the weighted network in part (a),
2. the capacitated network in part (b).

Edexcel D1 Q4

4. This question should be answered on the sheet provided. The Prime Minister is planning a reshuffle and the table indicates which posts each of the six ministers involved would be willing to accept.

Minister	Government Position
$P$	Chancellor ( $C$ )
$Q$	Foreign Secretary ( $F$ ), Minister for Education ( $E$ )
$R$	Minister for Defence ( $D$ ), Minister for Industry ( $I$ )
S	Minister for Defence ( $D$ ), Home Secretary ( $H$ )
$T$	Home Secretary (H)
$U$	Chancellor ( $C$ ), Foreign Secretary ( $F$ )

Draw a bipartite graph to model this situation. Initially the Prime Minister matches Minister $P$ to the post of Chancellor, $Q$ to Foreign Secretary, $R$ to Defence and $T$ to Home Secretary.
Draw this initial matching.
Starting from this initial matching use the maximum matching algorithm to find a complete matching. Indicate clearly how the algorithm has been applied, listing any alternating paths used. Minister $U$, on reflection, now expresses no interest in becoming Foreign Secretary.
Explain why no complete matching is now possible.
(2 marks)

Edexcel D1 Q5

5. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{63f3ba38-8bca-4684-957f-aca7104f2f3e-05_863_1061_223_360} \captionsetup{labelformat=empty} \caption{Fig. 2}

\end{figure} The network in Figure 2 represents the streets near Randolph Square in Newtown, Edinburgh. The weightings represent the average time, in seconds, taken to travel along each road in either direction. The large values for the roads $C D$ and $J L$ are due to traffic lights. In the course of his work, a van driver must travel along each road at least once each day. He starts and finishes at his depot, $F$, and wishes to minimise the total time that this takes.

Describe an appropriate algorithm that can be used to find this minimum time.
(3 marks)
Apply this algorithm to find a route that the driver can take and state the total time he can expect to spend on this journey each day.
(5 marks)
The section of road $A B$ is to be turned into a pedestrian precinct.
Assuming that the driver must still travel along all the other roads at least once each day, find the modified time he can expect to spend on his daily journey Comment on your answer.
(3 marks) Turn over

Edexcel D1 Q6

6. The table below shows the maximum flows possible within a system.

To From	$S$	$A$	$B$	$C$	D	$T$
S	-	35	30	55	-	-
A	-	-	-	-	-	50
B	-	12	-	8	-	20
C	-	-	-	-	15	30
D	-	-	-	-	-	14
T	-	-	-	-	-	-

For example, the maximum flow from $B$ to $A$ is 12 units.

Draw a digraph to represent this information.
Give the capacity of the cut $\{ S , A , B , C \} \mid \{ D , T \}$.
Find the minimum cut, stating its capacity, and expressing it in the form $\{ \quad \} \mid \{ \quad \}$.
Use the labelling procedure to find the maximum flow from $S$ to $T$. You should list each flow-augmenting route you find together with its flow.
Explain how you know that you have found the maximum possible flow.
Give an example of a practical situation that could be modelled by the original table.

Edexcel D1 Q7

7. A fitness centre runs introductory courses aimed at the following groups of customers: Pensioners, who will be charged $\pounds 4$ for a 2 -hour session.
Other adults, who will be charged $\pounds 10$ for a 4 -hour session.
Children, who will be charged $\pounds 2$ for a 1 -hour session.
Let the number of pensioners, other adults, and children be $x , y$ and $z$ respectively.
Regulations state that the number of pensioners, $x$, must be at most 5 more than the number of adults, $y$. There must also be at least twice as many adults, $y$, as there are children, $z$. The centre is able to supervise up to 40 person-hours each day at the centre and wishes to maximise the revenue $( \pounds R )$ that can be earned each day from these sessions. You may assume that the places on any courses that the centre runs will be filled.

Modelling this situation as a linear programming problem, write down the constraints and objective function in terms of $x , y$ and $z$. Using the Simplex algorithm, the following initial tableau is obtained.
$\_\_\_\_$

Edexcel D1 Q1

(a) Make plane drawings of each of the graphs shown in Figure 1.

Graph 1 \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-02_1155_664_278_529} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure} (b) State the name given to Graph 1 and write down the features that identify it.
(c) State, with a reason, whether it is possible to add further arcs to Graph 2 such that it remains a simple connected graph. No further vertices may be added.
(1 mark)

Edexcel D1 Q2

2. This question should be answered on the sheet provided. A builder is going to put up houses on a plot of land of area $12000 \mathrm {~m} ^ { 2 }$.
There are 5 designs to choose from and no more than one of each design can be built.

Design	Kendal	Milverton	Arlington	Elford	Grosvenor
Plot area ('000 $\mathrm { m } ^ { 2 }$ )	3	11	3	5	10
Value ( $\pounds ^ { \prime } 000 \mathrm {~s}$ )	100	190	40	80	120

The builder needs to work out which houses he should build in order to maximise the total value of the site. He does this using a tree diagram and each "branch" on the tree is terminated when the total area of land on that branch exceeds $12000 \mathrm {~m} ^ { 2 }$.

1. Complete the tree diagram so that each branch is terminated or all choices have been considered.
2. Hence, determine which designs the builder should use and the total value that the site will have when completed.
Explain how this method could be altered if more than one of each design is allowed.

Basic Variable	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	Value
\(s\)	1	2	4	1	0	0	20
\(t\)	4	3	14	0	1	0	75
\(u\)	5	2	10	0	0	1	60
\(R\)	\({ } ^ { - } 10\)	\({ } ^ { - } 12\)	\({ } ^ { - } 8\)	0	0	0	0

\(n\)	\(x _ { n }\)	\(а\)	Any more data?	\(x _ { n + 1 }\)	\(b\)	\(( b - a ) > 0\) ?	\(a\)
1	8	8	Yes	2	2	No	2
2	-	-

Activity	Depends on	Duration (hours)
A	-	5
B	A	4
C	A	2
D	B, C	11
E	C	4
\(F\)	D	3
\(G\)	D	8
\(H\)	D, E	2
I	\(F\)	1
J	\(F , G , H\)	7
\(K\)	\(I , J\)	2

\(E\)	\(\bullet\)	\(\bullet\)	\(O\)
\(F\)	\(\bullet\)	\(\bullet\)	\(D\)
\(G\)	\(\bullet\)	\(\bullet\)	\(C\)
\(H\)	\(\bullet\)	\(\bullet\)	\(A\)
\(I\)	\(\bullet\)	\(\bullet\)	\(S\)

\(E\)	\(\bullet\)	\(\bullet\)	\(O\)
\(F\)	\(\bullet\)	\(\bullet\)	\(D\)
\(G\)	\(\bullet\)	\(\bullet\)	\(C\)
\(H\)	\(\bullet\)	\(\bullet\)	\(A\)
\(I\)	\(\bullet\)	\(\bullet\)	\(S\)

Computer	Applications
E	Animation
F	Office, Data
G	Simulation
H	Animation, Office
I	Data, CAD, Simulation

Minister	Government Position
\(P\)	Chancellor ( \(C\) )
\(Q\)	Foreign Secretary ( \(F\) ), Minister for Education ( \(E\) )
\(R\)	Minister for Defence ( \(D\) ), Minister for Industry ( \(I\) )
S	Minister for Defence ( \(D\) ), Home Secretary ( \(H\) )
\(T\)	Home Secretary (H)
\(U\)	Chancellor ( \(C\) ), Foreign Secretary ( \(F\) )

Questions D1 (899 questions)

Browse by module

Browse by board

Edexcel D1 Q4

Edexcel D1 Q5

Edexcel D1 Q6

Edexcel D1 Q7

Edexcel D1 Q1

Edexcel D1 Q2

Edexcel D1 Q3

Edexcel D1 Q4

Edexcel D1 Q5

Edexcel D1 Q6

Edexcel D1 Q7

Edexcel D1 Q1

Edexcel D1 Q3

Edexcel D1 Q4

Edexcel D1 Q5

Edexcel D1 Q7

Edexcel D1 Q1

Edexcel D1 Q2

Edexcel D1 Q3

Edexcel D1 Q4

Edexcel D1 Q5

Edexcel D1 Q6

Edexcel D1 Q7

Edexcel D1 Q1

Edexcel D1 Q2