Groups

9 The set $C$ consists of the set of all complex numbers excluding 1 and - 1 . The operation ⊕ is defined on the elements of $C$ by $\mathrm { a } \oplus \mathrm { b } = \frac { \mathrm { a } + \mathrm { b } } { \mathrm { ab } + 1 }$ where $\mathrm { a } , \mathrm { b } \in \mathrm { C }$.

Determine the identity element of $C$ under ⊕.
For each element $x$ in $C$ show that it has an inverse element in $C$.
Show that $\oplus$ is associative on $C$.
Explain why $( C , \oplus )$ is not a group.
Find a subset, $D$, of $C$ such that $( D , \oplus )$ is a group of order 3 . \section*{END OF QUESTION PAPER} }{www.ocr.org.uk}) after the live examination series.
If OCR has unwittingly failed to correctly acknowledge or clear any third-party content in this assessment material, OCR will be happy to correct its mistake at the earliest possible opportunity.
For queries or further information please contact The OCR Copyright Team, The Triangle Building, Shaftesbury Road, Cambridge CB2 8EA.
OCR is part of Cambridge University Press \& Assessment, which is itself a department of the University of Cambridge.

View full question →

Subgroups and cosets

A question is this type if and only if it asks to identify, list, or prove properties of subgroups (including proper subgroups, cyclic subgroups, or Lagrange's theorem applications).

18 Challenging +1.4

8.7% of questions

8.03f Subgroups: definition and tests for proper subgroups

Show example »

Let $G$ be a group of order $46 ^ { 46 } + 47 ^ { 47 }$

Using Fermat's Little Theorem and explaining your reasoning, determine which of the following are possible orders for a subgroup of $G$

View full question →

9 The set $S$ consists of the numbers $3 ^ { n }$, where $n \in \mathbb { Z }$. ( $\mathbb { Z }$ denotes the set of integers $\{ 0 , \pm 1 , \pm 2 , \ldots \}$.)

Prove that the elements of $S$, under multiplication, form a commutative group $G$. (You may assume that addition of integers is associative and commutative.)
Determine whether or not each of the following subsets of $S$, under multiplication, forms a subgroup of $G$, justifying your answers.
1. The numbers $3 ^ { 2 n }$, where $n \in \mathbb { Z }$.
2. The numbers $3 ^ { n }$, where $n \in \mathbb { Z }$ and $n \geqslant 0$.
3. The numbers $3 ^ { \left( \pm n ^ { 2 } \right) }$, where $n \in \mathbb { Z }$. 4

View full question →

5 A multiplicative group $G$ of order 9 has distinct elements $p$ and $q$, both of which have order 3 . The group is commutative, the identity element is $e$, and it is given that $q \neq p ^ { 2 }$.

Write down the elements of a proper subgroup of $G$
1. which does not contain $q$,
2. which does not contain $p$.
3. Find the order of each of the elements $p q$ and $p q ^ { 2 }$, justifying your answers.
4. State the possible order(s) of proper subgroups of $G$.
5. Find two proper subgroups of $G$ which are distinct from those in part (i), simplifying the elements.

View full question →

Non-group structures

A question is this type if and only if it asks to show that a given set with an operation does NOT form a group by identifying which axiom(s) fail.

18 Standard +0.4

8.7% of questions

Show example »

1. Write down the pay-off matrix for Bex. 7
(ii) Explain why the pay-off matrix for Bex can be written as

View full question →

Easiest question Easy -2.5 »

1. Write down the pay-off matrix for Bex. 7
(ii) Explain why the pay-off matrix for Bex can be written as

View full question →

5 Alex and Beth play a zero-sum game. Alex chooses a strategy P, Q or R and Beth chooses a strategy $\mathrm { X } , \mathrm { Y }$ or Z . The table shows the number of points won by Alex for each combination of strategies. The entry for cell $( \mathrm { P } , \mathrm { X } )$ is $x$, where $x$ is an integer. \begin{table}[h]

\captionsetup{labelformat=empty} \caption{Beth}

		X	Y	Z
\cline { 3 - 5 }	P	$x$	3	2
\cline { 3 - 5 }	Q	4	0	- 2
\cline { 3 - 5 }	R	- 3	- 1	- 3
\cline { 3 - 5 }
\cline { 3 - 5 }

\end{table} Suppose that P is a play-safe strategy.

1. Determine the values of $x$ for which the game is stable.
2. Determine the values of $x$ for which the game is unstable. The game can be reduced to a $2 \times 3$ game using dominance.
Write down the pay-off matrix for the reduced game. When the game is unstable, Alex plays strategy P with probability $p$.
Determine, as a function of $x$, the value of $p$ for the optimal mixed strategy for Alex. Suppose, instead, that P is not a play-safe strategy and the value of $x$ is - 5 .
Show how to set up a linear programming formulation that could be used to find the optimal mixed strategy for Alex.

View full question →

Isomorphism between groups

A question is this type if and only if it asks to determine whether two groups are isomorphic or to specify an explicit isomorphism between them.

17 Challenging +1.3

8.3% of questions

8.03l Isomorphism: determine using informal methods

Show example »

4 The group $G$ consists of the set $\{ 1,3,7,9,11,13,17,19 \}$ combined under multiplication modulo 20.

Find the inverse of each element.
Show that $G$ is not cyclic.
Find two isomorphic subgroups of order 4 and state an isomorphism between them.

View full question →

9 The group $\left( C , + _ { 4 } \right)$ contains the elements $0,1,2$ and 3 9

1. Show that $C$ is a cyclic group.
  9
  1. (ii) State the group of symmetries of a regular polygon that is isomorphic to $C$ 9
2. The group ( $V , \otimes$ ) contains the elements (1, 1), (1, -1), (-1, 1) and (-1, -1) The binary operation $\otimes$ between elements of $V$ is defined by $$( a , b ) \otimes ( c , d ) = ( a \times c , b \times d )$$ 9
3. 1. Find the element in $V$ that is the inverse of $( - 1,1 )$ Fully justify your answer.
    [0pt] [2 marks]
    9
4. (ii) Determine, with a reason, whether or not $C \cong V$ $\mathbf { 9 }$ (c) The group $G$ has order 16
  Rachel claims that as $1,2,4,8$ and 16 are the only factors of 16 then, by Lagrange's theorem, the group $G$ will have exactly 5 distinct subgroups, including the trivial subgroup and $G$ itself. Comment on the validity of Rachel's claim. \includegraphics[max width=\textwidth, alt={}, center]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-16_2493_1721_214_150}

View full question →

Show that the set $G = \{ 1,3,4,5,9 \}$, under the binary operation of multiplication modulo 11 , is a group. You may assume associativity.
Explain why any two groups of order 5 must be isomorphic to each other. The set $H = \left\{ 1 , \mathrm { e } ^ { \frac { 2 } { 5 } \pi \mathrm { j } } , \mathrm { e } ^ { \frac { 4 } { 5 } \pi \mathrm { j } } , \mathrm { e } ^ { \frac { 6 } { 5 } \pi \mathrm { j } } , \mathrm { e } ^ { \frac { 8 } { 5 } \pi \mathrm { j } } \right\}$ is a group under the binary operation of multiplication of complex numbers.
Specify an isomorphism between the groups $G$ and $H$. The set $K$ consists of the 25 ordered pairs $( x , y )$, where $x$ and $y$ are elements of $G$. The set $K$ is a group under the binary operation defined by $$\left( x _ { 1 } , y _ { 1 } \right) \left( x _ { 2 } , y _ { 2 } \right) = \left( x _ { 1 } x _ { 2 } , y _ { 1 } y _ { 2 } \right)$$ where the multiplications are carried out modulo 11 ; for example, $( 3,5 ) ( 4,4 ) = ( 1,9 )$.
Write down the identity element of $K$, and find the inverse of the element $( 9,3 )$.
Explain why $( x , y ) ^ { 5 } = ( 1,1 )$ for every element $( x , y )$ in $K$.
Deduce that all the elements of $K$, except for one, have order 5. State which is the exceptional element.
A subgroup of $K$ has order 5 and contains the element (9, 3). List the elements of this subgroup.
Determine how many subgroups of $K$ there are with order 5 .

View full question →

Complete or analyse Cayley table

A question is this type if and only if it requires completing a composition/Cayley table for a group or using such a table to deduce group properties.

16 Standard +0.5

7.8% of questions

8.03c Group definition: recall and use, show structure is/isn't a group

Show example »

The set $S$ is given by $S = \{0, 2, 4, 6\}$

Construct a Cayley table, using the grid below, for $S$ under the binary operation addition modulo 8 [3 marks] \includegraphics{figure_2}
State the identity element for $S$ under the binary operation addition modulo 8 [1 mark]

View full question →

Easiest question Easy -1.2 »

The set $S$ is given by $S = \{0, 2, 4, 6\}$

Construct a Cayley table, using the grid below, for $S$ under the binary operation addition modulo 8 [3 marks] \includegraphics{figure_2}
State the identity element for $S$ under the binary operation addition modulo 8 [1 mark]

