| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Year | 2020 |
| Session | November |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Principle of Inclusion/Exclusion |
| Type | Finding Set Cardinalities from Constraints |
| Difficulty | Moderate -0.8 This is a straightforward bin-packing problem with mostly conceptual questions requiring minimal calculation. Parts (a)-(c) test basic understanding of construction vs. optimization problems and feasibility. Parts (d)-(e) apply standard first-fit algorithm and simple counting. The mathematics is elementary (addition of decimals, basic combinatorics) with no novel problem-solving required—easier than typical A-level questions. |
| Spec | 7.01a Types of problem: existence, construction, enumeration, optimisation7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Package | A | B | C | D | E | F | G | H | I | J |
| Volume \(\left( \mathrm { m } ^ { 3 } \right)\) | 0.20 | 0.05 | 0.15 | 0.25 | 0.04 | 0.03 | 0.02 | 0.02 | 0.12 | 0.12 |
| Answer | Marks | Guidance |
|---|---|---|
| 2 | (a) | How can I fit the packages in the boxes? |
| Answer | Marks | Guidance |
|---|---|---|
| She does not need to enumerate the number of solutions | B1 | |
| [1] | Correct question chosen with a valid reason | |
| 2 | (b) | A solution may not exist because the packages may be the wrong shapes. |
| Answer | Marks |
|---|---|
| 6 × 0.15 m3 and 4× 0.025 m3) | B1 |
| [1] | Shape matters as well as volume |
| Answer | Marks | Guidance |
|---|---|---|
| 2 | (c) | Would need all four boxes full, with no space left |
| Answer | Marks |
|---|---|
| 0.02. So impossible to fill 4 boxes | B1 |
| Answer | Marks |
|---|---|
| [2] | This first statement may be implied |
| Answer | Marks | Guidance |
|---|---|---|
| 2 | (d) | Box 1 A B |
| Answer | Marks |
|---|---|
| Box 5 J | M1 |
| Answer | Marks |
|---|---|
| [2] | A, B, C, D placed correctly |
| Answer | Marks | Guidance |
|---|---|---|
| 2 | (e) | 8 – (3 + 3) + 1 |
| = 3 | M1 |
| Answer | Marks |
|---|---|
| [2] | Or 3 + 3 – 1 = 5 shown on a Venn diagram |
| Answer | Marks |
|---|---|
| Box 1 | A B |
| Box 2 | C E F G |
| Box 3 | D |
| Box 4 | H I |
| Box 5 | J |
Question 2:
2 | (a) | How can I fit the packages in the boxes?
She needs to find a solution, although it may not be a good solution
She does not need to enumerate the number of solutions | B1
[1] | Correct question chosen with a valid reason
2 | (b) | A solution may not exist because the packages may be the wrong shapes.
May have a package that is too big (> 0.25 m3)
Could have packages that cannot be paired together to fit in six boxes (e.g.
6 × 0.15 m3 and 4× 0.025 m3) | B1
[1] | Shape matters as well as volume
Or explaining why total volume = 1 m3 does not mean that
individual volumes are small enough
2 | (c) | Would need all four boxes full, with no space left
A(0.20), C(0.15), D(0.25) must be in 3 separate boxes.
I(0.12) and J(0.12) cannot be in the same box as A, C or D so I and J are
together in another box
The box with I and J has 0.01 spare, but the smallest package has volume
0.02. So impossible to fill 4 boxes | B1
B1
[2] | This first statement may be implied
I and J must be together
(e.g showing a solution in which A, C and D are in
separate boxes and I, J are together in a box)
Explaining why this means that 4 boxes are not enough
(not just showing that first fit decreasing fails)
2 | (d) | Box 1 A B
Box 2 C E F G
Box 3 D
Box 4 H I
Box 5 J | M1
A1
[2] | A, B, C, D placed correctly
(if letters are not used, 0.20, 0.05, 0.15, 0.25 placed
correctly = M1 A0)
All correct, using letters
2 | (e) | 8 – (3 + 3) + 1
= 3 | M1
A1
[2] | Or 3 + 3 – 1 = 5 shown on a Venn diagram
3, from correct working seen
Box 1 | A B
Box 2 | C E F G
Box 3 | D
Box 4 | H I
Box 5 | J2 Jameela needs to store ten packages in boxes. She has a list showing the size of each package. The boxes are all the same size and Jameela can use up to six of these boxes to store all the packages.
\begin{enumerate}[label=(\alph*)]
\item Which of the following is a question that Jameela could ask which leads to a construction problem? Justify your choice.
\begin{itemize}
\item In how many different ways can I fit the packages in the boxes?
\item How can I fit the packages in the boxes?
\end{itemize}
The total volume of the packages is $1 \mathrm {~m} ^ { 3 }$. The volume of each of the six boxes is $0.25 \mathrm {~m} ^ { 3 }$.
\item Explain why a solution to the problem of storing all the packages in six boxes may not exist.
The volume of each package is given below.
\begin{center}
\begin{tabular}{ | l | c | c | c | c | c | c | c | c | c | c | }
\hline
Package & A & B & C & D & E & F & G & H & I & J \\
\hline
Volume $\left( \mathrm { m } ^ { 3 } \right)$ & 0.20 & 0.05 & 0.15 & 0.25 & 0.04 & 0.03 & 0.02 & 0.02 & 0.12 & 0.12 \\
\hline
\end{tabular}
\end{center}
\item By considering the five largest packages (A, C, D, I and J) first, explain what happens if Jameela tries to pack the 10 packages using only four boxes.
You may now assume that the packages will always fit in the boxes if there is enough volume.
\item Use first-fit to find a way of storing the packages in the boxes. Show the letters of the packages in each box, in the order that they are packed into that box.
The order of the packages within a box does not matter and the order of the boxes does not matter. So, for example, having A and E in box 1 is the same as having E and A in box 2 , but different from having A in one box and E in a different box.
\item Suppose that packages A and B are not in the same box. In this case the following are true:
\begin{itemize}
\item there are 8 different ways to put any or none of $\mathrm { E } , \mathrm { F } , \mathrm { G }$ and H with A
\item 3 include F with A
\item 3 include G with A
\item 1 includes both F and G with A
\end{itemize}
Use the inclusion-exclusion principle to determine how many of the 8 ways include neither package F nor package G.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2020 Q2 [8]}}