Questions Further Discrete

Browse by module

All questions AEA AS Paper 1 AS Paper 2 AS Pure C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Extra Pure Further Mechanics Further Mechanics A AS Further Mechanics AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics Further Paper 4 Further Pure Core Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Pure with Technology Further Statistics Further Statistics A AS Further Statistics AS Further Statistics B AS Further Statistics Major Further Statistics Minor Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 H240/01 H240/02 H240/03 M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 S1 S2 S3 S4 Unit 1 Unit 2 Unit 3 Unit 4

Browse by board

AQA AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Paper 1 Further Paper 2 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics M1 M2 M3 Paper 1 Paper 2 Paper 3 S1 S2 S3 CAIE FP1 FP2 Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 4 M1 M2 P1 P2 P3 S1 S2 Edexcel AEA AS Paper 1 AS Paper 2 C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 OCR AS Pure C1 C2 C3 C4 D1 D2 FD1 AS FM1 AS FP1 FP1 AS FP2 FP3 FS1 AS Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Mechanics Further Mechanics AS Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Statistics Further Statistics AS H240/01 H240/02 H240/03 M1 M2 M3 M4 PURE S1 S2 S3 S4 OCR MEI AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further Extra Pure Further Mechanics A AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Pure Core Further Pure Core AS Further Pure with Technology Further Statistics A AS Further Statistics B AS Further Statistics Major Further Statistics Minor M1 M2 M3 M4 Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 Pre-U Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 WJEC Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 Unit 1 Unit 2 Unit 3 Unit 4

Sort by: Default | Easiest first | Hardest first

OCR Further Discrete 2018 September Q6

8 marks Standard +0.3

6 Kai mixes hot drinks using coffee and steamed milk.
The amounts ( ml ) needed and profit ( $\pounds$ ) for a standard sized cup of four different drinks are given in the table. The table also shows the amount of the ingredients available.

Type of drink	Coffee	Foamed milk	Profit
w Americano	80	0	1.20
$x$ Cappuccino	60	120	X
$y$ Flat White	60	100	1.40
$z$ Latte	40	120	1.50
Available	900	1500

Kai makes the equivalent of $w$ standard sized americanos, $x$ standard sized cappuccinos, $y$ standard sized flat whites and $z$ standard sized lattes. He can make different sized drinks so $w , x , y , z$ need not be integers. Kai wants to find the maximum profit that he can make, assuming that the customers want to buy the drinks he has made.

What is the minimum value of X for it to be worthwhile for Kai to make cappuccinos? Kai makes no cappuccinos.
Use the simplex algorithm to solve Kai's problem. The grids in the Printed Answer Booklet should have at least enough rows and columns and there should be at least enough grids to show all the iterations needed. Only record the output from each iteration, not any intermediate stages.
Interpret the solution and state the maximum profit that Kai can make.

OCR Further Discrete 2018 September Q7

13 marks Challenging +1.8

7 A simply connected graph has 6 vertices and 10 arcs.

What is the maximum vertex degree? You are now given that the graph is also Eulerian.
Explaining your reasoning carefully, show that exactly two of the vertices have degree 2 .
Prove that the vertices of degree 2 cannot be adjacent to one another.
Use Kuratowski's theorem to show that the graph is planar.
Show that it is possible to make a non-planar graph by the addition of one more arc. A digraph is created from a simply connected graph with 6 vertices and $10 \operatorname { arcs }$ by making each arc into a single directed arc.
What can be deduced about the indegrees and outdegrees?
If a Hamiltonian cycle exists on the digraph, what can be deduced about the indegrees and outdegrees? \section*{OCR} \section*{Oxford Cambridge and RSA}

OCR Further Discrete 2018 December Q1

7 marks Standard +0.8

1 Arif and Bindiya play a game as follows.

They each secretly choose a positive integer from $\{ 2,3,4,5 \}$.
They then reveal their choices. Let Arif's choice be $A$ and Bindiya's choice be $B$.
If $A ^ { B } \geqslant B ^ { A }$, Arif wins $B$ points and Bindiya wins $- 4 - B$ points.
If $A ^ { B } < B ^ { A }$, Arif wins $- 4 - A$ points and Bindiya wins $A$ points.