View full question →

$T$ is the set $\{1, 2, 3, 4\}$. A binary operation $\bullet$ is defined on $T$ such that $a \bullet a = 2$ for all $a \in T$. It is given that $(T, \bullet)$ is a group.

Deduce the identity element in $T$, giving a reason for your answer. [2]
Find the value of $1 \bullet 3$, showing how the result is obtained. [3]
1. Complete a group table for $(T, \bullet)$. [2]
2. State with a reason whether the group is abelian. [1]

View full question →

Prove group-theoretic identities

A question is this type if and only if it asks to prove general algebraic identities or properties involving group elements, inverses, or powers (e.g., prove (xy)⁻¹ = y⁻¹x⁻¹).

15 Challenging +1.3

7.3% of questions

Show example »

The binary operation $*$ is defined as $$a * b = ab + 1 \quad \text{where } a, b \in \mathbb{R}$$

Prove that $*$ is commutative on $\mathbb{R}$ [2 marks]
Prove that $*$ is not associative on $\mathbb{R}$ [3 marks]

View full question →

1. The table below is a Cayley table for the group $G$ with operation ∘

。	$a$	$b$	$c$	$d$	$e$	$f$
$a$	$d$	c	$b$	$a$	$f$	$e$
$b$	$e$	$f$	$a$	$b$	$c$	$d$
$c$	$f$	$e$	$d$	$c$	$b$	$a$
$d$	$a$	$b$	$c$	$d$	$e$	$f$
$e$	$b$	$a$	$f$	$e$	$d$	$c$
$f$	c	$d$	$e$	$f$	$a$	$b$

State which element is the identity of the group.
Determine the inverse of the element ( $b \circ c$ )
Give a reason why the set $\{ a , b , e , f \}$ cannot be a subgroup of $G$. You must justify your answer.
Show that the set $\{ b , d , f \}$ is a subgroup of $G$.
(ii) Given that $H$ is a group with an element $x$ of order 3 and an element $y$ of order 6 satisfying $$y x = x y ^ { 5 }$$ show that $y ^ { 3 } x y ^ { 3 } x ^ { 2 }$ is the identity element. \includegraphics[max width=\textwidth, alt={}, center]{7d269bf1-f481-46bd-b9d3-fea211b186cf-02_2270_54_309_1980}

View full question →

Hardest question Hard +2.3 »

Explain why all groups of even order must contain at least one self-inverse element (that is, an element of order 2).
Prove that any group in which every non-identity element is self-inverse is abelian.
Simon believes that if $x$ and $y$ are two distinct self-inverse elements of a group, then the element $x y$ is also self-inverse. By considering the group of the six permutations of $\left( \begin{array} { l l } 1 & 2 \end{array} \right)$, produce a counter-example to prove him wrong.
A group $G$ has order $4 n + 2$, for some positive integer $n$, and $i$ is the identity element of $G$. Let $x$ and $y$ be two distinct self-inverse elements of $G$. By considering the set $H = \{ i , x , y , x y \}$, prove by contradiction that $G$ cannot contain all self-inverse elements.

View full question →

Matrix groups

A question is this type if and only if the group consists of matrices under matrix multiplication and requires operations with or analysis of these matrices.

13 Challenging +1.4

6.3% of questions

8.03a Binary operations: and their properties on given sets 8.03b Cayley tables: construct for finite sets under binary operation

Show example »

Consider the set $S$ of all matrices of the form $\begin{pmatrix} p & p \\ p & p \end{pmatrix}$, where $p$ is a non-zero rational number.

Show that $S$, under the operation of matrix multiplication, forms a group, $G$. [5]
Find a subgroup of $G$ of order 2 and show that $G$ contains no subgroups of order 3. [4]

View full question →

5 A local hockey league has three divisions. Each team in the league plays in a division for a year. In the following year a team might play in the same division again, or it might move up or down one division. This question is about the progress of one particular team in the league. In 2007 this team will be playing in either Division 1 or Division 2. Because of its present position, the probability that it will be playing in Division 1 is 0.6 , and the probability that it will be playing in Division 2 is 0.4 . The following transition probabilities apply to this team from 2007 onwards.

(a) Given $\mathbf { A } = \left( \begin{array} { l l } a & b \\ c & d \end{array} \right)$ and $\mathbf { B } = \left( \begin{array} { l l } e & f \\ g & h \end{array} \right)$, work out the matrix $\mathbf { A B }$ and write down expressions for $\operatorname { det } \mathbf { A }$ and $\operatorname { det } \mathbf { B }$.
(b) Verify, by direct calculation, that $\operatorname { det } ( \mathbf { A B } ) = \operatorname { det } \mathbf { A } \times \operatorname { det } \mathbf { B }$. Let $S$ be the set of all $2 \times 2$ matrices with determinant equal to 1 .
Show that $\left( S , \times _ { \mathrm { M } } \right)$ forms a group, $G$, where $\times _ { \mathrm { M } }$ is the operation of matrix multiplication. [You may assume that $\mathrm { X } _ { \mathrm { M } }$ is associative.]
(a) Show that $\mathbf { K } = \left( \begin{array} { l l } 1 & \mathrm { i } \\ \mathrm { i } & 0 \end{array} \right)$ is an element of $G$. Let $H$ be the smallest subgroup of $G$ that contains $\mathbf { K }$ and let $n$ be the order of $H$.
(b) Determine the value of $n$.
(c) Give a second subgroup of $G$, also of order $n$, which is isomorphic to $H$.

View full question →

Hardest question Hard +2.3 »

A class of students is set the task of finding a group of functions, under composition of functions, of order 6. Student P suggests that this can be achieved by finding a function $f$ for which $f^6(x) = x$ and using this as a generator for the group.

Explain why the suggestion by Student P might not work. [2]

Student Q observes that their class has already found a group of order 6 in a previous task; a group consisting of the powers of a particular, non-singular $2 \times 2$ real matrix $\mathbf{M} = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$, under the operation of matrix multiplication.

Explain why such a group is only possible if $\det(\mathbf{M}) = 1$ or $-1$. [2]
Write down values of $a$, $b$, $c$ and $d$ that would give a suitable matrix $\mathbf{M}$ for which $\mathbf{M}^6 = \mathbf{I}$ and $\det(\mathbf{M}) = 1$. [1]

Student Q believes that it is possible to construct a rational function $f$ in the form $f(x) = \frac{ax + b}{cx + d}$ so that the group of functions is isomorphic to the matrix group which is generated by the matrix $\mathbf{M}$ of part (iii).

1. Write down and simplify the function $f$ that, according to Student Q, corresponds to $\mathbf{M}$. [1]
2. By calculating $\mathbf{M}^2$, show that Student Q's suggestion does not work. [2]
3. Find a different function $f$ that will satisfy the requirements of the task. [4]

View full question →

Groups of symmetries

A question is this type if and only if it involves groups defined by geometric symmetries (reflections, rotations) of shapes such as squares, triangles, or pentagons.

5 Standard +1.0

2.4% of questions

8.03b Cayley tables: construct for finite sets under binary operation 8.03f Subgroups: definition and tests for proper subgroups

Show example »

4 The group $G$ consists of the symmetries of the equilateral triangle $A B C$ under the operation of composition of transformations (which may be assumed to be associative). Three elements of $G$ are

$\boldsymbol { i }$, the identity
$\boldsymbol { j }$, the reflection in the vertical line of symmetry of the triangle
$\boldsymbol { k }$, the anticlockwise rotation of $120 ^ { \circ }$ about the centre of the triangle.

These are shown in the diagram below. \includegraphics[max width=\textwidth, alt={}, center]{0b4458dc-4f82-40e4-adcf-cbffca088389-3_204_531_735_772} \includegraphics[max width=\textwidth, alt={}, center]{0b4458dc-4f82-40e4-adcf-cbffca088389-3_211_543_975_762} \includegraphics[max width=\textwidth, alt={}, center]{0b4458dc-4f82-40e4-adcf-cbffca088389-3_216_543_1215_762}

Explain why the order of $G$ is 6 .
Determine
- the order of $\boldsymbol { j }$,
- the order of $\boldsymbol { k }$.
- - Express, in terms of $\boldsymbol { j }$ and/or $\boldsymbol { k }$, each of the remaining three elements of $G$.
- Draw a diagram for each of these elements.
- Is the operation of composition of transformations on $G$ commutative? Justify your answer.
- List all the proper subgroups of $G$.

View full question →

Order of elements and cyclic structure

Questions asking to find or determine the order of specific elements, whether the group is cyclic, or which elements generate the group.

5 Standard +0.8

2.4% of questions

8.03a Binary operations: and their properties on given sets 8.03g Cyclic groups: meaning of the term

Show example »

7 A commutative group $G$ has order 18. The elements $a , b$ and $c$ have orders 2, 3 and 9 respectively.

Prove that $a b$ has order 6 .
Show that $G$ is cyclic.

