Non-group structures

1

1. Show that the set of numbers \(\{ 3,5,7 \}\), under multiplication modulo 8, does not form a group.
2. The set of numbers \(\{ 3,5,7 , a \}\), under multiplication modulo 8 , forms a group. Write down the value of \(a\).
3. State, justifying your answer, whether or not the group in part (ii) is isomorphic to the multiplicative group \(\left\{ e , r , r ^ { 2 } , r ^ { 3 } \right\}\), where \(e\) is the identity and \(r ^ { 4 } = e\).

4 Let \(A\) be the set of non-zero integers.

1. Show that \(A\) does not form a group under multiplication.
2. State the largest subset of \(A\) which forms a group under multiplication. Show that this is a group.

6 Rose is playing a game against a computer. Rose aims a laser beam along a row, \(A , B\) or \(C\), and, at the same time, the computer aims a laser beam down a column, \(X , Y\) or \(Z\). The number of points won by Rose is determined by where the two laser beams cross. These values are given in the table. The computer loses whatever Rose wins.

1. Find Rose's play-safe strategy and show that the computer's play-safe strategy is \(Y\). How do you know that the game does not have a stable solution?
2. Explain why Rose should never choose row \(C\) and hence reduce the game to a \(2 \times 3\) pay-off matrix.
3. Rose intends to play the game a large number of times. She decides to use a standard six-sided die to choose between row \(A\) and row \(B\), so that row \(A\) is chosen with probability \(a\) and row \(B\) is chosen with probability \(1 - a\). Show that the expected pay-off for Rose when the computer chooses column \(X\) is \(4 - 3 a\), and find the corresponding expressions for when the computer chooses column \(Y\) and when it chooses column \(Z\). Sketch a graph showing the expected pay-offs against \(a\), and hence decide on Rose's optimal choice for \(a\). Describe how Rose could use the die to decide whether to play \(A\) or \(B\). The computer is to choose \(X , Y\) and \(Z\) with probabilities \(x , y\) and \(z\) respectively, where \(x + y + z = 1\). Graham is an AS student studying the D1 module. He wants to find the optimal choices for \(x , y\) and \(z\) and starts off by producing a pay-off matrix for the computer.
4. Graham produces the following pay-off matrix.

   3	1	0
   0	1	2

   Write down the pay-off matrix for the computer and explain what Graham did to its entries to get the values in his pay-off matrix.
5. Graham then sets up the linear programming problem: $$\begin{array} { l l } \text { maximise } & P = p - 4 , \\ \text { subject to } & p - 3 x - y \leqslant 0 , \\ & p - y - 2 z \leqslant 0 , \\ & x + y + z \leqslant 1 , \\ \text { and } & p \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$ The Simplex algorithm is applied to the problem and gives \(x = 0.4\) and \(y = 0\). Find the values of \(z , p\) and \(P\) and interpret the solution in the context of the game. \href{http://physicsandmathstutor.com}{physicsandmathstutor.com}

2 Annie and Brett play a two-person, simultaneous play game. The table shows the pay-offs for Annie and Brett in the form ( \(a , b\) ). So, for example, if Annie plays strategy K and Brett plays strategy S, Annie wins 2 points and Brett wins 6 points.

1. 1. Determine the play-safe strategy for Annie.
   2. Show that the play-safe strategy for Brett is T.
2. 1. If Annie knows that Brett is planning on playing strategy T, which strategy should Annie play to maximise her points?
   2. If Brett knows that Annie is planning on playing the strategy identified in part (b)(i), which strategy should Brett play to maximise his points?
3. Show that, for Brett, strategy R is weakly dominated.
4. Using a graphical method, determine the optimal mixed strategy for Brett.
5. Show that the game has no Nash equilibrium points.

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] \end{table} Suppose that P is a play-safe strategy.

1. 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.
2. Write down the pay-off matrix for the reduced game. When the game is unstable, Alex plays strategy P with probability \(p\).
3. 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 .
4. Show how to set up a linear programming formulation that could be used to find the optimal mixed strategy for Alex.

4 The table shows the pay-off matrix for player \(A\) in a two-person zero-sum game between \(A\) and \(B\). Player \(A\)
Player \(B\)

1. 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.
2. If player \(B\) knows that player \(A\) will use their play-safe strategy, which strategy should player \(B\) use?
3. 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.
4. 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.
5. Show that the zero-sum game in the table above has a Nash equilibrium and explain what this means for the players.

4