OCR Further Discrete 2018 December Q2

10 marks Standard +0.3

2 Two simply connected graphs are shown below. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{10ca0bf1-beaa-4460-8f28-08f0e4e44d5c-02_307_584_1151_301} \captionsetup{labelformat=empty} \caption{Graph 1}

\end{figure} \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{10ca0bf1-beaa-4460-8f28-08f0e4e44d5c-02_307_584_1151_1178} \captionsetup{labelformat=empty} \caption{Graph 2}

\end{figure}

1. Write down the orders of the vertices for each of these graphs.
2. How many ways are there to allocate these vertex degrees to a graph with vertices $\mathrm { P } , \mathrm { Q }$, $\mathrm { R } , \mathrm { S } , \mathrm { T }$ and U ?
3. Use the vertex degrees to deduce whether the graphs are Eulerian, semi-Eulerian or neither.
Show that graphs 1 and 2 are not isomorphic.
1. Write down a Hamiltonian cycle for graph 1.
2. Use Euler's formula to determine the number of regions for graph 1.
3. Identify each of these regions for graph 1 by listing the cycle that forms its boundary.

OCR Further Discrete 2018 December Q3

11 marks Easy -1.2

3 A set of ten cards have the following values: $\begin{array} { l l l l l l l l l l } 13 & 8 & 4 & 20 & 12 & 15 & 3 & 2 & 10 & 8 \end{array}$ Kerenza wonders if there is a set of these cards with a total of exactly 50 .

Which type of problem (existence, construction, enumeration or optimisation) is this? The five cards $4,8,8,10$ and 20 have a total of 50.
How many ways are there to arrange three of these five cards (with the two 8 s being indistinguishable) so that the total of the numbers on the first two cards is less than the number on the third card?
How many ways are there to select (choose) three of the five cards so that the total of the numbers on the three cards is less than 25 ?
Show how quicksort works by using it to sort the original list of ten cards into increasing order.
You should indicate the pivots used and which values are already known to be in their correct position.

OCR Further Discrete 2018 December Q4

13 marks Moderate -0.5

4 An algorithm is represented by the flow diagram below. \includegraphics[max width=\textwidth, alt={}, center]{10ca0bf1-beaa-4460-8f28-08f0e4e44d5c-04_1871_1719_293_173} The algorithm is applied with $n = 4$ and the table of inputs $\mathrm { d } ( i , j )$ : $$j = 1 \quad j = 2 \quad j = 3 \quad j = 4$$ $$\begin{aligned} & i = 1 \\ & i = 2 \\ & i = 3 \\ & i = 4 \end{aligned}$$

0	3	5	2
3	0	4	3
5	4	0	1
2	3	1	0

An incomplete trace through the algorithm is shown below.

$n$	$i$	$j$	$\mathrm { d } ( i , j )$	A	$t$	$m$
4
					1
	1
				1		100
		1
			0
		2
			3
					2	3
		3
			5
		4
			2
					4	2
	4
				1, 4		100
		1
			2
		2
			3
					2	3
		3
			1
					3	1
		4
			0

The next box to be used is the box 'Let $i = t$ '.

Complete the trace in the Printed Answer Booklet. The table of inputs represents a weighted matrix for a network, where the weights represent distances.
1. State how the output of the algorithm relates to the network represented by the matrix.
2. How can the list A be used in the solution of the travelling salesperson problem on the network represented by the matrix?
3. Write down a limitation on the distances $\mathrm { d } ( i , j )$ for this algorithm.
Explain why the algorithm is finite for any table of inputs. Suppose that, for a problem with $n$ vertices, the run-time for the algorithm is given by $\alpha D + \beta T$, where $\alpha$ and $\beta$ are constants, $D$ is the number of times that a value of $\mathrm { d } ( i , j )$ is looked up and $T$ is the number of times that $t$ is updated.
Show how this means that the algorithm has $\mathrm { O } \left( n ^ { 2 } \right)$ complexity. A computer takes 3 seconds to run the algorithm for a problem with $n = 35$.
Use the complexity to calculate an approximate run-time for a problem with $n = 100$. The run-time using a second algorithm has $\mathrm { O } ( n ! )$ complexity.
A computer takes 2.8 seconds to run the second algorithm for a problem with $n = 35$.
Without performing any further calculations, give a reason why the first algorithm is likely to be more efficient than the second for a problem with $n = 100$.