View full question →

Proper subgroups identification

Questions asking to identify, list, or determine properties of proper subgroups of a given group, including applying Lagrange's theorem to constrain possible subgroup orders.

4 Challenging +1.3

1.9% of questions

8.03b Cayley tables: construct for finite sets under binary operation 8.03g Cyclic groups: meaning of the term

Show example »

The set $G = \{ 1,3,7,9,11,13,17,19 \}$ under the binary operation of multiplication modulo 20 forms a group.
1. Find the inverse of each element of $G$.
2. Find the order of each element of $G$.
3. Find a subgroup of $G$ of order 4
4. Explain how the subgroup you found in part (c) satisfies Lagrange's theorem.

View full question →

Groups with generators and relations

A question is this type if and only if the group is defined by generators with specific relations (e.g., aⁿ = e, ba = aᵏb) and requires deducing consequences or completing operation tables.

3 Challenging +1.4

1.5% of questions

8.03a Binary operations: and their properties on given sets 8.03f Subgroups: definition and tests for proper subgroups

Show example »

8 A multiplicative group $Q$ of order 8 has elements $\left\{ e , p , p ^ { 2 } , p ^ { 3 } , a , a p , a p ^ { 2 } , a p ^ { 3 } \right\}$, where $e$ is the identity. The elements have the properties $p ^ { 4 } = e$ and $a ^ { 2 } = p ^ { 2 } = ( a p ) ^ { 2 }$.

Prove that $a = p a p$ and that $p = a p a$.
Find the order of each of the elements $p ^ { 2 } , a , a p , a p ^ { 2 }$.
Prove that $\left\{ e , a , p ^ { 2 } , a p ^ { 2 } \right\}$ is a subgroup of $Q$.
Determine whether $Q$ is a commutative group.

View full question →

Function composition groups

A question is this type if and only if the group consists of functions under composition and requires computing compositions or analysing the group structure.

2 Challenging +1.5

1.0% of questions

Show example »

The function f is defined by $\text{f} : x \mapsto \frac{1}{2-2x}$ for $x \in \mathbb{R}, x \neq 0, x \neq \frac{1}{2}, x \neq 1$. The function g is defined by $\text{g}(x) = \text{ff}(x)$.

Show that $\text{g}(x) = \frac{1-x}{1-2x}$ and that $\text{gg}(x) = x$. [4]

It is given that f and g are elements of a group $K$ under the operation of composition of functions. The element e is the identity, where $\text{e} : x \mapsto x$ for $x \in \mathbb{R}, x \neq 0, x \neq \frac{1}{2}, x \neq 1$.

State the orders of the elements f and g. [2]
The inverse of the element f is denoted by h. Find $\text{h}(x)$. [2]
Construct the operation table for the elements e, f, g, h of the group $K$. [4]

View full question →

Order of elements

A question is this type if and only if it asks to find or prove the order of specific elements in a group.

2 Challenging +1.3

1.0% of questions

Show example »

2 The elements of a group $G$ are the complex numbers $a + b \mathrm { i }$ where $a , b \in \{ 0,1,2,3,4 \}$. These elements are combined under the operation of addition modulo 5 .

State the identity element and the order of $G$.
Write down the inverse of $2 + 4 \mathrm { i }$.
Show that every non-zero element of $G$ has order 5 .

View full question →

Commutativity and group classification

Questions asking whether a group is abelian/commutative, or to classify/identify the type of group (e.g., distinguishing between groups of the same order).

2 Challenging +1.3

1.0% of questions

Show example »

1 In this question $G$ is a group of order $n$, where $3 \leqslant n < 8$.

In each case, write down the smallest possible value of $n$ :
1. if $G$ is cyclic,
2. if $G$ has a proper subgroup of order 3,
3. if $G$ has at least two elements of order 2 .
4. Another group has the same order as $G$, but is not isomorphic to $G$. Write down the possible value(s) of $n$.

View full question →

Unclassified

Questions not yet assigned to a type.

26.2% of questions

Show 54 unclassified »

When the team is playing in Division 1, the probability that it will play in Division 2 in the following year is 0.2 .
When the team is playing in Division 2, the probability that it will play in Division 1 in the following year is 0.1 , and the probability that it will play in Division 3 in the following year is 0.3 .
When the team is playing in Division 3, the probability that it will play in Division 2 in the following year is 0.15 .

This process is modelled as a Markov chain with three states corresponding to the three divisions.

Write down the transition matrix.
Determine in which division the team is most likely to be playing in 2014.
Find the equilibrium probabilities for each division for this team. In 2015 the rules of the league are changed. A team playing in Division 3 might now be dropped from the league in the following year. Once dropped, a team does not play in the league again.
-The transition probabilities from Divisions 1 and 2 remain the same as before.
- When the team is playing in Division 3, the probability that it will play in Division 2 in the following year is 0.15 , and the probability that it will be dropped from the league is 0.1 .
The team plays in Division 2 in 2015.
The new situation is modelled as a Markov chain with four states: 'Division1', 'Division 2', 'Division 3' and 'Out of league'.
Write down the transition matrix which applies from 2015.
Find the probability that the team is still playing in the league in 2020.
Find the first year for which the probability that the team is out of the league is greater than 0.5 .

5 In this question, give probabilities correct to 4 decimal places.
A contestant in a game-show starts with one, two or three 'lives', and then performs a series of tasks. After each task, the number of lives either decreases by one, or remains the same, or increases by one. The game ends when the number of lives becomes either four or zero. If the number of lives is four, the contestant wins a prize; if the number of lives is zero, the contestant loses and leaves with nothing. At the start, the number of lives is decided at random, so that the contestant is equally likely to start with one, two or three lives. The tasks do not involve any skill, and after every task:

the probability that the number of lives decreases by one is 0.5 ,
the probability that the number of lives remains the same is 0.05 ,
the probability that the number of lives increases by one is 0.45 .

This is modelled as a Markov chain with five states corresponding to the possible numbers of lives. The states corresponding to zero lives and four lives are absorbing states.

Write down the transition matrix $\mathbf { P }$.
Show that, after 8 tasks, the probability that the contestant has three lives is 0.0207 , correct to 4 decimal places.
Find the probability that, after 10 tasks, the game has not yet ended.
Find the probability that the game ends after exactly 10 tasks.
Find the smallest value of $N$ for which the probability that the game has not yet ended after $N$ tasks is less than 0.01 .
Find the limit of $\mathbf { P } ^ { n }$ as $n$ tends to infinity.
Find the probability that the contestant wins a prize. The beginning of the game is now changed, so that the probabilities of starting with one, two or three lives can be adjusted.
State the maximum possible probability that the contestant wins a prize, and how this can be achieved.
Given that the probability of starting with one life is 0.1 , and the probability of winning a prize is 0.6 , find the probabilities of starting with two lives and starting with three lives. }{www.ocr.org.uk}) after the live examination series.
If OCR has unwittingly failed to correctly acknowledge or clear any third-party content in this assessment material, OCR will be happy to correct its mistake at the earliest possible opportunity.
For queries or further information please contact the Copyright Team, First Floor, 9 Hills Road, Cambridge CB2 1GE.
OCR is part of the

5 In this question, give probabilities correct to 4 decimal places.
The speeds of vehicles are measured on a busy stretch of road and are categorised as A (not more than 30 mph ), B (more than 30 mph but not more than 40 mph ) or C (more than 40 mph ).

Following a vehicle in category A , the probabilities that the next vehicle is in categories $\mathrm { A } , \mathrm { B } , \mathrm { C }$ are $0.9,0.07,0.03$ respectively.
Following a vehicle in category B , the probabilities that the next vehicle is in categories $\mathrm { A } , \mathrm { B } , \mathrm { C }$ are $0.3,0.6,0.1$ respectively.
Following a vehicle in category C , the probabilities that the next vehicle is in categories $\mathrm { A } , \mathrm { B } , \mathrm { C }$ are $0.1,0.7,0.2$ respectively.

This is modelled as a Markov chain with three states corresponding to the categories A, B, C. The speed of the first vehicle is measured as 28 mph .

Write down the transition matrix $\mathbf { P }$.
Find the probabilities that the 10th vehicle is in each of the three categories.
Find the probability that the 12th and 13th vehicles are in the same category.
Find the smallest value of $n$ for which the probability that the $n$th and $( n + 1 )$ th vehicles are in the same category is less than 0.8, and give the value of this probability.
Find the expected number of vehicles (including the first vehicle) in category A before a vehicle in a different category.
Find the limit of $\mathbf { P } ^ { n }$ as $n$ tends to infinity, and hence write down the equilibrium probabilities for the three categories.
Find the probability that, after many vehicles have passed by, the next three vehicles are all in category A. On a new stretch of road, the same categories are used but some of the transition probabilities are different.
- Following a vehicle in category A , the probability that the next vehicle is in category B is equal to the probability that it is in category C .
- Following a vehicle in category B , the probability that the next vehicle is in category A is equal to the probability that it is in category C .
- Following a vehicle in category C , the probabilities that the next vehicle is in categories $\mathrm { A } , \mathrm { B } , \mathrm { C }$ are $0.1,0.7,0.2$ respectively.
In the long run, the proportions of vehicles in categories A, B, C are 50\%, 40\%, 10\% respectively.
Find the transition matrix for the new stretch of road.

