Group properties and structure

1. The payoff matrix for player \(A\) in a two-person zero-sum game is shown below.

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.

1. Using a graphical method, find the optimal strategy for player \(X\).
2. Find the optimal strategy for player \(Y\).
3. Find the value of the game.

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

1. Represent the expected payoffs to \(A\) against \(B\) 's strategies graphically and hence determine which strategy is not worth considering for player \(B\).
2. 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] \end{table}

1. In one game, player 2 chooses strategy H. Write down the greatest number of points that player 2 could win. You are given that strategy A is a play-safe strategy for player 1.
2. Determine the range of possible values for \(k\).
3. Determine the column minimax value.

3 A zero-sum game is being played between two players, \(X\) and \(Y\). The pay-off matrix for \(X\) is given below. \section*{Player X}

1. Find an optimal mixed strategy for player \(X\).
2. Give one assumption that must be made about the behaviour of \(Y\) in order to make the mixed strategy of Player \(X\) valid.

6 The pay-off matrix for a game between two players, Sumi and Vlad, is shown below. If Sumi plays A and Vlad plays X then Sumi gets X points and Vlad gets 1 point. Sumi You are given that cell ( \(\mathrm { A } , \mathrm { X }\) ) is a Nash Equilibrium solution.

1. Find the range of possible values of X .
2. Explain what the statement 'cell (A, X) is a Nash Equilibrium solution' means for each player.
3. Find a cell where each player gets their maximin pay-off. Suppose, instead, that the game can be converted to a zero-sum game.
4. Determine the optimal strategy for Sumi for the zero-sum game.
   • Record the pay-offs for Sumi when the game is converted to a zero-sum game.
   • Describe how Sumi should play using this strategy.

5 In each turn of a game between two players they simultaneously each choose a strategy and then calculate the points won using the table below. They are each trying to maximise the number of points that they win. In each cell the first value is the number of points won by player 1 and the second value is the number of points won by player 2 .

1. Find the play-safe strategy for each player.
2. Explain why player 2 would never choose strategy Z .
3. Find the Nash equilibrium solution(s) or show that there is no Nash equilibrium solution. Player 2 chooses strategy X with probability \(p\) and strategy Y with probability \(1 - p\). You are given that when player 1 chooses strategy A, the expected number of points won by each player is the same.
4. 1. Calculate the value of \(p\).
   2. Determine which player expects to win the greater number of points when player 1 chooses strategy B.

7 Player 1 and player 2 are playing a two-person zero-sum game.
In each round of the game the players each choose a strategy and simultaneously reveal their choice. The number of points won in each round by player 1 for each combination of strategies is shown in the table below. Each player is trying to maximise the number of points that they win.
Player 2 Player 1

1. 1. Determine play-safe strategies for each player.
   2. Show that the game is not stable.
2. Show that the number of strategies available to player 1 cannot be reduced by dominance. You must make it clear which values are being compared. Player 1 intends to make a random choice between strategies \(\mathrm { X } , \mathrm { Y } , \mathrm { Z }\), choosing strategy X with probability \(x\), strategy Y with probability \(y\) and strategy Z with probability \(z\).
   Player 1 formulates the following LP problem so they can find the optimal values of \(x , y\) and \(z\) using the simplex algorithm. Maximise \(M = m - 4\)
   subject to \(m \leqslant 6 x + 4 y + 2 z\) $$\begin{aligned} & m \leqslant x + 5 y + 6 z \\ & m \leqslant 7 y + 8 z \\ & x + y + z \leqslant 1 \end{aligned}$$ and \(m \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0\)
3. Explain how the inequality \(m \leqslant 6 x + 4 y + 2 z\) was formed. The problem is solved by running the simplex algorithm on a computer.
   The printout gives a solution in which \(\mathrm { x } + \mathrm { y } = 1\).
   This means that the LP problem can be reduced to the following formulation.
   Maximise \(M = m - 4\)
   subject to \(m \leqslant 4 + 2 x\)
   \(\mathrm { m } \leqslant 5 - 4 \mathrm { x }\)
   \(m \leqslant 7 - 7 x\)
   and \(m \geqslant 0 , x \geqslant 0\)