OCR Further Discrete 2018 December Q5

12 marks Moderate -0.3

5 A rapid transport system connects 8 stations using three railway lines.
The blue line connects A to B to C to D .

From	to	Travel time
A	B	5
B	C	3
C	D	9

The red line connects $B$ to $F$ to $E$ to $D$.

From	to	Travel time
B	F	2
F	E	3
E	D	2

The green line connects E to G to H to A .

From	to	Travel time
E	G	5
G	H	6
H	A	4

The travel times for the return journeys are the same as for the outward journeys (so, for example, the travel time from B to A is 5 minutes, the same as the time from A to B ).
All travel times include time spent stopped at stations.
No trains are delayed so the travel times are all correct.
Give a reason why the quickest journey from A to D may take longer than 12 minutes.

OCR Further Discrete 2018 December Q6

22 marks Standard +0.3

6 Jack is making pizzas for a party. He can make three types of pizza:

	Suitable for vegans	Suitable for vegetarians	Suitable for meat eaters
Type X			✓
Type Y		✓	✓
Type Z	✓	✓	✓

There is enough dough to make 30 pizzas.
Type Z pizzas use vegan cheese. Jack only has enough vegan cheese to make 2 type Z pizzas.
At least half the pizzas made must be suitable for vegetarians.
Jack has enough onions to make 50 type X pizzas or 20 type Y pizzas or 20 type Z pizzas or some mixture of the three types.

Suppose that Jack makes $x$ type X pizzas, $y$ type Y pizzas and $z$ type Z pizzas.

Formulate the constraints above in terms of the non-negative, integer valued variables $x , y$ and $z$, together with non-negative slack variables $s , t , u$ and $v$. Jack wants to find out the maximum total number of pizzas that he can make.

Set up an initial simplex tableau for Jack's problem.

Carry out one iteration of the simplex algorithm, choosing your pivot so that $x$ becomes a basic variable. When Jack carries out the simplex algorithm his final tableau is:

$P$	$x$	$y$	$z$	$s$	$t$	$u$	$v$	RHS
1	0	0	0	0	0	$\frac { 3 } { 7 }$	$\frac { 2 } { 7 }$	$28 \frac { 4 } { 7 }$
0	0	0	0	1	0	$- \frac { 3 } { 7 }$	$- \frac { 2 } { 7 }$	$1 \frac { 3 } { 7 }$
0	0	0	1	0	1	0	0	2
0	1	0	0	0	0	$\frac { 5 } { 7 }$	$\frac { 1 } { 7 }$	$14 \frac { 2 } { 7 }$
0	0	1	1	0	0	$- \frac { 2 } { 7 }$	$\frac { 1 } { 7 }$	$14 \frac { 2 } { 7 }$

Use this final tableau to deduce how many pizzas of each type Jack should make. Jack knows that some of the guests are vegans. He decides to make 2 pizzas of type $Z$.
1. Plot the feasible region for $x$ and $y$.
2. Complete the branch-and-bound formulation in the Printed Answer Booklet to find the number of pizzas of each type that Jack should make.
  You should branch on $x$ first. \section*{END OF QUESTION PAPER}

OCR Further Discrete 2018 March Q1

6 marks Easy -1.2

The masses, in kg, of ten bags are given below. 8 \quad 10 \quad 10 \quad 12 \quad 12 \quad 12 \quad 13 \quad 15 \quad 18 \quad 18

Use first-fit decreasing to pack the bags into crates that can hold a maximum of 50 kg each. [3]