5 Each level of a fantasy computer game is set in a single location, Alphaworld, Betaworld, Chiworld or Deltaworld. After completing a level, a player goes on to the next level, which could be set in the same location as the previous level, or in a different location. In the first version of the game, the initial and transition probabilities are as follows.
Level 1 is set in Alphaworld or Betaworld, with probabilities 0.6, 0.4 respectively.
After a level set in Alphaworld, the next level will be set in Betaworld, Chiworld or Deltaworld, with probabilities $0.7,0.1,0.2$ respectively.
After a level set in Betaworld, the next level will be set in Alphaworld, Betaworld or Deltaworld, with probabilities $0.1,0.8,0.1$ respectively.
After a level set in Chiworld, the next level will also be set in Chiworld.
After a level set in Deltaworld, the next level will be set in Alphaworld, Betaworld or Chiworld, with probabilities $0.3,0.6,0.1$ respectively. The situation is modelled as a Markov chain with four states.

Write down the transition matrix.
Find the probabilities that level 14 is set in each location.
Find the probability that level 15 is set in the same location as level 14 .
Find the level at which the probability of being set in Chiworld first exceeds 0.5.
Following a level set in Betaworld, find the expected number of further levels which will be set in Betaworld before changing to a different location. In the second version of the game, the initial probabilities and the transition probabilities after Alphaworld, Betaworld and Deltaworld are all the same as in the first version; but after a level set in Chiworld, the next level will be set in Chiworld or Deltaworld, with probabilities $0.9,0.1$ respectively.
By considering powers of the new transition matrix, or otherwise, find the equilibrium probabilities for the four locations. In the third version of the game, the initial probabilities and the transition probabilities after Alphaworld, Betaworld and Deltaworld are again all the same as in the first version; but the transition probabilities after Chiworld have changed again. The equilibrium probabilities for Alphaworld, Betaworld, Chiworld and Deltaworld are now 0.11, 0.75, 0.04, 0.1 respectively.
Find the new transition probabilities after a level set in Chiworld. }{www.ocr.org.uk}) after the live examination series.
If OCR has unwittingly failed to correctly acknowledge or clear any third-party content in this assessment material, OCR will be happy to correct its mistake at the earliest possible opportunity. For queries or further information please contact the Copyright Team, First Floor, 9 Hills Road, Cambridge CB2 1PB.
OCR is part of the

Let $V$ be the subspace of $\mathbb { R } ^ { 4 }$ spanned by $$\mathbf { v } _ { 1 } = \left( \begin{array} { l } 1 \\ 2 \\ 0 \\ 2 \end{array} \right) , \quad \mathbf { v } _ { 2 } = \left( \begin{array} { r } - 2 \\ - 5 \\ 5 \\ 6 \end{array} \right) , \quad \mathbf { v } _ { 3 } = \left( \begin{array} { r } 0 \\ - 3 \\ 15 \\ 18 \end{array} \right) \quad \text { and } \quad \mathbf { v } _ { 4 } = \left( \begin{array} { r } 0 \\ - 2 \\ 10 \\ 8 \end{array} \right) .$$

Show that the dimension of $V$ is 3 . $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$
Express $\mathbf { v } _ { 4 }$ as a linear combination of $\mathbf { v } _ { 1 } , \mathbf { v } _ { 2 }$ and $\mathbf { v } _ { 3 }$. $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$
Write down a basis for $V$. $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ Let $\mathbf { M } = \left( \begin{array} { r r r r } 1 & - 2 & 0 & 0 \\ 2 & - 5 & - 3 & - 2 \\ 0 & 5 & 15 & 10 \\ 2 & 6 & 18 & 8 \end{array} \right)$.
Find the general solution of $\mathbf { M x } = \mathbf { v } _ { 1 } + \mathbf { v } _ { 2 }$. $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ The set of elements of $\mathbb { R } ^ { 4 }$ which are not solutions of $\mathbf { M x } = \mathbf { v } _ { 1 } + \mathbf { v } _ { 2 }$ is denoted by $W$.
State, with a reason, whether $W$ is a vector space. $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$ $\_\_\_\_$

10 The vectors $\mathbf { b } _ { 1 } , \mathbf { b } _ { 2 } , \mathbf { b } _ { 3 } , \mathbf { b } _ { 4 }$ are defined as follows: $$\mathbf { b } _ { 1 } = \left( \begin{array} { c } 1 \\ 0 \\ 0 \\ 0 \end{array} \right) , \quad \mathbf { b } _ { 2 } = \left( \begin{array} { c } 1 \\ 1 \\ 0 \\ 0 \end{array} \right) , \quad \mathbf { b } _ { 3 } = \left( \begin{array} { c } 1 \\ 1 \\ 1 \\ 0 \end{array} \right) , \quad \mathbf { b } _ { 4 } = \left( \begin{array} { c } 1 \\ 1 \\ 1 \\ 1 \end{array} \right) .$$ The linear space spanned by $\mathbf { b } _ { 1 } , \mathbf { b } _ { 2 } , \mathbf { b } _ { 3 }$ is denoted by $V _ { 1 }$ and the linear space spanned by $\mathbf { b } _ { 1 } , \mathbf { b } _ { 2 } , \mathbf { b } _ { 4 }$ is denoted by $V _ { 2 }$.

Give a reason why $V _ { 1 } \cup V _ { 2 }$ is not a linear space.
State the dimension of the linear space $V _ { 1 } \cap V _ { 2 }$ and write down a basis. Consider now the set $V _ { 3 }$ of all vectors of the form $q \mathbf { b } _ { 2 } + r \mathbf { b } _ { 3 } + s \mathbf { b } _ { 4 }$, where $q , r , s$ are real numbers. Show that $V _ { 3 }$ is a linear space, and show also that it has dimension 3 . Determine whether each of the vectors $$\left( \begin{array} { l } 4 \\ 4 \\ 2 \\ 5 \end{array} \right) \quad \text { and } \quad \left( \begin{array} { l } 5 \\ 4 \\ 2 \\ 5 \end{array} \right)$$ belongs to $V _ { 3 }$ and justify your conclusions.

5 Each day that Adam is at work he carries out one of three tasks A, B or C. Each task takes a whole day. Adam chooses the task to carry out on each day according to the following set of three rules.

If, on any given day, he has worked on task A then the next day he will choose task A with probability 0.75 , and tasks B and C with equal probability.
If, on any given day, he has worked on task B then the next day he will choose task B or task C with equal probability but will never choose task A .
If, on any given day, he has worked on task C then the next day he will choose task A with probability $p$ and tasks B and C with equal probability.
1. Write down the transition matrix.
2. Over a long period Adam carries out the tasks $\mathrm { A } , \mathrm { B }$ and C with equal frequency. Find the value of $p$.
3. On day 1 Adam chooses task A . Find the probability that he also chooses task A on day 5 .
Adam decides to change rule 3 as follows.
If, on any given day, he has worked on task C then the next day he will choose tasks $\mathrm { A } , \mathrm { B } , \mathrm { C }$ with probabilities $0.4,0.3,0.3$ respectively.
On day 1 Adam chooses task A. Find the probability that he chooses the same task on day 7 as he did on day 4 .
On a particular day, Adam chooses task A. Find the expected number of consecutive further days on which he will choose A. Adam changes all three rules again as follows.
- If he works on A one day then on the next day he chooses C .
- If he works on B one day then on the next day he chooses A or C each with probability 0.5.
- If he works on C one day then on the next day he chooses A or B each with probability 0.5 .
- Find the long term probabilities for each task.

3 Two people, Rhona and Colleen, play a zero-sum game. The game is represented by the following pay-off matrix for Rhona.


\cline { 2 - 5 }	Colleen
\cline { 2 - 5 } Strategy	$\mathbf { C } _ { \mathbf { 1 } }$	$\mathbf { C } _ { \mathbf { 2 } }$	$\mathbf { C } _ { \mathbf { 3 } }$
\cline { 2 - 5 } Rhona	$\mathbf { R } _ { \mathbf { 1 } }$	2	6	4
\cline { 2 - 5 }	$\mathbf { R } _ { \mathbf { 2 } }$	3	- 3	- 1
\cline { 2 - 5 }	$\mathbf { R } _ { \mathbf { 3 } }$	$x$	$x + 3$	3
\cline { 2 - 5 }
\cline { 2 - 5 }

It is given that $x < 2$.

1. Write down the three row minima.
2. Show that there is no stable solution.
Explain why Rhona should never play strategy $R _ { 3 }$.
1. Find the optimal mixed strategy for Rhona.
2. Find the value of the game.

3 Two people, Roz and Colum, play a zero-sum game. The game is represented by the following pay-off matrix for Roz.

