A2 June 2023 Q4
4. The eleven distinct numbers listed below are to be packed into bins of size 40
| 15 | 22 | 3 | 9 | 23 | \(x\) | 5 | 4 | 18 | 20 | 13 |
It is known that \(x\)
- is an integer less than 40
- is the largest number in the list
Given that it is possible to pack the numbers into 4 bins of size 40
When the first-fit decreasing bin packing algorithm is applied to the list, neither the 15 nor the 13 is placed in the first bin.
| Scheme | Marks | AO |
|---|---|---|
| \(132 + x \gt 120\) for all positive values of \(x\) therefore 3 bins is not possible | B1 | 2.4 |
| (1) |
Notes
B1: Correct reasoning for why 3 bins is not possible or at least 4 bins are required
Examples of B1:
- If \(x \gt 23\) then \(132 + x\) is at least 156 and \(\dfrac{156}{40} = 3.9\) so 3 is not possible
- The lower bound for the number of bins is \(\dfrac{156}{40} = 3.9\) so 3 is not possible
- If \(x = 24\) then \(\dfrac{156}{40} = 3.9\) so 3 is not possible (or comparing 156 with 120)
- If \(x \gt 23\) then \(132 + x\) is > 155 so you would need to have more than \(\dfrac{155}{40} = 3.875\) bins so is not possible (condone ‘at least’ rather than ‘more than’ on the bod so condone comparing 155 with 120)
- 4 values are at least half the capacity of a bin (or at least 20) and they are 20, 22, 23 and \(x\), so 3 so not possible (must explicitly state the four values but condone those candidates who imply that the 20, 22, 23 and the \(x\) are all greater than half the capacity of a bin)
- Comparing 132 with 120 and saying that 3 is not possible (no mention of \(x\) is required)
- \(x\) would have to be \(-12\) for it to be possible (but not just that \(x\) would have to be negative)
| Scheme | Marks | AO |
|---|---|---|
| \(23 \lt x \leqslant 28\) | B1 B1 | 2.2a 2.2a |
| (2) |
Notes
B1: One correct inequality (\(x \gt 23,\ x \geqslant 24,\ x \leqslant 28\) or \(x \lt 29\))
B1: CAO (\(23 \lt x \leqslant 28\) or \(24 \leqslant x \leqslant 28\) or 29 with a strict inequality)
| Scheme | Marks | AO |
|---|---|---|
| Bin 1: \(\underline{15}\) \(\underline{22}\) \(\underline{3}\) Bin 2: \(\underline{9}\) \(\underline{23}\) \(\boxed{5}\) Bin 3: \(\boxed{x}\) \(\boxed{4}\) Bin 4: 18 20 Bin 5: 13 | M1 A1 A1 | 1.1b 1.1b 1.1b |
| (3) |
Notes
(c) NO MISREADS MARK EXACTLY TO THE SCHEME – if \(x\) is given a value then M1 only
M1: First five values placed correctly (underlined values) and the \(x\) not in Bin 1 or 2 – at least eight values placed (condone cumulative values for M1 only)
A1: First eight values places correctly (underlined and boxed values with no repeated values)
A1: CSO no additional/repeated values
| Scheme | Marks | AO | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| M1 A1 A1ft A1 | 1.1b 1.1b 1.1b 1.1b | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (4) |
Notes
M1: Quick sort, pivot, p, chosen (must be choosing middle left or right – choosing first/last item as the pivot is M0). After the first pass the list must read (values greater than the pivot), pivot, (values less that the pivot). If only choosing one pivot per iteration then max of M1A1 only – Bubble sort is not a MR and scores M0
A1: First two passes correct (pivots for third pass need not be chosen)
A1ft: Third and fourth passes correct (follow through from their second pass and choice of consistent pivots). They do not need to be choosing a pivot for the fifth pass for this mark. After their second pass their list must contain either 10, 11 or 12 numbers (so allow one additional or one missing number or a slip in one number e.g. the 5 becoming a 6)
A1: CSO (correct solution only – all previous marks in this part must have been awarded) – both middle left and middle right require six passes
SC: If the list is sorted in ascending order, then award a maximum of M1A1A0A0 (so 2 marks) as in the scheme above even if the list is re-ordered after the sort is complete
Ascending (below is middle-right for middle-left the pivot is the 23):
| 15 | 22 | 3 | 9 | 23 | \(\boldsymbol{x}\) | 5 | 4 | 18 | 20 | 13 |
| 15 | 22 | 3 | 9 | 23 | 5 | 4 | 18 | 20 | 13 | \(\underline{x}\) |
| 3 | 4 | 5 | 15 | 22 | 9 | 23 | 18 | 20 | 13 | \(x\) |
Middle left:
| 15 | 22 | 3 | 9 | 23 | \(\boldsymbol{x}\) | 5 | 4 | 18 | 20 | 13 |
| \(\underline{x}\) | 15 | 22 | 3 | 9 | 23 | 5 | 4 | 18 | 20 | 13 |
| \(\underline{x}\) | \(\underline{23}\) | 15 | 22 | 3 | 9 | 5 | 4 | 18 | 20 | 13 |
| \(\underline{x}\) | \(\underline{23}\) | 15 | 22 | 9 | 18 | 20 | 13 | \(\underline{5}\) | 3 | 4 |
| \(\underline{x}\) | \(\underline{23}\) | 15 | 22 | 18 | 20 | 13 | \(\underline{9}\) | \(\underline{5}\) | 4 | \(\underline{3}\) |
| \(\underline{x}\) | \(\underline{23}\) | 22 | 20 | \(\underline{18}\) | 15 | 13 | \(\underline{9}\) | \(\underline{5}\) | 4 | \(\underline{3}\) |
| \(\underline{x}\) | \(\underline{23}\) | \(\underline{22}\) | 20 | \(\underline{18}\) | \(\underline{15}\) | 13 | \(\underline{9}\) | \(\underline{5}\) | 4 | \(\underline{3}\) |
| Scheme | Marks | AO | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
e.g. attempt at first-fit decreasing (or clearly considering the cases in the correct order)
| B1 | 3.1a | ||||||||||||
| Therefore, \(x\) must be 28 | dB1 | 2.2a | ||||||||||||
| (2) | ||||||||||||||
| (12 marks) |
Notes
B1: any clear indication that as the 15 does not fit in Bin 1 then \(x + 15 \gt 40\) (condone for this mark just stating \(x \gt 25\)) or any clear indication that as the 13 does not fit in Bin 1 then \(x + 13 \gt 40\) (condone for this mark just stating that \(x \gt 27\))
dB1: correct answer of \(x = 28\) – this mark is dependent on the previous B mark and the correct upper bound of 28 in (b) (so if \(x = 28\) stated with no justification then no marks). As a minimum accept \(x + 13 \gt 40\) therefore \(x \gt 27\) so \(x = 28\) (just ‘\(x \gt 27\) so \(x = 28\)’ scores B1 B0 unless explicit mention of where \(x \gt 27\) has come from)
SC in (e): if B0B0 then award B1B0 for the first 7 values placed correctly in bins just once (ignore the other values)
| Bin 1: | \(x\) |
| Bin 2: | 23 15 |
| Bin 3: | 22 18 |
| Bin 4: | 20 13 |