Only two crates are available, so only some of the bags will be packed. Each bag is given a value.

Bag	A	B	C	D	E	F	G	H	I	J
Mass (kg)	8	10	10	12	12	12	13	15	18	18
Value	6	3	3	2	4	5	4	6	4	4

Find a packing into two crates so that the total value of the bags in the crates is at least 32. [3]

OCR Further Discrete 2018 March Q2

14 marks Challenging +1.2

A linear programming problem is \begin{align} \text{Maximise } P &= 4x - y - 2z
\text{subject to } x + 5y + 3z &\leq 60
2x - 5y &\leq 80
2y + z &\leq 10
x \geq 0, y &\geq 0, z \geq 0 \end{align}

Use the simplex algorithm to solve the problem. [7]

In the case when $z = 0$ the feasible region can be represented graphically. \includegraphics{figure_1} The vertices of the feasible region are $(0, 0)$, $(40, 0)$, $(46.67, 2.67)$, $(35, 5)$ and $(0, 5)$, where non-integer values are given to 2 decimal places. The linear programming problem is given the additional constraint that $x$ and $y$ are integers.

Use branch-and-bound, branching on $x$ first, to show that the optimum solution with this additional constraint is $x = 45, y = 2$. [7]

OCR Further Discrete 2018 March Q3

8 marks Standard +0.8

50 people are at a TV game show. 21 of the 50 are there to take part in the game show and the others are friends who are in the audience, 22 are women and 20 are from London, 2 are women from London who are there to take part in the game show and 15 are men who are not from London and are friends who are in the audience.

Deduce how many of the 50 people are in two of the categories 'there to take part in the game show', 'is a woman' and 'is from London', but are not in all three categories. [3]

The 21 people who are there to take part in the game show are moved to the stage where they are seated in two rows of seats with 20 seats in each row. Some of the seats are empty.

Show how the pigeonhole principle can be used to show that there must be at least one pair of these 21 people with no empty chair between them. [2]

The 21 people are split into three sets of 7. In each round of the game show, three of the people are chosen. The three people must all be from the same set of 7 but once two people have played in the same round they cannot play together in another round. For example, if A plays with B and C in round 1 then A cannot play with B or with C in any other round.

By first considering how many different rounds can be formed using the first set of seven people, deduce how many rounds there can be altogether. [3]

OCR Further Discrete 2018 March Q4

12 marks Challenging +1.3

The graph below connects nine vertices A, B, $\ldots$, H, I. \includegraphics{figure_2}

1. Show that the minimum sum of the degrees of each pair of non-adjacent vertices is 9. [2]
2. Explain what you can deduce from the result in part (a). [1]
Use Kuratowski's theorem to prove that the graph is non-planar. [3]
Prove that there is no subgraph of the graph that is isomorphic to $K_4$, without using subdivision or contraction. [6]

OCR Further Discrete 2018 March Q5

12 marks Standard +0.3

The diagram represents a map of seven locations (A to G) and the direct road distances (km) between some of them. \includegraphics{figure_3} A delivery driver needs to start from his depot at D, make deliveries at each of A, B, F and G, and finish at D.

Write down a route from A to G of length 70 km. [1]

The table shows the length of the shortest path between some pairs of places.

	D	A	B	F	G
D	-
A		-			70
B			-	84
F			84	-
G		70			-

1. Complete the table.
2. Use the nearest neighbour method on the table, starting at D, to find the length of a cycle through D, A, B, F and G, ignoring possibly repeating E and C. [4]
By first considering the table with the row and column for D removed, find a lower bound for the distance that the driver must travel. [2]
What can you conclude from your previous answers about the distance that the driver must travel? [1]

A new road is constructed between D and F. Using this road the driver starts from D, makes the deliveries and returns to D having travelled just 172 km.

Find the length of the new road if
1. the driver does not return to D until all the deliveries have been made,
2. the driver uses the new road twice in making the deliveries. [4]

OCR Further Discrete 2018 March Q6

15 marks Standard +0.3