Colum
\cline { 2 - 5 }	Strategy	$\mathbf { C } _ { \mathbf { 1 } }$	$\mathbf { C } _ { \mathbf { 2 } }$	$\mathbf { C } _ { \mathbf { 3 } }$
\multirow{3}{*}{$\operatorname { Roz }$}	$\mathbf { R } _ { \mathbf { 1 } }$	- 2	- 6	- 1
\cline { 2 - 5 }	$\mathbf { R } _ { \mathbf { 2 } }$	- 5	2	- 6
\cline { 2 - 5 }	$\mathbf { R } _ { \mathbf { 3 } }$	- 3	3	- 4

Explain what is meant by the term 'zero-sum game'.
Determine the play-safe strategy for Colum, giving a reason for your answer.
1. Show that the matrix can be reduced to a 2 by 3 matrix, giving the reason for deleting one of the rows.
2. Hence find the optimal mixed strategy for Roz.

2 Harry and Will play a zero-sum game. The game is represented by the following pay-off matrix for Harry.

	Will
\cline { 2 - 6 }	Strategy	$\boldsymbol { D }$	$\boldsymbol { E }$	$\boldsymbol { F }$	$\boldsymbol { G }$
Harry	$\boldsymbol { A }$	- 1	2	3
\cline { 2 - 6 }	$\boldsymbol { B }$	4	6	3	7
\cline { 2 - 6 }	$\boldsymbol { C }$	1	3	- 2	4

Show that this game has a stable solution and state the play-safe strategy for each player.
List any saddle points.

6 Kate and Pippa play a zero-sum game. The game is represented by the following pay-off matrix for Kate. \includegraphics[max width=\textwidth, alt={}, center]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-18_2482_1707_223_155}

4 Two people, Roger and Corrie, play a zero-sum game.
The game is represented by the following pay-off matrix for Roger.

	Corrie
\cline { 2 - 5 }	Strategy	$\mathbf { C } _ { \mathbf { 1 } }$	$\mathbf { C } _ { \mathbf { 2 } }$	$\mathbf { C } _ { \mathbf { 3 } }$
\cline { 2 - 5 } Roger	$\mathbf { R } _ { \mathbf { 1 } }$	7	3	- 5
\cline { 2 - 5 }	$\mathbf { R } _ { \mathbf { 2 } }$	- 2	- 1	4
\cline { 2 - 5 }
\cline { 2 - 5 }

1. Find the optimal mixed strategy for Roger.
2. Show that the value of the game is $\frac { 7 } { 13 }$.
Given that the value of the game is $\frac { 7 } { 13 }$, find the optimal mixed strategy for Corrie.
\includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-09_2484_1709_223_153}

Two people, Tom and Jerry, play a zero-sum game. The game is represented by the following pay-off matrix for Tom.
Jerry
\cline { 2 - 5 } Strategy A B C
Tom I - 4 5 - 3
\cline { 2 - 5 } II - 3 - 2 8
\cline { 2 - 5 } III - 7 6 - 2
Show that this game has a stable solution and state the play-safe strategy for each player.

Rohan and Carla play a different zero-sum game for which there is no stable solution. The game is represented by the following pay-off matrix for Rohan. \begin{table}[h]

\captionsetup{labelformat=empty} \caption{Carla} Rohan

Strategy	$\mathbf { C } _ { \mathbf { 1 } }$	$\mathbf { C } _ { \mathbf { 2 } }$	$\mathbf { C } _ { \mathbf { 3 } }$
$\mathbf { R } _ { \mathbf { 1 } }$	3	5	- 1
$\mathbf { R } _ { \mathbf { 2 } }$	1	- 2	4

5 Romeo and Juliet play a zero-sum game. The game is represented by the following pay-off matrix for Romeo.

Find the optimal mixed strategy for Rohan and show that the value of the game is $\frac { 3 } { 2 }$.
Carla plays strategy $\mathrm { C } _ { 1 }$ with probability $p$, and strategy $\mathrm { C } _ { 2 }$ with probability $q$. Find the values of $p$ and $q$ and hence find the optimal mixed strategy for Carla.
(4 marks)

\includegraphics[max width=\textwidth, alt={}]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-10_2486_1714_221_153}

\includegraphics[max width=\textwidth, alt={}]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-11_2486_1714_221_153}

	Juliet
\cline { 2 - 5 }	Strategy	D	E	F
A	4	- 4	0
\cline { 2 - 5 } Romeo	B	- 2	- 5	3
\cline { 2 - 5 }	C	2	1	- 2
\cline { 2 - 5 }
\cline { 2 - 5 }

Find the play-safe strategy for each player.
Show that there is no stable solution.
Explain why Juliet should never play strategy D.
1. Explain why the following is a suitable pay-off matrix for Juliet.
  4 5 - 1
  0 - 3 2
2. Hence find the optimal strategy for Juliet.
3. Find the value of the game for Juliet.

5. A two-person zero-sum game is represented by the following pay-off matrix for player A.

	B plays 1	B plays 2	B plays 3	B plays 4
A plays 1	- 2	1	3	- 1
A plays 2	- 1	3	2	1
A plays 3	- 4	2	0	- 1
A plays 4	1	- 2	- 1	3

Verify that there is no stable solution to this game.
Explain why the $4 \times 4$ game above may be reduced to the following $3 \times 3$ game.
Formulate the $3 \times 3$ game as a linear programming problem for player A. Write the
- 2 1 3
- 1 3 2
1 - 2 - 1
constraints as inequalities. Define your variables clearly.

2. A two-person zero-sum game is represented by the following pay-off matrix for player $A$.

		$B$
		I	II	III	IV
\multirow{3}{*}{$A$}	I	- 4	- 5	- 2	4
	II	- 1	1	- 1	2
	III	0	5	- 2	- 4
	IV	- 1	3	- 1	1

Determine the play-safe strategy for each player.
Verify that there is a stable solution and determine the saddle points.
State the value of the game to $B$.

4. Andrew ( $A$ ) and Barbara ( $B$ ) play a zero-sum game. This game is represented by the following payoff matrix for Andrew. $$A \left( \begin{array} { c c c } & B & \\ 3 & 5 & 4 \\ 1 & 4 & 2 \\ 6 & 3 & 7 \end{array} \right)$$

Explain why this matrix may be reduced to $$\left( \begin{array} { l l } 3 & 5 \\ 6 & 3 \end{array} \right)$$
Hence find the best strategy for each player and the value of the game.
(8)

4. A two person zero-sum game is represented by the following pay-off matrix for player $A$.

\cline { 2 - 4 } \multicolumn{1}{c\|}{}	$B$ plays I	$B$ plays II	$B$ plays III
$A$ plays I	2	- 1	3
$A$ plays II	1	3	0
$A$ plays III	0	1	- 3

Identify the play safe strategies for each player.
Verify that there is no stable solution to this game.
Explain why the pay-off matrix above may be reduced to
\cline { 2 - 4 } \multicolumn{1}{c|}{} $B$ plays I $B$ plays II $B$ plays III
$A$ plays I 2 - 1 3
$A$ plays II 1 3 0
Find the best strategy for player $A$, and the value of the game.

2. Denis (D) and Hilary (H) play a two-person zero-sum game represented by the following pay-off matrix for Denis.

	H plays 1	H plays 2	H plays 3
D plays 1	2	- 1	3
D plays 2	- 3	4	- 4

Show that there is no stable solution to this game.
Find the best strategy for Denis and the value of the game to him.
(10) (Total 13 marks)

4. Laura and Sam play a zero-sum game. This game is represented by the following pay-off matrix for Laura.

	S plays 1	S plays 2	S plays 3
L plays 1	- 4	- 1	1
L plays 2	3	- 1	- 2
L plays 3	- 3	0	2

Find the best strategy for Laura and the value of the game to her.

4. Robin (R) and Steve (S) play a two-person zero-sum game which is represented by the following pay-off matrix for Robin.

	S plays 1	S plays 2	S plays 3
R plays 1	2	1	3
R plays 2	1	- 1	2
R plays 3	- 1	3	- 3

Find the best strategy for Robin and the value of the game to him.

4. A two-person zero-sum game is represented by the following pay-off matrix for player A.

	B plays 1	B plays 2	B plays 3
A plays 1	5	4	- 6
A plays 2	- 1	- 2	3
A plays 3	1	- 1	2

Reduce the game so that player B has only two possible actions.
Write down the reduced pay-off matrix for player B.
Find the best strategy for player B and the value of the game to him.

3. A two-person zero-sum game is represented by the following pay-off matrix for player A.

	B plays 1	B plays 2	B plays 3
A plays 1	- 2	2	- 3
A plays 2	1	1	- 1
A plays 3	2	- 1	1

Starting by reducing player B's options, find the best strategy for player B.
State the value of the game to player B.

2. Rani and Greg play a zero-sum game. The pay-off matrix shows the number of points that Rani scores for each combination of strategies.

	Greg plays 1	Greg plays 2	Greg plays 3
