OCR Further Discrete AS (Further Discrete AS) 2024 June

1 There are six non-isomorphic trees with exactly six vertices.
A student has drawn the diagram below showing six trees each with exactly six vertices. However, two of the trees that the student has drawn are isomorphic. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Identify which two of these trees are isomorphic.
2. Draw an example of the missing tree. Graph G has exactly six vertices.
   The degree sequence of G is \(1,1,1,3,3,3\).
3. Without using a sketch, calculate the number of edges in graph G.
4. Explain how the result from part (c) shows that graph G is not a tree. In a simple graph with six vertices each vertex degree must be one of the values \(0,1,2,3,4\) or 5 .
5. Use the pigeonhole principle to show that in a simple graph with six vertices there must be at least two vertices with the same vertex degree.

2 In a game two players are each dealt five cards from a set of ten different cards.
Player 1 is dealt cards A, B, F, G and J.
Player 2 is dealt cards C, D, E, H and I. Each player chooses a card to play.
The players reveal their choices simultaneously. The pay-off matrix below shows the points scored by player 1 for each combination of cards. Pay-off for player 1 \begin{table}[h] \end{table}

1. Determine the play-safe strategy for player 1, ignoring any effect on player 2. The pay-off matrix below shows the points scored by player 2 for each combination of cards.
   Pay-off for player 2 Player 1 \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Player 2}

   		C	D	E	H
   \cline { 2 - 6 } A	2	2	0	1	I
   \cline { 2 - 6 } B	3	1	2	1	2
   \cline { 2 - 6 } F	3	2	2	1	0
   \cline { 2 - 6 } G	1	3	0	0	0
   \cline { 2 - 6 } J	2	1	0	3	1
   \cline { 2 - 6 }
   \cline { 2 - 6 }

   \end{table}
2. Use a dominance argument to delete two columns from the pay-off matrix. You must show all relevant comparisons.
3. Explain, with reference to specific combinations of cards, why the game cannot be converted to a zero-sum game.

3 Heidi has a pack of cards.
Each card has a single digit on one side and is blank on the other side.
Each of the digits from 1 to 9 appears on exactly four cards.
Apart from the numerical values of the digits, the cards are indistinguishable from each other.
Heidi draws four cards from the pack, at random and without replacement. She places the four cards in a row to make a four-digit number. Determine how many different four-digit numbers Heidi could have made in each of the following cases.

1. The four digits are all different.
2. Two of the digits are the same and the other two digits are different.
3. There is no restriction on whether any of the digits are the same or not.

4 A project is represented by the activity network below. The activity durations are given in minutes.
\includegraphics[max width=\textwidth, alt={}, center]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-5_447_1020_392_246}

1. Give the reason for the dummy activity from event (3) to event (4).
2. Complete a forward pass to determine the minimum project completion time.
3. By completing a backward pass, calculate the float for each activity.
4. Determine the effect on the minimum project completion time if the duration of activity A changes from 2 minutes to 3 minutes. The duration of activity C changes to \(m\) minutes, where \(m\) need not be an integer. This reduces the minimum project completion time.
5. By considering the range of possible values of \(m\), determine the minimum project completion time, in terms of \(m\) where necessary.

5 A garden centre sells mixed packs of flower bulbs.
Each pack contains bulbs which produce flowers of two different colours. The cost, in \(\pounds\), of a pack of each colour combination is shown in the table below.

1. Represent the information in the table as a network in which the vertices are the colours and the arcs are the packs available, weighted using the costs.
2. Construct a minimum spanning tree for the network. Taylor wants to buy at most four different packs of bulbs and to ensure that the packs include bulbs capable of producing all four flower colours. Taylor wants to minimise the total cost of these packs.
3. Determine whether or not buying the packs represented by the solution to part (b) solves Taylor's problem.
4. Represent Taylor's problem as an LP formulation, in which the variables are the number of packs of each type.

6 Beth wants to buy some tokens for use in a game.
Each token is either a silver token or a gold token.
Silver tokens and gold tokens have different points values in the game.
Silver tokens have a value of 1.5 points each.
Gold tokens have a value of 4 points each.
Beth already has 2 silver tokens and 1 gold token.
She also has \(\pounds 10\) that can be spent on buying more tokens.
Silver tokens can be bought for \(\pounds 2\) each.
Gold tokens can be bought for \(\pounds 6\) each.
After buying some tokens, Beth has \(x\) silver tokens and \(y\) gold tokens.
She now has a total of at least 5 tokens and no more than 8 tokens.

1. Set up an LP formulation in \(x\) and \(y\) for the problem of maximising the points value of tokens that she finishes with.
2. Use a graphical method to determine how many tokens of each type Beth should buy to maximise the points value of her tokens.

7 Six items need to be packed into bins. Each bin has size \(k\), where \(k\) is an integer. The sizes of the items are
\(\begin{array} { l l l l l l } 8 & 5 & 4 & 7 & 3 & 3 \end{array}\)

1. Show a way to pack the items into two bins of size \(k = 18\).
2. If exactly three bins are needed, determine the possible values of \(k\).
3. Use the first-fit method to pack the items into bins of size 12.
4. Explain why, in general, the first-fit algorithm does not necessarily find the most efficient solution to a packing problem. A possible way to calculate the run-time of the first-fit method is to count for each item the number of bins, excluding full bins, that are considered before the bin where each item is packed. The total count for all packed items is then used to calculate the run-time of the method.
5. Determine the total count for the packing used in part (c). A student says that when \(k = 13\) the total count is 0 because the first bin fills up before the second bin is considered.
6. Explain why the student's argument is not correct.
7. Determine the least possible value of \(k\) for which the total count is 0 . \section*{END OF QUESTION PAPER}