The activities involved in a project, their durations, immediate predecessors and the number of workers required for each activity are shown in the table.

Activity	Duration (hours)	Immediate predecessors	Number of workers
A	6	-	2
B	4	-	1
C	4	-	1
D	2	A	2
E	3	A, B	1
F	4	C	1
G	3	D	1
H	3	E, F	2

Model the project using an activity network.
Draw a cascade chart for the project, showing each activity starting at its earliest possible start time. [3]
Construct a schedule to show how three workers can complete the project in the minimum possible time. [4]

OCR Further Discrete 2018 March Q7

8 marks Challenging +1.2

Each day Alix and Ben play a game. They each choose a card and use the table below to find the number of points they win. The table shows the cards available to each player. The entries in the cells are of the form $(a, b)$, where $a =$ points won by Alix and $b =$ points won by Ben. Each is trying to maximise the points they win.

	Ben
\cline{2-4} \multicolumn{1}{c}{}	Card X	Card Y	Card Z
\cline{2-4} \multirow{3}{*}{Alix}
Card P	(4, 4)	(5, 9)	(1, 7)
\cline{2-4} Card Q	(3, 5)	(4, 1)	(8, 2)
\cline{2-4} Card R	$(x, y)$	(2, 2)	(9, 4)
\cline{2-4}

Explain why the table cannot be reduced through dominance no matter what values $x$ and $y$ have. [2]
Show that the game is not stable no matter what values $x$ and $y$ have. [2]
Find the Nash equilibrium solutions for the various values that $x$ and $y$ can have. [4]

OCR Further Discrete 2017 Specimen Q1

13 marks Moderate -0.5

Fiona is a mobile hairdresser. One day she needs to visit five clients, A to E, starting and finishing at her own house at F. She wants to find a suitable route that does not involve her driving too far.

Which standard network problem does Fiona need to solve? [1]

The shortest distances between clients, in km, are given in the matrix below.

	A	B	C	D	E
A	-	12	8	6	4
B	12	-	10	8	10
C	8	10	-	13	10
D	6	8	13	-	10
E	4	10	10	10	-

Use the copy of the matrix in the Printed Answer Booklet to construct a minimum spanning tree for these five client locations. State the algorithm you have used, show the order in which you build your tree and give its total weight. Draw your minimum spanning tree. [4]

The distance from Fiona's house to each client, in km, is given in the table below.

	A	B	C	D	E
F	2	11	9	7	5

Use this information together with your answer to part (ii) to find a lower bound for the length of Fiona's route. [2]
1. Find all the cycles that result from using the nearest neighbour method, starting at F. [3]
2. Use these to find an upper bound for the length of Fiona's route. [2]
Fiona wants to drive less than 35 km. Using the information in your answers to parts (iii) and (iv) explain whether or not a route exists which is less than 35 km in length. [1]

OCR Further Discrete 2017 Specimen Q2

13 marks Standard +0.3

Kirstie has bought a house that she is planning to renovate. She has broken the project into a list of activities and constructed an activity network, using activity on arc. \includegraphics{figure_1}

Construct a cascade chart for the project, showing the float for each non-critical activity. [7]
Calculate the float for remodelling the internal layout stating how much of this is independent float and how much is interfering float. [3]

Kirstie needs to supervise the project. This means that she cannot allow more than three activities to happen on any day.

Describe how Kirstie should organise the activities so that the project is completed in the minimum project completion time and no more than three activities happen on any day. [3]

OCR Further Discrete 2017 Specimen Q3

9 marks Standard +0.8

Bob has been given a pile of five letters addressed to five different people. He has also been given a pile of five envelopes addressed to the same five people. Bob puts one letter in each envelope at random.

How many different ways are there to pair the letters with the envelopes? [1]
Find the number of arrangements with exactly three letters in the correct envelopes. [2]
1. Show that there are two derangements of the three symbols A, B and C. [1]
2. Hence find the number of arrangements with exactly two letters in the correct envelopes. [1]

Let $D_n$ represent the number of derangements of $n$ symbols.