Rani plays 1	- 3	1	2
Rani plays 2	0	2	1
Rani plays 3	2	4	- 5

Explain what the term 'zero-sum game' means.
State the number of points that Greg scores if he plays his strategy 3 and Rani plays her strategy 3.
Verify that there is no stable solution to this game.
Reduce the game so that Greg has only two possible strategies. Write down the reduced pay-off matrix for Greg.
Find the best strategy for Greg and the value of the game to him.

3. A two-person zero-sum game is represented by the following pay-off matrix for player A.

	B plays 1	B plays 2	B plays 3
A plays 1	- 2	4	3
A plays 2	4	- 1	2

Find the best strategy for player A and the value of the game.
(Total 7 marks)

8. A two person zero-sum game is represented by the following pay-off matrix for player $A$.

	I	II	III
I	5	2	3
II	3	5	4

Verify that there is no stable solution to this game.
Find the best strategy for player $A$ and the value of the game to her.
(Total 11 marks)

6 Lucy and Maria repeatedly play a zero-sum game. The pay-off matrix shows the number of points won by Lucy, who is playing rows, for each combination of strategies.


\cline { 2 - 5 }	$X$	$Y$	$Z$
$A$	2	- 3	4
\cline { 2 - 5 } Lucy's	$B$	- 3	5	1
\cline { 2 - 5 } strategyy	$C$	4	2	- 3

Show that strategy $A$ does not dominate strategy $B$ and also that strategy $B$ does not dominate strategy $A$.
Show that Maria will not choose strategy $Y$ if she plays safe.
Give a reason why Lucy might choose to play strategy $B$. Lucy decides to play strategy $A$ with probability $p _ { 1 }$, strategy $B$ with probability $p _ { 2 }$ and strategy $C$ with probability $p _ { 3 }$. She formulates the following LP problem to be solved using the Simplex algorithm: $$\begin{array} { l l } \text { maximise } & M = m - 3 , \\ \text { subject to } & m \leqslant 5 p _ { 1 } + 7 p _ { 3 } , \\ & m \leqslant 8 p _ { 2 } + 5 p _ { 3 } , \\ & m \leqslant 7 p _ { 1 } + 4 p _ { 2 } , \\ & p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1 , \\ \text { and } & p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , p _ { 3 } \geqslant 0 , m \geqslant 0 . \end{array}$$ [You are not required to solve this problem.]
Explain why 3 has to be subtracted from $m$ in the objective row.
Explain how $5 p _ { 1 } + 7 p _ { 3 } , 8 p _ { 2 } + 5 p _ { 3 }$ and $7 p _ { 1 } + 4 p _ { 2 }$ were obtained.
Explain why $m$ has to be less than or equal to each of the expressions in part (v). Lucy discovers that Maria does not intend ever to choose strategy $Y$. Because of this she decides that she will never choose strategy $B$. This means that $p _ { 2 } = 0$.
Show that the expected number of points won by Lucy when Maria chooses strategy $X$ is $4 - 2 p _ { 1 }$ and find a similar expression for the number of points won by Lucy when Maria chooses strategy $Z$.
Set your two expressions from part (vii) equal to each other and solve for $p _ { 1 }$. Calculate the expected number of points won by Lucy with this value of $p _ { 1 }$ and also when $p _ { 1 } = 0$ and when $p _ { 1 } = 1$. Use these values to decide how Lucy should choose between strategies $A$ and $C$ to maximise the expected number of points that she wins.

3 Rebecca and Claire repeatedly play a zero-sum game in which they each have a choice of three strategies, $X , Y$ and $Z$. The table shows the number of points Rebecca scores for each pair of strategies. \begin{table}[h]

\captionsetup{labelformat=empty} \caption{Claire}

	$X$	$Y$	$Z$
\cline { 2 - 5 }	$X$	5	- 3	1
\cline { 2 - 5 } Rebecca	$Y$	3	2	- 2
\cline { 2 - 5 }	$Z$	- 1	1	3
\cline { 2 - 5 }
\cline { 2 - 5 }

5 The local rugby club has challenged the local cricket club to a chess match to raise money for charity. Each of the top three chess players from the rugby club has played 10 chess games against each of the top three chess players from the cricket club. There were no drawn games. The table shows, for each pairing, the number of games won by the player from the rugby club minus the number of games won by the player from the cricket club. This will be called the score; the scores make a zero-sum game.

If both players choose strategy $X$, how many points will Claire score?
Show that row $X$ does not dominate row $Y$ and that column $Y$ does not dominate column $Z$.
Find the play-safe strategies. State which strategy is best for Claire if she knows that Rebecca will play safe.
Explain why decreasing the value ' 5 ' when both players choose strategy $X$ cannot alter the playsafe strategies.

		Cricket club
\cline { 2 - 5 }\cline { 2 - 5 }		Doug	Euan	Fiona
\cline { 2 - 5 } Sanjeev	0	4	- 2
\cline { 2 - 5 } Rugby club	Tom	- 4	2	- 4
\cline { 2 - 5 }	Ursula	2	- 6	0
\cline { 2 - 5 }
\cline { 2 - 5 }

How many of the 10 games between Sanjeev and Doug did Sanjeev win? How many of the 10 games between Sanjeev and Euan did Euan win? Each club must choose one person to play. They want to choose the person who will optimise the score.
Find the play-safe choice for each club, showing your working. Explain how you know that the game is not stable.
Which person should the cricket club choose if they know that the rugby club will play-safe and which person should the rugby club choose if they know that the cricket club will play-safe?
Explain why the rugby club should not choose Tom. Which player should the cricket club not choose, and why? The rugby club chooses its player by using random numbers to choose between Sanjeev and Ursula, where the probability of choosing Sanjeev is $p$ and the probability of choosing Ursula is $1 - p$.
Write down an expression for the expected score for the rugby club for each of the two remaining choices that can be made by the cricket club. Calculate the optimal value for $p$. Doug is studying AS Mathematics. He removes the row representing Tom and then models the cricket club's problem as the following LP. $$\begin{array} { l l } \operatorname { maximise } & M = m - 4 \\ \text { subject to } & m \leqslant 4 x \quad + 6 z \\ & m \leqslant 2 x + 10 y + 4 z \\ & x + y + z \leqslant 1 \\ \text { and } & m \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
Show how Doug used the values in the table to get the constraints $m \leqslant 4 x + 6 z$ and $m \leqslant 2 x + 10 y + 4 z$. Doug uses the Simplex algorithm to solve the LP problem. His solution has $x = 0$ and $y = \frac { 1 } { 6 }$.
Calculate the optimal value of $M$.

5 Robbie received a new computer game for Christmas. He has already worked through several levels of the game but is now stuck at one of the levels in which he is playing against a character called Conan. Robbie has played this particular level several times. Each time Robbie encounters Conan he can choose to be helped by a dwarf, an elf or a fairy. Conan chooses between being helped by a goblin, a hag or an imp. The players make their choices simultaneously, without knowing what the other has chosen. Robbie starts the level with ten gold coins. The table shows the number of gold coins that Conan must give Robbie in each encounter for each combination of helpers (a negative entry means that Robbie gives gold coins to Conan). If Robbie's total reaches twenty gold coins then he completes the level, but if it reaches zero the game ends. This means that each attempt can be regarded as a zero-sum game.

Conan
\cline { 2 - 5 }		Goblin	Hag	Imp
\cline { 2 - 5 }	Dwarf	- 1	- 4	2
\cline { 2 - 5 } Robbie	Elf	3	1	- 4
\cline { 2 - 5 }	Fairy	1	- 1	1
\cline { 2 - 5 }
\cline { 2 - 5 }

Find the play-safe choice for each player, showing your working. Which helper should Robbie choose if he thinks that Conan will play-safe?
How many gold coins can Robbie expect to win, with each choice of helper, if he thinks that Conan will choose randomly between his three choices (so that each has probability $\frac { 1 } { 3 }$ )? Robbie decides to choose his helper by using random numbers to choose between the elf and the fairy, where the probability of choosing the elf is $p$ and the probability of choosing the fairy is $1 - p$.
Write down an expression for the expected number of gold coins won at each encounter by Robbie for each of Conan's choices. Calculate the optimal value of $p$. Robbie's girlfriend thinks that he should have included the possibility of choosing the dwarf. She denotes the probability with which Robbie should choose the dwarf, the elf and the fairy as $x , y$ and $z$ respectively. She then models the problem of choosing between the three helpers as the following LP. $$\begin{aligned} \text { Maximise } & M = m - 4 , \\ \text { subject to } & m \leqslant 3 x + 7 y + 5 z \\ & m \leqslant 5 y + 3 z \\ & m \leqslant 6 x + 5 z \\ & x + y + z \leqslant 1 , \\ \text { and } & m \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{aligned}$$
Explain how the expression $3 x + 7 y + 5 z$ was formed. Robbie's girlfriend uses the Simplex algorithm to solve the LP problem. Her solution has $x = 0$ and $y = \frac { 2 } { 7 }$.
Calculate the optimal value of $M$.