4. Solve this problem to find the optimal values of \(x , y\) and \(z\) and the corresponding value of the game to player 1.

1 At the end of each year the workers at an office take part in a gift exchange.
Each worker randomly chooses the name of one other worker and buys a small gift for that person. Each worker's name is chosen by exactly one of the others.
A worker cannot choose their own name. In the first year there were four workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D .
There are 9 ways in which A, B, C and D can choose the names for the gift exchange. One of these is already given in the table in the Printed Answer Booklet.

1. Complete the table in the Printed Answer Booklet to show the remaining 8 ways in which the names can be chosen. During the second year, worker D left and was replaced with worker E.
   The organiser of the gift exchange wants to know whether it is possible for the event to happen for another 3 years (starting with the second year) with none of the workers choosing a name they have chosen before, assuming that there are no further changes in the workers.
2. Classify the organiser's problem as an existence, construction, enumeration or optimisation problem. After the second year, the organiser drew a graph showing who each worker chose in the first two years of the gift exchange.
   None of the workers chose the same name in the first and second years.
   The vertices of the graph represented the workers, A, B, C, D and E, and the arcs showed who had been chosen by each worker.
3. Explain why the graph must be a digraph.
4. State the number of arcs in the digraph that shows the choices for the first two years.
5. Assuming that the digraph created in part (d) is planar, use Euler's formula to calculate how many regions it has.

3 Amir and Beth play a zero-sum game.
The table shows the pay-off for Amir for each combination of strategies, where these values are known. \begin{table}[h] \end{table} You are given that \(\mathrm { a } < 0 < \mathrm { b } < \mathrm { c }\).
Amir's play-safe strategy is R.

1. Determine the range of possible values of \(a\). Beth's play-safe strategy is Y.
2. Determine the range of possible values of \(b\).
3. Determine whether or not the game is stable.

6 The group \(G\) consists of the set \(\{ 3,6,9,12,15,18,21,24,27,30,33,36 \}\) under \(\times _ { 39 }\), the operation of multiplication modulo 39.

1. List the possible orders of proper subgroups of \(G\), justifying your answer.
2. List the elements of the subset of \(G\) generated by the element 3 .
3. State the identity element of \(G\).
4. Determine the order of the element 18 .
5. Find the two elements \(g _ { 1 }\) and \(g _ { 2 }\) in \(G\) which satisfy \(g \times { } _ { 39 } g = 3\). The group \(H\) consists of the set \(\{ 1,2,3,4,5,6,7,8,9,10,11,12 \}\) under \(\times _ { 13 }\), the operation of multiplication modulo 13. You are given that \(G\) is isomorphic to \(H\). A student states that \(G\) is isomorphic to \(H\) because each element \(3 x\) in \(G\) maps directly to the element \(x\) in \(H\) (for \(x = 1,2,3,4,5,6,7,8,9,10,11,12\) ).
6. Explain why this student is incorrect.

1 The set \(G = \{ 1,4,5,6,7,9,11,16,17 \}\) is a group of order 9 under the binary operation of multiplication modulo 19.

1. Show that \(G\) is a cyclic group generated by the element 4 .
2. Find another generator for \(G\). Justify your answer.
3. Specify two distinct isomorphisms from the group \(J = \{ 0,1,2,3,4,5,6,7,8 \}\) under addition modulo 9 to \(G\).

2 The set \(\{ 1,2,4,8,9,13,15,16 \}\) forms a group under the operation of multiplication modulo 17. Which of the following is a generator of the group? Circle your answer.
[0pt] [1 mark] 491316

1. 1. The table below is a Cayley table for the group \(G\) with operation ∘

1. State which element is the identity of the group.
2. Determine the inverse of the element ( \(b \circ c\) )
3. Give a reason why the set \(\{ a , b , e , f \}\) cannot be a subgroup of \(G\). You must justify your answer.
4. 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}

1. The set of matrices \(G = \{ \mathbf { I } , \mathbf { A } , \mathbf { B } , \mathbf { C } , \mathbf { D } , \mathbf { E } \}\) where

