| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2024 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Groups |
| Difficulty | Standard +0.3 This question involves basic combinatorics (listing derangements of 4 elements), problem classification, and elementary graph theory (digraph properties, arc counting, Euler's formula). While it requires understanding of multiple concepts, each part is straightforward application of definitions with minimal problem-solving depth. The derangement enumeration is tedious but routine, and the graph theory is A-level standard rather than requiring deep group theory despite the topic label. |
| Spec | 7.01m Derangements: enumeration by ad hoc methods |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (a) | A chooses B B B C C C D D D |
| Answer | Marks |
|---|---|
| D chooses C A C B B A C B A | M1 |
| Answer | Marks |
|---|---|
| [2] | 1.1 |
| 1.1 | Any three correct derangements (not including the one given) |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (b) | Existence |
| [1] | 1.2 | |
| 1 | (c) | e.g. |
| A might choose B but B not choose A | B1 | |
| [1] | 2.4 | An example to explain why graph must be directed |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (d) | 8 |
| [1] | 1.1 | 8 cao |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (e) | V + R = E + 2 5 + R = 8 + 2 |
| R = 5 | M1 |
| Answer | Marks |
|---|---|
| [2] | 1.1 |
| 1.1 | Attempt to use Euler’s formula, with 5, 2 and ‘their 8’, |
| Answer | Marks | Guidance |
|---|---|---|
| A chooses | B | B |
| B chooses | A | C |
| C chooses | D | D |
| D chooses | C | A |
| 1 | -2 | 1 |
| 1 | 0 | -1 |
| 1 | 0 |
Question 1:
1 | (a) | A chooses B B B C C C D D D
B chooses A C D A D D A C C
C chooses D D A D A B B A B
D chooses C A C B B A C B A | M1
A1
[2] | 1.1
1.1 | Any three correct derangements (not including the one given)
All correct and no repeats or extras (except allow given
derangement repeated)
1 | (b) | Existence | B1
[1] | 1.2
1 | (c) | e.g.
A might choose B but B not choose A | B1
[1] | 2.4 | An example to explain why graph must be directed
Or an appropriate description involving who is choosing
(gifting) and who was chosen (receiving)
e.g.
The person chosen by a worker need not choose that worker
A giving a gift to B is not the same as B giving a gift to A
1 | (d) | 8 | B1
[1] | 1.1 | 8 cao
2×4 (= 8), 4+4 (= 8), 4 arcs for each of two years (so 8)
1 | (e) | V + R = E + 2 5 + R = 8 + 2
R = 5 | M1
A1 FT
[2] | 1.1
1.1 | Attempt to use Euler’s formula, with 5, 2 and ‘their 8’,
allow other notation (e.g. A for R)
5 (regions) or ‘their 8’ – 3
FT their 8 from part (d)
A chooses | B | B | B | C | C | C | D | D | D
B chooses | A | C | D | A | D | D | A | C | C
C chooses | D | D | A | D | A | B | B | A | B
D chooses | C | A | C | B | B | A | C | B | A
1 | -2 | 1 | -1 | 0 | 0 | 0 | 0
1 | 0 | -1 | -1 | 0 | 2 | 0 | 12
1 | 01 At the end of each year the workers at an office take part in a gift exchange.\\
Each worker randomly chooses the name of one other worker and buys a small gift for that person.
Each worker's name is chosen by exactly one of the others.\\
A worker cannot choose their own name.
In the first year there were four workers, $\mathrm { A } , \mathrm { B } , \mathrm { C }$ and D .\\
There are 9 ways in which A, B, C and D can choose the names for the gift exchange. One of these is already given in the table in the Printed Answer Booklet.
\begin{enumerate}[label=(\alph*)]
\item Complete the table in the Printed Answer Booklet to show the remaining 8 ways in which the names can be chosen.
During the second year, worker D left and was replaced with worker E.\\
The organiser of the gift exchange wants to know whether it is possible for the event to happen for another 3 years (starting with the second year) with none of the workers choosing a name they have chosen before, assuming that there are no further changes in the workers.
\item Classify the organiser's problem as an existence, construction, enumeration or optimisation problem.
After the second year, the organiser drew a graph showing who each worker chose in the first two years of the gift exchange.\\
None of the workers chose the same name in the first and second years.\\
The vertices of the graph represented the workers, A, B, C, D and E, and the arcs showed who had been chosen by each worker.
\item Explain why the graph must be a digraph.
\item State the number of arcs in the digraph that shows the choices for the first two years.
\item Assuming that the digraph created in part (d) is planar, use Euler's formula to calculate how many regions it has.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2024 Q1 [7]}}