| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Year | 2018 |
| Session | June |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | First-Fit Bin Packing |
| Difficulty | Moderate -0.3 This is a straightforward application of first-fit bin packing with clearly defined constraints. Part (i) requires following a simple algorithm mechanically, part (ii) involves basic optimization by considering total capacity (which students are guided toward), and part (iii) asks for a minor adaptation. The arithmetic is simple and the problem-solving is routine for Further Maths students studying this topic. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Crate 1: 12 small jars | M1 | Crates 1 and 2 correct |
| Crate 2: 5 small and 1 medium jar | A1 | All correct, in this order |
| Crates 3 and 4: 3 medium jars each | [2] | May use S, M, L provided intention is obvious; if using e.g. 4S for M, must have defined this for A1 |
| Crates 5, 6 and 7: 1 large jar each |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| E.g. Crates 1, 2 and 3: 1 large jar and 3 small jars each | M1 | Attempt a packing using 6 crates |
| Crates 4 and 5: 3 medium jars each | A1 | Pack 17 small, 7 medium and 3 large in 6 boxes, any order |
| Crate 6: 1 medium and 8 small jars | B1 | \((17 + 7\times4 + 3\times9)\div12 = 72\div12 = 6\) |
| There is no spare capacity/six full crates/all full | [3] | For reference: Crate size \(= 12\); Medium \(= \times4\), large \(= \times9\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| e.g. Put each large jar in a box, then put two medium jars in boxes until no more pairs are possible. Put any remaining medium jar in another box and fill in the spaces with small jars. | E1 [1] | Description of a general minimising strategy that has at most 2 medium jars in any box |
# Question 1:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Crate 1: 12 small jars | M1 | Crates 1 and 2 correct |
| Crate 2: 5 small and 1 medium jar | A1 | All correct, in this order |
| Crates 3 and 4: 3 medium jars each | [2] | May use S, M, L provided intention is obvious; if using e.g. 4S for M, must have defined this for A1 |
| Crates 5, 6 and 7: 1 large jar each | | |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| E.g. Crates 1, 2 and 3: 1 large jar and 3 small jars each | M1 | Attempt a packing using 6 crates |
| Crates 4 and 5: 3 medium jars each | A1 | Pack 17 small, 7 medium and 3 large in 6 boxes, any order |
| Crate 6: 1 medium and 8 small jars | B1 | $(17 + 7\times4 + 3\times9)\div12 = 72\div12 = 6$ |
| There is no spare capacity/six full crates/all full | [3] | For reference: Crate size $= 12$; Medium $= \times4$, large $= \times9$ |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| e.g. Put each large jar in a box, then put two medium jars in boxes until no more pairs are possible. Put any remaining medium jar in another box and fill in the spaces with small jars. | E1 [1] | Description of a general minimising strategy that has at most 2 medium jars in any box |
---1 Some jars need to be packed into small crates.\\
There are 17 small jars, 7 medium jars and 3 large jars to be packed.
\begin{itemize}
\item A medium jar takes up the same space as four small jars.
\item A large jar takes up the same space as nine small jars.
\end{itemize}
Each crate can hold:
\begin{itemize}
\item at most 12 small jars,
\item or at most 3 medium jars,
\item or at most 1 large jar (and 3 small jars),
\item or a mixture of jars of different sizes.\\
(i) One strategy is to fill as many crates as possible with small jars first, then continue using the medium jars and finally the large jars.
\end{itemize}
Show that this method will use seven crates.
The jars can be packed using fewer than seven crates.\\
(ii) The jars are to be packed in the minimum number of crates possible.
\begin{itemize}
\item Describe how the jars can be packed in the minimum number of crates.
\item Explain how you know that this is the minimum number of crates.
\end{itemize}
Some other numbers of the small, medium and large jars need to be packed into boxes.\\
The number of jars that a box can hold is the same as for a crate, except that
\begin{itemize}
\item a box cannot hold 3 medium jars.\\
(iii) Describe a packing strategy that will minimise the number of boxes needed.
\end{itemize}
\hfill \mbox{\textit{OCR Further Discrete AS 2018 Q1 [6]}}