1. In each of the following cases, a set \(G\) and a binary operation ∘ are given. The operation ∘ may be assumed to be associative on \(G\). Determine which, if any, of the other three group axioms are satisfied by ( \(G , \circ\) ) and which, if any, are not satisfied.
   1. \(G = \{ 2 n + 1 : n \in \mathbb { Z } \}\) and \(\circ\) is addition.
   2. \(G = \{ a + b \sqrt { 2 } : a , b \in \mathbb { Z } \}\) and ∘ is multiplication.
   3. \(G\) is the set of all real numbers and ∘ is multiplication.
2. A group \(M\) consists of eight \(2 \times 2\) matrices under the operation of matrix multiplication. Five of the eight elements of \(M\) are as follows. $$\frac { 1 } { \sqrt { 2 } } \left( \begin{array} { l l } 1 & \mathrm { i } \\ \mathrm { i } & 1 \end{array} \right) \quad \frac { 1 } { \sqrt { 2 } } \left( \begin{array} { r r } - 1 & \mathrm { i } \\ \mathrm { i } & - 1 \end{array} \right) \quad \frac { 1 } { \sqrt { 2 } } \left( \begin{array} { r r } 1 & - \mathrm { i } \\ - \mathrm { i } & 1 \end{array} \right) \quad \left( \begin{array} { l l } 0 & \mathrm { i } \\ \mathrm { i } & 0 \end{array} \right) \quad \left( \begin{array} { l l } 1 & 0 \\ 0 & 1 \end{array} \right)$$
   1. Find the other three elements of \(M\).
      \(( N , * )\) is another group of order 8, with identity element \(e\). You are given that \(N = \langle a , b , c \rangle\) where \(a * a = b * b = c * c = e\).
   2. State whether \(M\) and \(N\) are isomorphic to each other, giving a reason for your answer.

1. A binary operation ★ on the set of non-negative integers, \(\mathbb { Z } _ { 0 } ^ { + }\), is defined by

$$m \star n = | m - n | \quad m , n \in \mathbb { Z } _ { 0 } ^ { + }$$

1. Explain why \(\mathbb { Z } _ { 0 } ^ { + }\)is closed under the operation
2. Show that 0 is an identity for \(\left( \mathbb { Z } _ { 0 } ^ { + } , \star \right)\)
3. Show that all elements of \(\mathbb { Z } _ { 0 } ^ { + }\)have an inverse under ★
4. Determine if \(\mathbb { Z } _ { 0 } ^ { + }\)forms a group under ★, giving clear justification for your answer.

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] \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. 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]{83d00f1f-25e5-4a26-bac5-dc2baf965438-02_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 }\).
2. 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.

1 The table shows some of the outcomes of performing a modular arithmetic operation. Which pair are operations that could each be represented by the table?
Tick ( ✓ ) one box.
\includegraphics[max width=\textwidth, alt={}, center]{5a826f8b-4751-4589-ad0a-109fc5c821f2-02_109_111_1338_497} Addition \(\bmod 6\) and multiplication \(\bmod 5\)
\includegraphics[max width=\textwidth, alt={}, center]{5a826f8b-4751-4589-ad0a-109fc5c821f2-02_108_109_1471_497} Addition mod 6 and multiplication \(\bmod 6\)
\includegraphics[max width=\textwidth, alt={}, center]{5a826f8b-4751-4589-ad0a-109fc5c821f2-02_113_109_1603_497} Addition mod 4 and multiplication \(\bmod 5\)
\includegraphics[max width=\textwidth, alt={}, center]{5a826f8b-4751-4589-ad0a-109fc5c821f2-02_107_109_1742_497} Addition mod 4 and multiplication mod 6

2 The binary operation ⊗ is given by
\(a \otimes b = 3 a ( 5 + b ) ( \bmod 8 )\)
where \(a , b \in \mathbb { Z }\)
Given that \(2 \otimes x = 6\), which of the integers below is a possible value of \(x\) ?
Circle your answer.
[0pt] [1 mark]
0123

6 The diagram shows a nature reserve which has its entrance at \(A\), eight information signs at \(B , C , \ldots , I\), and fifteen grass paths. The length of each grass path is given in metres.
The total length of the grass paths is 1465 metres.
\includegraphics[max width=\textwidth, alt={}, center]{dcf97b92-d067-41d4-89a6-ea5bab9ea4ff-10_812_1192_584_424} To cut the grass, Ashley starts at the entrance and drives a mower along every grass path in the nature reserve. The mower moves at 7 kilometres per hour. 6

1. Find the least possible time that it takes for Ashley to cut the grass on all fifteen paths in the nature reserve and return to the entrance. Fully justify your answer.
   6
2. Brook visits every information sign in the nature reserve to update them, starting and finishing at the entrance. For the eight information signs, the minimum connecting distance of the grass paths is 510 metres. 6
3. 1. Determine a lower bound for the distance Brook walks to visit every information sign.
      Fully justify your answer.
      [0pt] [2 marks]
      6
