| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Year | 2021 |
| Session | November |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Combinations & Selection |
| Type | Pigeonhole principle applications |
| Difficulty | Challenging +1.2 This question tests Stirling numbers of the second kind (partitions) and a straightforward pigeonhole principle application. Parts (a)-(c) involve systematic counting of set partitions with guided scaffolding, while part (d) is a direct pigeonhole application (8 numbers, at most 6 pieces). The concepts are non-trivial for Further Maths but the execution is methodical rather than requiring deep insight. |
| Spec | 7.01b Set notation: basic language and notation of sets, partitions7.01c Pigeonhole principle |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (a) | 5 partitions into a set of size 1 and a set of size 4 |
| {X | X, X, X, X} |
| Answer | Marks |
|---|---|
| {X, X | X, X, X} |
| Answer | Marks |
|---|---|
| 2 | B1 |
| B1 | 1.1 |
| 2.5 | 5 where smaller set has size 1 or 5C = 5 |
| Answer | Marks | Guidance |
|---|---|---|
| {A}, {B, C, D, E} | {B}, {A, C, D, E} | B1 |
| {C}, {A, B, D, E} | {D}, {A, B, C, E} | smaller set has size 1 |
| {E}, {A, B, C, D} | May just list one set, e.g. {A}, {B}, {C}, {D}, {E} | |
| {A, B}, {C, D, E} | {A, C}, {B, D, E} | List (or any equivalent) that has 10 distinct cases sets where smaller |
| {A, D}, {B. C. E} | {A, E}, {B, C, D} | set has size 2 |
| {B, C}, {A, D, E} | {B, D}, {A, C, E} | B1 |
| {B, E}, {A, C, D} | {C, D}, {A, B, E} |
| Answer | Marks |
|---|---|
| {C, E}, {A, B, D} | {D, E}, {A, B, C} |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (b) | Partitions into sets of sizes 1, 1 and 3 |
| Answer | Marks |
|---|---|
| 2 | M1 |
| Answer | Marks |
|---|---|
| [4] | 1.1 |
| Answer | Marks |
|---|---|
| 2.1 | Considering cases where set sizes are 1, 1, 3 |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (c) | 10 partitions into sets of sizes 1, 1, 1, 2 |
| Answer | Marks |
|---|---|
| 15 + 25 + 10 + 1 = 51 | M1 |
| Answer | Marks |
|---|---|
| [2] | 2.1 |
| 1.1 | Trying to deal with the cases when there are more than 3 subsets |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (d) | Number line is split into 6 pieces |
| Answer | Marks |
|---|---|
| Hence result by the pigeonhole principle | B1 |
| Answer | Marks |
|---|---|
| [2] | 2.1 |
| 2.2a | 6 pieces |
Question 1:
1 | (a) | 5 partitions into a set of size 1 and a set of size 4
{X | X, X, X, X}
10 partitions into a set of size 2 and a set of size 3
{X, X | X, X, X}
because there are 5C choices for the set of size 2
2 | B1
B1 | 1.1
2.5 | 5 where smaller set has size 1 or 5C = 5
1
10 where smaller set has size 2, with an explanation of why it is 10
(note the total of 15 is given in the question)
e.g. 5C = 10 or (5×4) ÷ 2 = 10 or 4 + 3 + 2 + 1 = 10
2
Alternative solution
{A}, {B, C, D, E} | {B}, {A, C, D, E} | B1 | List (or any equivalent) that has exactly 5 distinct cases where
{C}, {A, B, D, E} | {D}, {A, B, C, E} | smaller set has size 1
{E}, {A, B, C, D} | May just list one set, e.g. {A}, {B}, {C}, {D}, {E}
{A, B}, {C, D, E} | {A, C}, {B, D, E} | List (or any equivalent) that has 10 distinct cases sets where smaller
{A, D}, {B. C. E} | {A, E}, {B, C, D} | set has size 2
{B, C}, {A, D, E} | {B, D}, {A, C, E} | B1 | May just list one set, e.g. {A, B}, {A, C} {A, D}, {A, E}, {B, C},
{B, E}, {A, C, D} | {C, D}, {A, B, E}
{B, D}, {B, E}, {C, D}, {C, E}, {D, E}
{C, E}, {A, B, D} | {D, E}, {A, B, C}
[2]
1 | (b) | Partitions into sets of sizes 1, 1 and 3
5 × 4 ÷ 2 = 10 partitions of this type
Partitions into sets of sizes 1, 2 and 2
5 × (4C ÷ 2) = 5 × 3 = 15 partitions of this type
2 | M1
A1
M1
A1
[4] | 1.1
2.1
1.1
2.1 | Considering cases where set sizes are 1, 1, 3
Explanation of why there are 10 of these
e.g. 5C = 10 or 5 × 4 ÷ 2 = 10 or a list of the cases
3
Considering cases where set sizes are 1, 2, 2
Explaining why there are 15 of these
e.g a relevant calculation or list of cases
1 | (c) | 10 partitions into sets of sizes 1, 1, 1, 2
1 partition into sets of sizes 1, 1, 1, 1, 1
15 + 25 + 10 + 1 = 51 | M1
A1
[2] | 2.1
1.1 | Trying to deal with the cases when there are more than 3 subsets
May be implied from answer 51
51
1 | (d) | Number line is split into 6 pieces
But there are 8 numbers
Hence result by the pigeonhole principle | B1
B1
[2] | 2.1
2.2a | 6 pieces
Using pigeonhole, or explaining why there must be at least one piece
with two or more numbers1 A set consists of five distinct non-integer values, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }$ and E .
The set is partitioned into non-empty subsets and there are at least two subsets in each partition.
\begin{enumerate}[label=(\alph*)]
\item Show that there are 15 different partitions into two subsets.
\item Show that there are 25 different partitions into three subsets.
\item Calculate the total number of different partitions.
The numbers 12, 24, 36, 48, 60, 72, 84 and 96 are marked on a number line. The number line is then cut into pieces by making cuts at $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }$ and E , where $0 < \mathrm { A } < \mathrm { B } < \mathrm { C } < \mathrm { D } < \mathrm { E } < 100$.
\item Explain why there must be at least one piece with two or more of the numbers 12, 24, 36, 48, 60, 72, 84 and 96.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2021 Q1 [10]}}