Questions — Edexcel D1 (505 questions)

Browse by module
All questions AEA AS Paper 1 AS Paper 2 AS Pure C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Extra Pure Further Mechanics Further Mechanics A AS Further Mechanics AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics Further Paper 4 Further Pure Core Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Pure with Technology Further Statistics Further Statistics A AS Further Statistics AS Further Statistics B AS Further Statistics Major Further Statistics Minor Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 H240/01 H240/02 H240/03 M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 S1 S2 S3 S4 Unit 1 Unit 2 Unit 3 Unit 4
Browse by board
AQA AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Paper 1 Further Paper 2 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics M1 M2 M3 Paper 1 Paper 2 Paper 3 S1 S2 S3 CAIE FP1 FP2 Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 4 M1 M2 P1 P2 P3 S1 S2 Edexcel AEA AS Paper 1 AS Paper 2 C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 OCR AS Pure C1 C2 C3 C4 D1 D2 FD1 AS FM1 AS FP1 FP1 AS FP2 FP3 FS1 AS Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Mechanics Further Mechanics AS Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Statistics Further Statistics AS H240/01 H240/02 H240/03 M1 M2 M3 M4 PURE S1 S2 S3 S4 OCR MEI AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further Extra Pure Further Mechanics A AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Pure Core Further Pure Core AS Further Pure with Technology Further Statistics A AS Further Statistics B AS Further Statistics Major Further Statistics Minor M1 M2 M3 M4 Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 Pre-U Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 WJEC Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 Unit 1 Unit 2 Unit 3 Unit 4
Sort by: Default | Easiest first | Hardest first
Edexcel D1 Q1
7 marks Standard +0.3
1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-02_629_700_196_443} \captionsetup{labelformat=empty} \caption{Fig 1}
\end{figure}
  1. Find a Hamiltonian cycle for the graph shown in Figure 1.
  2. Starting with your cycle, construct a plane drawing of the graph, showing your method clearly.
    (5 marks)
Edexcel D1 Q2
8 marks Easy -1.3
2. (a) The following list of numbers is to be sorted into descending order. $$\begin{array} { l l l l l l } 35 & 23 & 10 & 46 & 24 & 11 \end{array}$$ Use the Bubble sort algorithm to obtain a sorted list, giving the state of the list at each stage where two values could be interchanged.
(b) Find the maximum number of interchanges needed when 8 values are sorted into descending order using the Bubble sort algorithm.
(c) Use the first-fit decreasing algorithm to fit the data in part (a) into bins of size 50. Explain how you decided in which bin to place the number 11.
Edexcel D1 Q3
8 marks Moderate -0.8
3. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-03_744_1524_319_315} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure} Figure 2 shows an activity network. The nodes represent events and the arcs represent the activities. The number in each bracket gives the time, in days, needed to complete the activity.
  1. Calculate the early and late times for each event using appropriate forward and backward scanning.
    (5 marks)
  2. Hence, determine the activities which lie on the critical path.
  3. State the minimum number of days needed to complete the entire project.
Edexcel D1 Q4
8 marks Moderate -0.8
4. This question should be answered on the sheet provided. The manager of an outdoor centre must staff each activity offered by the centre with an appropriately qualified instructor. The table below shows the sports for which each member of staff is qualified to supervise.
NameActivities
FatimaWindsurfing, Sailing
GavinClimbing, Orienteering
HassanWindsurfing, Climbing
IainSailing, Diving
JaneDiving, Sailing, Orienteering
  1. 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.
  2. 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
12 marks Moderate -0.3
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.
  1. 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.
  2. Find if there are any other paths of least weight and explain your answer.
  3. Describe a practical problem that could be modelled by the above network.
Edexcel D1 Q6
15 marks Standard +0.3
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.
  1. Calculate the values of cut \(C _ { 1 }\) and \(C _ { 2 }\).
  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.
  3. State the values of \(x , y\) and \(z\).
  4. 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