5 Rose and Colin are playing a game in which they each have four cards. Each player chooses a card from those in their hand, and simultaneously they show each other the cards they have chosen. The table below shows how many points Rose wins for each combination of cards. In each case the number of points that Colin wins is the negative of the entry in the table. Both Rose and Colin are trying to win as many points as possible.

		Colin's card
		$\circ$	$\square$	$\diamond$	$\triangle$
\cline { 2 - 6 }	$\bullet$	- 2	3	- 4	1
\cline { 2 - 6 } Rose's	$\square$	4	- 3	4	5
\cline { 2 - 6 } card	$\diamond$	2	- 5	- 2	- 1
\cline { 2 - 6 }	$\triangle$	- 6	5	- 5	- 3
\cline { 2 - 6 }

What is the greatest number of points that Colin can win when Rose chooses and which card does Colin need to choose to achieve this?
Explain why Rose should never choose and find the card that Colin should never choose. Hence reduce the game to a $3 \times 3$ pay-off matrix.
Find the play-safe strategy for each player on the reduced game and show whether or not the game is stable. Rose makes a random choice between her cards, choosing with probability $x$ with probability $y$, and with probability $z$. She formulates the following LP problem to be solved using the Simplex algorithm:
maximise $\quad M = m - 6$,
subject to $\quad m \leqslant 4 x + 10 y$, $n \leqslant 9 x + 3 y + 11 z$, $n \leqslant 2 x + 10 y + z$, $x + y + z \leqslant 1$,
and $x \geqslant 0 , y \geqslant 0 , z \geqslant 0 , m \geqslant 0$.
(You are not required to solve this problem.)
Explain how $9 x + 3 y + 11 z$ was obtained. The Simplex algorithm is used to solve the LP problem. The solution has $x = \frac { 7 } { 48 } , y = \frac { 27 } { 48 } , z = \frac { 14 } { 48 }$.
Calculate the optimal value of $M$.

4 A group of rowers have challenged some cyclists to see which team is fitter. There will be several rounds to the challenge. In each round, the rowers and the cyclists each choose a team member and these two compete in a series of gym exercises. The time by which the winner finishes ahead of the loser is converted into points. These points are added to the score for the winner's team and taken off the score for the loser's team. The table shows the expected number of points added to the score for the rowers for each combination of competitors. Rowers \begin{table}[h]

\captionsetup{labelformat=empty} \caption{Cyclists}

	Chris	Jamie	Wendy
Andy	- 3	2	- 4
Kath	5	4	- 6
Zac	1	- 4	- 5

4 Ross and Collwen are playing a game in which each secretly chooses a magic spell. They then reveal their choices, and work out their scores using the tables below. Ross and Collwen are both trying to get as large a score as possible.

Regarding this as a zero-sum game, find the play-safe strategy for the rowers and the play-safe strategy for the cyclists. Show that the game is stable. Unfortunately, Wendy and Kath are needed by their coaches and cannot compete.
Show that the resulting reduced game is unstable.
Suppose that the cyclists are equally likely to choose Chris or Jamie. Calculate the expected number of points added to the score for the rowers when they choose Andy and when they choose Zac. Suppose that the cyclists use random numbers to choose between Chris and Jamie, so that Chris is chosen with probability $p$ and Jamie with probability $1 - p$.
Showing all your working, calculate the optimum value of $p$ for the cyclists.
The rowers use random numbers in a similar way to choose between Andy and Zac, so that Andy is chosen with probability $q$ and Zac with probability $1 - q$. Calculate the optimum value of $q$.

Explain how this can be rewritten as the following zero-sum game.
Collwen's choice
Fire Ice Gale
\cline { 2 - 5 } Fire - 3 3 - 2
\cline { 2 - 5 }
Ross's
choice
Ice 2 - 2 0
\cline { 2 - 5 } Gale 1 - 3 - 1
\cline { 2 - 5 }
If Ross chooses Ice what is Collwen's best choice?
Find the play-safe strategy for Ross and the play-safe strategy for Collwen, showing your working. Explain how you know that the game is unstable.
Show that none of Collwen's strategies dominates any other.
Explain why Ross would never choose Gale, hence reduce the game to a $2 \times 3$ zero-sum game, showing the pay-offs for Ross. Suppose that Ross uses random numbers to choose between Fire and Ice, choosing Fire with probability $p$ and Ice with probability $1 - p$.
Use a graphical method to find the optimal value of $p$ for Ross.

6 At the final battle in a war game, the two opposing armies, led by General Rose, $R$, and Colonel Cole, $C$, are facing each other across a wide river. Each army consists of four divisions. The commander of each army needs to send some of his troops North and send the rest South. Each commander has to decide how many divisions (1,2 or 3) to send North. Intelligence information is available on the number of thousands of soldiers that each army can expect to have remaining with each combination of strategies. Thousands of soldiers remaining in $R$ 's army $C$ 's choice $R$ 's choice

	1	2	3
1	15	25	30
2	20	50	15
3	30	35	15

Thousands of soldiers remaining in $C$ 's army $C$ 's choice $R$ 's choice

	1	2	3
1	20	35	10
2	15	50	20
3	10	25	40