Explain why $D_n = (n-1) \times (D_{n-1} + D_{n-2})$. [2]
Find the number of ways in which all five letters are in the wrong envelopes. [2]

OCR Further Discrete 2017 Specimen Q4

11 marks Standard +0.8

The table shows the pay-off matrix for player $A$ in a two-person zero-sum game between $A$ and $B$.

	Player $B$
	Strategy $X$	Strategy $Y$	Strategy $Z$
Player $A$ Strategy $P$	4	5	$-4$
Player $A$ Strategy $Q$	3	$-1$	2
Player $A$ Strategy $R$	4	0	2

Find the play-safe strategy for player $A$ and the play-safe strategy for player $B$. Use the values of the play-safe strategies to determine whether the game is stable or unstable. [3]
If player $B$ knows that player $A$ will use their play-safe strategy, which strategy should player $B$ use? [1]
Suppose that the value in the cell where both players use their play-safe strategies can be changed, but all other entries are unchanged. Show that there is no way to change this value that would make the game stable. [2]
Suppose, instead, that the value in one cell can be changed, but all other entries are unchanged, so that the game becomes stable. Identify a suitable cell and write down a new pay-off value for that cell which would make the game stable. [2]
Show that the zero-sum game with the new pay-off value found in part (iv) has a Nash equilibrium and explain what this means for the players. [3]

OCR Further Discrete 2017 Specimen Q5

13 marks Standard +0.3

A garden centre sells tulip bulbs in mixed packs. The cost of each pack and the number of tulips of each colour are given in the table.

	Cost (£)	Red	White	Yellow	Pink
Pack A	50	25	25	25	25
Pack B	48	40	30	30	0
Pack C	53	20	30	40	10

Dirk is designing a floral display in which he will need the number of red tulips to be at most 50 more than the number of white tulips, and the number of white tulips to be less than or equal to twice the number of pink tulips. He has a budget of £240 and wants to find out which packs to buy to maximise the total number of bulbs. Dirk uses the variables $x$, $y$ and $z$ to represent, respectively, how many of pack A, pack B and pack C he buys. He sets up his problem as an initial simplex tableau, which is shown below.

Initial tableau	$P$	$x$	$y$	$z$	$s$	$t$	$u$	RHS
Row 1	1	$-1$	$-1$	$-1$	0	0	0	0
Row 2	0	0	1	$-1$	1	0	0	5
Row 3	0	$-5$	6	2	0	1	0	0
Row 4	0	50	48	53	0	0	1	240

Show how the constraint on the number of red tulips leads to one of the rows of the tableau. [3]

The tableau that results after the first iteration is shown below.

After first iteration	$P$	$x$	$y$	$z$	$s$	$t$	$u$	RHS
Row 5	1	0	$-0.04$	0.06	0	0	0.02	4.8
Row 6	0	0	1	$-1$	1	0	0	5
Row 7	0	0	10.8	7.3	0	1	0.1	24
Row 8	0	1	0.96	1.06	0	0	0.02	4.8

Which cell was used as the pivot? [1]
Explain why row 2 and row 6 are the same. [1]
1. Read off the values of $x$, $y$ and $z$ after the first iteration. [1]
2. Interpret this solution in terms of the original problem. [2]
Identify the variable that has become non-basic. Use the pivot row of the initial tableau to eliminate $x$ algebraically from the equation represented by Row 1 of the initial tableau. [3]

The feasible region can be represented graphically in three dimensions, with the variables $x$, $y$ and $z$ corresponding to the $x$-axis, $y$-axis and $z$-axis respectively. The boundaries of the feasible region are planes. Pairs of these planes intersect in lines and at the vertices of the feasible region these lines intersect.

The planes defined by each of the new basic variables being set equal to 0 intersect at a point. Show how the equations from part (v) are used to find the values $P$ and $x$ at this point. [2]

OCR Further Discrete 2017 Specimen Q6

16 marks Challenging +1.2

A planar graph $G$ is described by the adjacency matrix below. $$\begin{pmatrix} 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}$$

