| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2021 |
| Session | November |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Combinations & Selection |
| Type | Bin packing problems |
| Difficulty | Moderate -0.3 This is a straightforward bin packing question requiring application of the first-fit algorithm (routine procedure), basic reasoning about why 4 bags are insufficient (simple observation that largest items exceed capacity), and a greedy optimization problem solved by inspection. All parts are mechanical applications of standard algorithms with no novel insight required, making it slightly easier than average A-level. |
| Spec | 7.01c Pigeonhole principle7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Item | \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) | \(G\) | \(H\) |
| Mass (kg) | 3 | 4 | 3.5 | 2.5 | 6 | 7.5 | 8 | 5 |
| Item | \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) | \(G\) | \(H\) |
| Mass (kg) | 3 | 4 | 3.5 | 2.5 | 6 | 7.5 | 8 | 5 |
| Value | 6 | 10 | 12 | 10 | 16 | 12 | 20 | 14 |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (a) | Bag 1: A B D |
| Answer | Marks |
|---|---|
| Bag 5: H | M1* |
| Answer | Marks |
|---|---|
| [3] | 1.1 |
| Answer | Marks |
|---|---|
| 1.1 | Bag 1 starts A B (or 3 4) and bag 2 starts C (or 3.5) |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (b) | G must be in a bag on its own, since 8 + 2.5 > 10 |
| The remaining seven items have total mass 31.5 kg > 310 kg | M1 | |
| A1 | 3.4 | |
| 2.3 | G must be on its own |
| Answer | Marks |
|---|---|
| Alternative method | G must be its own or identifying ways to make 10 or 9.5 |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (c) | Leave A behind |
| Answer | Marks |
|---|---|
| the best possibility. | B1 |
| Answer | Marks |
|---|---|
| [3] | 2.2a |
| Answer | Marks |
|---|---|
| 3.4 | A |
Question 1:
1 | (a) | Bag 1: A B D
Bag 2: C E
Bag 3: F
Bag 4: G
Bag 5: H | M1*
M1dep*
A1
[3] | 1.1
1.1
1.1 | Bag 1 starts A B (or 3 4) and bag 2 starts C (or 3.5)
D is in bag 1 and E is in bag 2 (using letters)
All correct
(using letters and in the correct order within bags)
1 | (b) | G must be in a bag on its own, since 8 + 2.5 > 10
The remaining seven items have total mass 31.5 kg > 310 kg | M1
A1 | 3.4
2.3 | G must be on its own
Explaining why this means that 4 bags are not enough
Alternative method | G must be its own or identifying ways to make 10 or 9.5
4 bags would mean 3 full bags and one with 9.5 kg
G must be in a bag on its own, since 10 – 8 = 2 < 2.5
So cannot make a bag containing G with mass 9.5 or 10 kg
[2]
1 | (c) | Leave A behind
EB, FD, G, HC or EC, FD, G, HB
Must leave out at least one. The value of A is the smallest so this is
the best possibility. | B1
B1ft
B1
[3] | 2.2a
3.1b
3.4 | A
A possible packing
Value of A is lower than any other
A has the lowest value
SC B1 leave F because it has the lowest value per kg
G must be its own or identifying ways to make 10 or 9.51 Sam is packing for a holiday. The table shows the mass of each item to be packed.
\begin{center}
\begin{tabular}{ | l | c | c | c | c | c | c | c | c | }
\hline
Item & $A$ & $B$ & $C$ & $D$ & $E$ & $F$ & $G$ & $H$ \\
\hline
Mass (kg) & 3 & 4 & 3.5 & 2.5 & 6 & 7.5 & 8 & 5 \\
\hline
\end{tabular}
\end{center}
Sam's bags can each carry 10 kg , but no more.
\begin{enumerate}[label=(\alph*)]
\item Use first-fit to show a possible packing that Sam could use. Indicate the items by using the letters $A , B , \ldots$ rather than their masses.
The total mass of the 8 items is 39.5 kg . Sam says that this means they can be packed using just 4 bags.
\item Explain why Sam cannot pack the items using just 4 bags.
Sam is only allowed to take 4 bags. Each item is given a value out of 20 representing how important it is to Sam.
\begin{center}
\begin{tabular}{ | l | c | c | c | c | c | c | c | c | }
\hline
Item & $A$ & $B$ & $C$ & $D$ & $E$ & $F$ & $G$ & $H$ \\
\hline
Mass (kg) & 3 & 4 & 3.5 & 2.5 & 6 & 7.5 & 8 & 5 \\
\hline
Value & 6 & 10 & 12 & 10 & 16 & 12 & 20 & 14 \\
\hline
\end{tabular}
\end{center}
\item Sam wishes to pack items with a large total value.
\begin{itemize}
\item State which item Sam should leave behind to maximise the total value.
\item Write down a possible packing with this item omitted.
\item Explain why no larger total is possible.
\end{itemize}
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2021 Q1 [8]}}