$$\mathbf { I } = \left( \begin{array} { l l } 1 & 0 \\ 0 & 1 \end{array} \right) \quad \mathbf { A } = \left( \begin{array} { l l } 0 & 1 \\ 1 & 0 \end{array} \right) \quad \mathbf { B } = \left( \begin{array} { l l } 1 & 1 \\ 1 & 0 \end{array} \right) \quad \mathbf { C } = \left( \begin{array} { l l } 1 & 1 \\ 0 & 1 \end{array} \right) \quad \mathbf { D } = \left( \begin{array} { l l } 1 & 0 \\ 1 & 1 \end{array} \right) \quad \mathbf { E } = \left( \begin{array} { l l } 0 & 1 \\ 1 & 1 \end{array} \right)$$ with the operation \(\otimes _ { 2 }\) of matrix multiplication with entries evaluated modulo 2 , forms a group.

1. Show that \(\mathbf { B }\) is an element of order 3 in \(G\).
2. Determine the orders of the other elements of \(G\).
3. Give a reason why \(G\) is not isomorphic to
   1. a cyclic group of order 6
   2. the group of symmetries of a regular hexagon. The group \(H\) of permutations of the numbers 1, 2 and 3 contains the following elements, denoted in two-line notation, $$\begin{array} { l l l } e = \left( \begin{array} { l l l } 1 & 2 & 3 \\ 1 & 2 & 3 \end{array} \right) & a = \left( \begin{array} { l l l } 1 & 2 & 3 \\ 2 & 3 & 1 \end{array} \right) & b = \left( \begin{array} { l l l } 1 & 2 & 3 \\ 3 & 1 & 2 \end{array} \right) \\ c = \left( \begin{array} { l l } 1 & 2 \\ 1 & 3 \\ 2 \end{array} \right) & d = \left( \begin{array} { l l l } 1 & 2 & 3 \\ 2 & 1 & 3 \end{array} \right) & f = \left( \begin{array} { l l } 1 & 2 \\ 3 & 2 \end{array} \right) \end{array}$$
4. Determine an isomorphism between the groups \(G\) and \(H\).

7 The set \(M\) contains all matrices of the form \(\mathbf { X } ^ { n }\), where \(\mathbf { X } = \frac { 1 } { \sqrt { 3 } } \left( \begin{array} { r r } 2 & - 1 \\ 1 & 1 \end{array} \right)\) and \(n\) is a positive integer.

1. Show that \(M\) contains exactly 12 elements.
2. Deduce that \(M\), together with the operation of matrix multiplication, form a cyclic group \(G\).
3. Determine all the proper subgroups of \(G\). \section*{END OF QUESTION PAPER}

5 The set \(S\) consists of all \(2 \times 2\) matrices having determinant 1 or - 1 . For instance, the matrices \(\mathbf { P } = \left( \begin{array} { c c } \frac { 1 } { 2 } & \frac { \sqrt { 3 } } { 2 } \\ - \frac { \sqrt { 3 } } { 2 } & \frac { 1 } { 2 } \end{array} \right) , \mathbf { Q } = - \left( \begin{array} { c c } \frac { 1 } { 2 } & \frac { \sqrt { 3 } } { 2 } \\ - \frac { \sqrt { 3 } } { 2 } & \frac { 1 } { 2 } \end{array} \right)\) and \(\mathbf { R } = \left( \begin{array} { r r } 1 & 0 \\ 0 & - 1 \end{array} \right)\) are elements of \(S\). It is given that \(\times _ { \mathbf { M } }\) is the operation of matrix multiplication.

1. State the identity element of \(S\) under \(\times _ { \mathbf { M } }\). The group \(G\) is generated by \(\mathbf { P }\), under \(\times _ { \mathbf { M } }\).
2. Determine the order of \(G\). The group \(H\) is generated by \(\mathbf { Q }\) and \(\mathbf { R }\), also under \(\times _ { \mathbf { M } }\).
3. 1. By finding each element of \(H\), determine the order of \(H\).
   2. List all the proper subgroups of \(H\).
4. State whether each of the following statements is true or false. Give a reason for each of your answers.
   • \(G\) is abelian
   • \(G\) is cyclic
   • \(H\) is abelian
   • \(H\) is cyclic