4. (ii) Using the nearest neighbour algorithm starting from the entrance, determine an upper bound for the distance Brook walks to visit every information sign.
   [0pt] [2 marks]
   6
5. Brook takes one minute to update the information at one information sign. Brook walks on the grass paths at an average speed of 5 kilometres per hour. Ashley and Brook start from the entrance at the same time. 6
6. 1. Use your answers from parts (a) and (b) to show that Ashley and Brook will return to the entrance at approximately the same time. Fully justify your answer.
      6
7. (ii) State an assumption that you have used in part (c)(i).
   \includegraphics[max width=\textwidth, alt={}, center]{dcf97b92-d067-41d4-89a6-ea5bab9ea4ff-13_2488_1716_219_153}
   \(7 \quad\) Ali and Bex play a zero-sum game. The game is represented by the following pay-off matrix for Ali.

   \multirow{2}{*}{}	Bex
   	Strategy	\(\mathbf { B } _ { \mathbf { 1 } }\)	\(\mathbf { B } _ { \mathbf { 2 } }\)	\(\mathbf { B } _ { \mathbf { 3 } }\)
   \multirow{4}{*}{Ali}	\(\mathbf { A } _ { \mathbf { 1 } }\)	2	-1	3
   	\(\mathbf { A } _ { \mathbf { 2 } }\)	-4	-2	2
   	\(\mathbf { A } _ { \mathbf { 3 } }\)	0	1	1
   	\(\mathrm { A } _ { 4 }\)	-3	2	-2

7

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

3 Summer and Haf play a zero-sum game. The pay-off matrix for the game is shown below. Haf 3

1. Show that the game has a stable solution.
   3
2. 1. State the value of the game for Summer. 3
3. (ii) State the play-safe strategy for each player.

5
7
8
12 1 (b) Find the value of \(y\)
Circle your answer.
5
7
8
15 2 The set \(S\) is given by \(S = \{ 0,2,4,6 \}\) 2 (a) Construct a Cayley table, using the grid below, for \(S\) under the binary operation addition modulo 8
\includegraphics[max width=\textwidth, alt={}, center]{18ce34aa-e4c3-4a84-a36d-6542d2319bf5-03_561_563_607_831} 2 (b) State the identity element for \(S\) under the binary operation addition modulo 8

8
12 1 (b) Find the value of \(y\)
Circle your answer.
5
7
8
15 2 The set \(S\) is given by \(S = \{ 0,2,4,6 \}\) 2 (a) Construct a Cayley table, using the grid below, for \(S\) under the binary operation addition modulo 8
\includegraphics[max width=\textwidth, alt={}, center]{18ce34aa-e4c3-4a84-a36d-6542d2319bf5-03_561_563_607_831} 2 (b) State the identity element for \(S\) under the binary operation addition modulo 8

7 Kez and Lui play a zero-sum game. The game does not have a stable solution. The game is represented by the following pay-off matrix for Kez. 7

1. State, with a reason, why Kez should never play strategy \(\mathbf { K } _ { \mathbf { 2 } }\) 7
2. \(\quad\) Kez and Lui play the game 20 times.
   Kez plays their optimal mixed strategy.
   Find the expected number of times that Kez will play strategy \(\mathbf { K } _ { \mathbf { 3 } }\)
   Fully justify your answer.

6 Xander and Yvonne are playing a zero-sum game. The game is represented by the pay-off matrix for Xander. \begin{table}[h] \end{table} 6

1. Show that the game has a stable solution.
   6
2. State the play-safe strategy for each player. Play-safe strategy for Xander is \(\_\_\_\_\)
   Play-safe strategy for Yvonne is \(\_\_\_\_\) 6
3. The game that Xander and Yvonne are playing is part of a marbles challenge. The pay-off matrix values represent the number of marbles gained by Xander in each game. In the challenge, the game is repeated until one player has 24 marbles more than the other player. Explain why Xander and Yvonne must play at least 3 games to complete the challenge.

2 Which of the following statements is true about the operation of matrix multiplication on the set of all \(2 \times 2\) real matrices? Tick ( \(\checkmark\) ) one box. Matrix multiplication is associative and commutative.
\includegraphics[max width=\textwidth, alt={}, center]{c297a67f-65fd-47e0-a60c-d38fd86c6081-03_109_112_552_1599} Matrix multiplication is associative but not commutative. □ Matrix multiplication is commutative but not associative. □ Matrix multiplication is not commutative and not associative. □

1 Which one of the following sets forms a group under the given binary operation?
Tick ( ✓ ) one box.