17 marks Moderate -0.3
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.
  1. Model this as a linear programming problem simplifying your expressions so that they have integer coefficients.
    (4 marks)
  2. Show that the initial tableau, when using the simplex algorithm, can be written as:
    Basic Variable\(x\)\(y\)\(z\)\(s\)\(t\)\(u\)Value
    \(s\)12410020
    \(t\)431401075
    \(u\)521000160
    \(R\)\({ } ^ { - } 10\)\({ } ^ { - } 12\)\({ } ^ { - } 8\)0000
  3. Explain the purpose of the variables \(s\), \(t\) and \(u\).
  4. By increasing the value of \(y\) first, work out the next two complete tableaus.
  5. 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}
    3. \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-08_2017_1051_462_244}
      \section*{Please hand this sheet in for marking}
    4. \(F \quad \bullet\)
      H •
      I •
      J •
      Complete matching:
      F •
      \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}
    5. \(\_\_\_\_\)
    6. \(\_\_\_\_\)
    7. \(\_\_\_\_\)
    8. \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
5 marks Moderate -0.8
  1. 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.
ABCD\(E\)\(F\)
A-130190155140125
B130-215200190170
C190215-110180100
D155200110-7045
E14019018070-75
F1251701004575-
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
7 marks Moderate -0.8
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.
  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.
  2. Explain what the algorithm achieves for any set of data \(x _ { 1 }\) to \(x _ { n }\).
Edexcel D1 Q3
11 marks Standard +0.3
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.
  1. 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
11 marks Moderate -0.8
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 }\).
  1. State the features of the graph that identify it as \(K _ { 4 }\).
  2. 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 }\).
  3. 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
11 marks Moderate -0.8
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.
  1. Calculate the shortest length of stitch required to embroider Logo 1 .
  2. Calculate the shortest length of stitch required to embroider Logo 2.
  3. Hence, determine the difference in the length of stitching required for the two Logos.
Edexcel D1 Q6
15 marks Standard +0.3
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.
MonthSeptemberOctoberNovember
Manufacturing costs per set during each month (£)500800600
Demand for sets at the end of each month8001000700
Cost of storing sets during each month ( £ )-100150
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.
  2. Find as inequalities the constraints that apply in addition to \(x \geq 800\) and \(y \geq 0\).
    (2 marks)
  3. On graph paper, illustrate these inequalities and label clearly the feasible region.
    (4 marks)
  4. 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
15 marks Moderate -0.3
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.
  1. Execute a forward scan to calculate the early times and a backward scan to calculate the late times, for each event.
  2. Determine which activities lie on the critical path and list them in order.
  3. 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.
  4. Activity \(N\) could be completed in 1 day at an extra cost of \(\pounds 90000\). Explain why doing this is not economical.
    (3 marks)
  5. 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}
    ABCDE\(F\)
    A-130190155140125
    B130-215200190170
    C190215-110180100
    D155200110-7045
    E14019018070-75
    \(F\)1251701004575-
    \section*{Please hand this sheet in for marking}
    1. \(n\)\(x _ { n }\)\(a\)Any more data?\(x _ { n + 1 }\)\(b\)\(( b - a ) > 0\) ?\(a\)
      188Yes22No2
      2--
      Final output
    2. \(\_\_\_\_\) 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}
    6. \includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-12_764_1612_402_255}
    7. \(\_\_\_\_\)
    8. \(\_\_\_\_\)
    9. \(\_\_\_\_\)
    10. \(\_\_\_\_\)
Edexcel D1 Q1
6 marks Moderate -0.8
  1. 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.
DurnessHelmsdaleInvernessThursoWick
Durness-681238192
Helmsdale68-1027264
Inverness123102-148127
Thurso8172148-48
Wick926412748-
  1. 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.
  2. Calculate the minimum total length of cable required.
Edexcel D1 Q2
7 marks Moderate -0.8
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.
  1. Describe a strategy which would enable the contestant to find the chosen name in as few guesses as possible.
  2. 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
8 marks Challenging +1.2
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,
  1. 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,
  2. find the range of values for the maximum flow from \(S\) to \(T\).
  3. 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
11 marks Moderate -0.8
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.
MinisterGovernment Position
\(P\)Chancellor ( \(C\) )
\(Q\)Foreign Secretary ( \(F\) ), Minister for Education ( \(E\) )
\(R\)Minister for Defence ( \(D\) ), Minister for Industry ( \(I\) )
SMinister for Defence ( \(D\) ), Home Secretary ( \(H\) )
\(T\)Home Secretary (H)
\(U\)Chancellor ( \(C\) ), Foreign Secretary ( \(F\) )
  1. 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.
  2. Draw this initial matching.
  3. 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.
  4. Explain why no complete matching is now possible.
    (2 marks)