Construct a table to show the number of thousands of soldiers remaining in $R$ 's army minus the number of thousands of soldiers remaining in $C$ 's army (the excess for $R$ 's army) for each combination of strategies. The commander whose army has the greatest positive excess of soldiers remaining at the end of the game will be declared the winner.
Explain the meaning of the value in the top left cell of your table from part (i) (where each commander chooses strategy 1). Hence explain why this table may be regarded as representing a zero-sum game.
Find the play-safe strategy for $R$ and the play-safe strategy for $C$. If $C$ knows that $R$ will choose his play-safe strategy, which strategy should $C$ choose? One of the strategies is redundant for one of the commanders, because of dominance.
Draw a table for the reduced game, once the redundant strategy has been removed. Label the rows and columns to show how many divisions have been sent North. A mixed strategy is to be employed on the resulting reduced game. This leads to the following LP problem:
Maximise $\quad M = m - 25$ Subject to $\quad m \leqslant 15 x + 25 y + 35 z$ $m \leqslant 45 x + 20 y$ $x + y + z \leqslant 1$ and
Interpret what $x , y$ and $z$ represent and show how $m \leqslant 15 x + 25 y + 35 z$ was formed. A computer runs the Simplex algorithm to solve this problem. It gives $x = 0.5385 , y = 0$ and $z = 0.4615$.
Describe how this solution should be interpreted, in terms of how General Rose chooses where to send his troops. Calculate the optimal value for $M$ and explain its meaning. Elizabeth does not have access to a computer. She says that at the solution to the LP problem $15 x + 25 y + 35 z$ must equal $45 x + 20 y$ and $x + y + z$ must equal 1 . This simplifies to give $y + 7 z = 6 x$ and $x + y + z = 1$.
Explain why there can be no valid solution of $y + 7 z = 6 x$ and $x + y + z = 1$ with $x = 0$. Elizabeth tries $z = 0$ and gets the solution $x = \frac { 1 } { 7 }$ and $y = \frac { 6 } { 7 }$.
Explain why this is not a solution to the LP problem.

4 Rowan and Colin are playing a game of 'scissors-paper-rock'. In each round of this game, each player chooses one of scissors ( $\$$ ), paper ( $\square$ ) or rock ( $\bullet$ ). The players reveal their choices simultaneously, using coded hand signals. Rowan and Colin will play a large number of rounds. At the end of the game the player with the greater total score is the winner. The rules of the game are that scissors wins over paper, paper wins over rock and rock wins over scissors. In this version of the game, if a player chooses scissors they will score $+ 1,0$ or - 1 points, according to whether they win, draw or lose, but if they choose paper or rock they will score $+ 2,0$ or - 2 points. This gives the following pay-off tables. \includegraphics[max width=\textwidth, alt={}, center]{490ff276-6639-40a1-bffb-dc6967f3ab21-5_476_773_667_239} \includegraphics[max width=\textwidth, alt={}, center]{490ff276-6639-40a1-bffb-dc6967f3ab21-5_478_780_667_1071}

Use an example to show that this is not a zero-sum game.
Write down the minimum number of points that Rowan can win using each strategy. Hence find the strategy that maximises the minimum number of points that Rowan can win. Rowan decides to use random numbers to choose between the three strategies, choosing scissors with probability $p$, paper with probability $q$ and rock with probability $( 1 - p - q )$.
Find and simplify, in terms of $p$ and $q$, expressions for the expected number of points won by Rowan for each of Colin's possible choices. Rowan wants his expected winnings to be the same for all three of Colin's possible choices.
Calculate the probability with which Rowan should play each strategy.

1 The switching circuit in Fig. 1.1 shows switches, $s$ for a car's sidelights, $h$ for its dipped headlights and f for its high-intensity rear foglights. It also shows the three sets of lights. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{ab28be76-9329-41c8-90fe-ff1bdb28f788-2_284_917_404_580} \captionsetup{labelformat=empty} \caption{Fig. 1.1}

\end{figure} (Note: $s$ and $h$ are each "ganged" switches. A ganged switch consists of two connected switches sharing a single switch control, so that both are either on or off together.)

1. Describe in words the conditions under which the foglights will come on. Fig. 1.2 shows a combinatorial circuit. \begin{figure}[h]
  \includegraphics[alt={},max width=\textwidth]{ab28be76-9329-41c8-90fe-ff1bdb28f788-2_367_1235_1183_431} \captionsetup{labelformat=empty} \caption{Fig. 1.2}
  \end{figure}
2. Write the output in terms of a Boolean expression involving $s , h$ and $f$.
3. Use a truth table to prove that $\mathrm { s } \wedge \mathrm { h } \wedge \mathrm { f } = \sim ( \sim \mathrm { s } \vee \sim \mathrm { h } ) \wedge \mathrm { f }$.
A car's first gear can be engaged ( g ) if either both the road speed is low ( r ) and the clutch is depressed ( d ), or if both the road speed is low ( r ) and the engine speed is the correct multiple of the road speed (m).
1. Draw a switching circuit to represent the conditions under which first gear can be engaged. Use two ganged switches to represent $r$, and single switches to represent each of $\mathrm { d } , \mathrm { m }$ and g .
2. Draw a combinatorial circuit to represent the Boolean expression $\mathrm { r } \wedge ( \mathrm { d } \vee \mathrm { m } ) \wedge \mathrm { g }$.
3. Use Boolean algebra to prove that $\mathrm { r } \wedge ( \mathrm { d } \vee \mathrm { m } ) \wedge \mathrm { g } = ( ( \mathrm { r } \wedge \mathrm { d } ) \vee ( \mathrm { r } \wedge \mathrm { m } ) ) \wedge \mathrm { g }$.
4. Draw another switching circuit to represent the conditions under which first gear can be selected, but without using a ganged switch.

Use a truth table to prove $\sim ( \sim \mathrm { T } \Rightarrow \sim \mathrm { S } ) \Leftrightarrow ( \sim \mathrm { T } \wedge \mathrm { S } )$.
Prove that $( \mathrm { A } \Rightarrow \mathrm { B } ) \Leftrightarrow ( \sim \mathrm { A } \vee \mathrm { B } )$ and hence use Boolean algebra to prove that $$\sim ( \sim \mathrm { T } \Rightarrow \sim \mathrm {~S} ) \Leftrightarrow ( \sim \mathrm { T } \wedge \mathrm {~S} ) .$$
A teacher wrote on a report "It is not the case that if Joanna doesn't try then she won't succeed." He meant to say that if Joanna were to try then she would have a chance of success. By letting T be "Joanna will try" and S be "Joanna will succeed", find the real meaning of what the teacher wrote.

The Plain English Society presents an annual "Foot in Mouth" award for "a truly baffling comment". In 2004 it was presented to Boris Johnson MP for a comment on the $12 ^ { \text {th } }$ December 2003 edition of "Have I Got News For You":
"I could not fail to disagree with you less."
1. Explain why this can be rewritten as:
  "I could succeed in agreeing with you more."
2. Rewrite the comment more simply in your own words without changing its meaning.
Two switches are to be wired between a mains electricity supply and a light so that when the state of either switch is changed the state of the light changes (i.e. from off to on, or from on to off). Draw a switching circuit to achieve this. The switches are both 2-way switches, thus: \includegraphics[max width=\textwidth, alt={}, center]{88acde67-e22b-478a-9145-48abe931beff-2_127_220_895_1054}
Construct a truth table to show the following. $$[ ( a \wedge b ) \vee ( ( \sim a ) \wedge ( \sim b ) ) ] \Leftrightarrow [ ( ( \sim a ) \vee b ) \wedge ( a \vee ( \sim b ) ) ]$$

The following was said in a charity appeal on Radio 4 in October 2006.
"It is hard to underestimate the effect that your contribution will make."
Rewrite the comment more simply in your own words without changing its meaning.
A machine has three components, A, B and C, each of which is either active or inactive.
The states (active or inactive) of the components and the machine are to be modelled by a combinatorial circuit in which "active" is represented by "true" and "inactive" is represented by "false". Draw such a circuit.
Construct a truth table to show the following. $$[ ( ( \mathrm { a } \wedge \mathrm {~b} ) \vee ( ( \sim \mathrm { a } ) \wedge \mathrm { c } ) ) \vee ( ( \sim \mathrm { b } ) \wedge \mathrm { c } ) ] \Leftrightarrow \sim [ ( ( \sim \mathrm { a } ) \wedge ( \sim \mathrm { c } ) ) \vee ( ( \sim \mathrm { b } ) \wedge ( \sim \mathrm { c } ) ) ]$$

Heard in Parliament: "Will the minister not now discontinue her proposal to ban the protest?"
The minister replied "Yes I will."
To what had the minister committed herself logically, and why might that not have been her intention?
In a cricket tournament an umpire might be required to decide whether or not a batsman is out 'lbw', ie 'leg before wicket'. The lbw law for the tournament refers to parts of the cricket pitch as shown in the diagram (assuming a right-handed batsman): \includegraphics[max width=\textwidth, alt={}, center]{52b8153f-e655-4852-a0f8-6f1c1e9c9170-2_254_1045_717_507} The umpire has to make a number of judgements:
A Would the ball have hit the wicket?
B Did the ball hit the batsman, or part of his equipment other than the bat, without hitting the bat?
C Did the ball hit the batsman, or part of his equipment other than the bat, before hitting the bat?
D Was the part of the batsman or his equipment which was hit by the ball, between the wickets when it was hit? E Was the part of the batsman or his equipment which was hit by the ball, outside of the wicket on the off side when it was hit? F Was the batsman attempting to play a stroke?
The law can be interpreted as saying that the batsman is out lbw if $[ ( \mathrm { A } \wedge \mathrm { B } ) \vee ( \mathrm { A } \wedge \mathrm { C } ) ] \wedge [ \mathrm { D } \vee ( \mathrm { E } \wedge \sim \mathrm { F } ) ]$.
The tournament's umpiring manual, in attempting to simplify the law, states that the batsman is out lbw if $\mathrm { A } \wedge ( \mathrm { B } \vee \mathrm { C } ) \wedge ( \mathrm { D } \vee \mathrm { E } ) \wedge ( \mathrm { D } \vee \sim \mathrm { F } )$. For an lbw decision this requires 4 conditions each to be true.
1. Use the rules of Boolean algebra to show that the manual's rule is logically equivalent to the law as stated above, naming the rules used at each step. A trainee umpire, using the manual, considers each condition in turn and judges that the following are true: A; B; E; D.
2. What is her decision and why?
3. What is odd about her judgement, and does this make the logic invalid?

The payoff matrix for player $A$ in a two-person zero-sum game is shown below.

\cline { 3 - 5 } \multicolumn{2}{c\|}{}	$B$
\cline { 3 - 5 } \multicolumn{2}{c\|}{}	I	II	III
\multirow{3}{*}{$A$}	I	- 3	4	0
\cline { 2 - 5 }	II	2	2	1
\cline { 2 - 5 }	III	3	- 2	- 1

Find the optimal strategy for each player and the value of the game.

5. The payoff matrix for player $X$ in a two-person zero-sum game is shown below.

\cline { 3 - 5 } \multicolumn{2}{c\|}{}	$Y$
\cline { 2 - 5 } \multicolumn{2}{c\|}{}	$Y _ { 1 }$	$Y _ { 2 }$	$Y _ { 3 }$
\multirow{2}{*}{$X$}	$X _ { 1 }$	10	4	3
\cline { 2 - 5 }	$X _ { 2 }$	${ } ^ { - } 4$	${ } ^ { - } 1$	9

Using a graphical method, find the optimal strategy for player $X$.
Find the optimal strategy for player $Y$.
Find the value of the game.

3. A two-person zero-sum game is represented by the payoff matrix for player $A$ shown below.

\cline { 3 - 5 } \multicolumn{2}{c\|}{}	$B$
\cline { 3 - 5 } \multicolumn{2}{c\|}{}	I	II	III
\multirow{2}{*}{$A$}	I	1	- 1	2
\cline { 2 - 5 }	II	3	5	- 1

Represent the expected payoffs to $A$ against $B$ 's strategies graphically and hence determine which strategy is not worth considering for player $B$.
Find the best strategy for player $A$ and the value of the game.

5 The number of points won by player 1 in a zero-sum game is shown in the pay-off matrix below, where $k$ is a constant. \begin{table}[h]

\captionsetup{labelformat=empty} \caption{Player 2}

	Strategy E	Strategy F	Strategy G	Strategy H
Strategy A	$2 k$	-2	$1 - k$	4
Strategy B	-3	3	4	-5
Strategy C	1	4	-4	2
Strategy D	4	-2	-5	6