Draw the graph $G$. [1]
Use Euler's formula to verify that there are four regions. Identify each region by listing the vertices that define it. [3]
Explain why graph $G$ cannot have a Hamiltonian cycle that includes the edge $AB$. Deduce how many Hamiltonian cycles graph $G$ has. [4]

A colouring algorithm is given below. STEP 1: Choose a vertex, colour this vertex using colour 1. STEP 2: If all vertices are coloured, STOP. Otherwise use colour 2 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 1. STEP 3: If all vertices are coloured, STOP. Otherwise use colour 1 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 2. STEP 4: Go back to STEP 2.

Apply this algorithm to graph $G$, starting at $E$. Explain how the colouring shows you that graph $G$ is not bipartite. [2]

By removing just one edge from graph $G$ it is possible to make a bipartite graph.

Identify which edge needs to be removed and write down the two sets of vertices that form the bipartite graph. [2]

Graph $G$ is augmented by the addition of a vertex $X$ joined to each of $A$, $B$, $C$, $D$, $E$ and $F$.

Apply Kuratowski's theorem to a contraction of the augmented graph to explain how you know that the augmented graph has thickness 2. [4]

\(n\)	\(i\)	\(j\)	\(\mathrm { d } ( i , j )\)	A	\(t\)	\(m\)
4
					1
	1
				1		100
		1
			0
		2
			3
					2	3
		3
			5
		4
			2
					4	2
	4
				1, 4		100
		1
			2
		2
			3
					2	3
		3
			1
					3	1
		4
			0

\(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	\(v\)	RHS
1	0	0	0	0	0	\(\frac { 3 } { 7 }\)	\(\frac { 2 } { 7 }\)	\(28 \frac { 4 } { 7 }\)
0	0	0	0	1	0	\(- \frac { 3 } { 7 }\)	\(- \frac { 2 } { 7 }\)	\(1 \frac { 3 } { 7 }\)
0	0	0	1	0	1	0	0	2
0	1	0	0	0	0	\(\frac { 5 } { 7 }\)	\(\frac { 1 } { 7 }\)	\(14 \frac { 2 } { 7 }\)
0	0	1	1	0	0	\(- \frac { 2 } { 7 }\)	\(\frac { 1 } { 7 }\)	\(14 \frac { 2 } { 7 }\)

	Player \(B\)
	Strategy \(X\)	Strategy \(Y\)	Strategy \(Z\)
Player \(A\) Strategy \(P\)	4	5	\(-4\)
Player \(A\) Strategy \(Q\)	3	\(-1\)	2
Player \(A\) Strategy \(R\)	4	0	2

Initial tableau	\(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	RHS
Row 1	1	\(-1\)	\(-1\)	\(-1\)	0	0	0	0
Row 2	0	0	1	\(-1\)	1	0	0	5
Row 3	0	\(-5\)	6	2	0	1	0	0
Row 4	0	50	48	53	0	0	1	240

Questions Further Discrete (71 questions)

Browse by module

Browse by board

OCR Further Discrete 2018 September Q6

OCR Further Discrete 2018 September Q7

OCR Further Discrete 2018 December Q1

OCR Further Discrete 2018 December Q2

OCR Further Discrete 2018 December Q3

OCR Further Discrete 2018 December Q4

OCR Further Discrete 2018 December Q5

OCR Further Discrete 2018 December Q6

OCR Further Discrete 2018 March Q1

OCR Further Discrete 2018 March Q2

OCR Further Discrete 2018 March Q3

OCR Further Discrete 2018 March Q4

OCR Further Discrete 2018 March Q5

OCR Further Discrete 2018 March Q6

OCR Further Discrete 2018 March Q7

OCR Further Discrete 2017 Specimen Q1

OCR Further Discrete 2017 Specimen Q2

OCR Further Discrete 2017 Specimen Q3

OCR Further Discrete 2017 Specimen Q4

OCR Further Discrete 2017 Specimen Q5

OCR Further Discrete 2017 Specimen Q6