Edexcel D1 Q5
11 marks Moderate -0.5
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.
  1. Describe an appropriate algorithm that can be used to find this minimum time.
    (3 marks)
  2. 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.
  3. 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)
Edexcel D1 Q6
16 marks Moderate -0.3
6. The table below shows the maximum flows possible within a system.
To From\(S\)\(A\)\(B\)\(C\)D\(T\)
S-353055--
A-----50
B-12-8-20
C----1530
D-----14
T------
For example, the maximum flow from \(B\) to \(A\) is 12 units.
  1. Draw a digraph to represent this information.
  2. Give the capacity of the cut \(\{ S , A , B , C \} \mid \{ D , T \}\).
  3. Find the minimum cut, stating its capacity, and expressing it in the form \(\{ \quad \} \mid \{ \quad \}\).
  4. 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.
  5. Explain how you know that you have found the maximum possible flow.
  6. Give an example of a practical situation that could be modelled by the original table.
Edexcel D1 Q7
16 marks Standard +0.8
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.
  1. 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.
  2. \(\_\_\_\_\)
Edexcel D1 Q1
6 marks Easy -1.2
  1. (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
7 marks Moderate -0.8
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.
DesignKendalMilvertonArlingtonElfordGrosvenor
Plot area ('000 \(\mathrm { m } ^ { 2 }\) )3113510
Value ( \(\pounds ^ { \prime } 000 \mathrm {~s}\) )1001904080120
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.
  2. Explain how this method could be altered if more than one of each design is allowed.
Edexcel D1 Q3
7 marks Easy -1.2
3. (a) Draw a graph with 6 vertices, each of degree 1 .
(b) Draw two graphs with 6 vertices, each of degree 2 such that:
  1. the graph is connected,
  2. the graph is not connected. A simple connected graph has 5 vertices each of degree \(x\).
    (c) Find the possible values of \(x\) and explain your answer.
    (d) For each value of \(x\) you found in part (c) draw a possible graph.
Edexcel D1 Q4
12 marks Standard +0.3
4. A company produces \(x _ { 1 }\) finished articles at the end of January, \(x _ { 2 }\) finished articles at the end of February, \(x _ { 3 }\) finished articles at the end of March, \(x _ { 4 }\) finished articles at the end of April. Other details for each month are as follows:
MonthJanuaryFebruaryMarchApril
Demand at end of month200350250200
Production costs per article£1000£1800£1600£1900
The cost of storing each finished but unsold article is \(\pounds 500\) per month. Thus, for example, any article unsold at the end of January would incur a \(\pounds 500\) charge if it is stored until the end of February or a \(\pounds 1000\) charge if it is stored until the end of March. There must be no unsold stock at the end of April.
The selling price of each article is \(\pounds 4000\) and the total profit ( \(\pounds P\) ) must be maximised.
  1. Rewrite \(x _ { 4 }\) in terms of the other 3 variables.
  2. Show that the total cost incurred \(( \pounds C )\) is given by: $$C = 600 x _ { 1 } + 900 x _ { 2 } + 200 x _ { 3 } + 1125000$$
  3. Hence, show that \(P = { } ^ { - } 600 x _ { 1 } - 900 x _ { 2 } - 200 x _ { 3 } + 2875000\).
  4. Three of the constraints operating can be expressed as \(x _ { 1 } \geq 200\), \(x _ { 2 } \geq 0\) and \(x _ { 3 } \geq 0\). Write down inequalities representing two further constraints.
    (2 marks)
  5. Explain why it is not appropriate to use a graphical method to solve this problem.
  6. An employee of the company wishes to use the Simplex algorithm to solve the problem. He tries to generate an initial tableau with \(x _ { 1 } , x _ { 2 }\) and \(x _ { 3 }\) as the non-basic variables. Explain why this is not appropriate and explain what he should do instead. You are not required to generate an initial tableau or to solve the problem.
    (2 marks)