7.01d Multiplicative principle: arrangements of n distinct objects

3 Fig. 3.1 shows an equilateral triangle, with vertices \(\mathrm { A } , \mathrm { B }\) and C , and the three axes of symmetry of the triangle, \(\mathrm { S } _ { \mathrm { a } } , \mathrm { S } _ { \mathrm { b } }\) and \(\mathrm { S } _ { \mathrm { c } }\). The axes of symmetry are fixed in space and all intersect at the point O . \begin{figure}[h] \end{figure} There are six distinct transformations under which the image of the triangle is indistinguishable from the triangle itself, ignoring labels.
These are denoted by \(\mathrm { I } , \mathrm { M } _ { a ^ { \prime } } \mathrm { M } _ { \mathrm { b } ^ { \prime } } , \mathrm { M } _ { \mathrm { c } ^ { \prime } } , \mathrm { R } _ { 120 }\) and \(\mathrm { R } _ { 240 }\) where

• I is the identity transformation
• \(\mathrm { M } _ { \mathrm { a } }\) is a reflection in the mirror line \(\mathrm { S } _ { \mathrm { a } }\) (and likewise for \(\mathrm { M } _ { \mathrm { b } }\) and \(\mathrm { M } _ { \mathrm { c } }\) )
• \(\mathrm { R } _ { 120 }\) is an anticlockwise rotation by \(120 ^ { \circ }\) about O (and likewise for \(\mathrm { R } _ { 240 }\) ).

Composition of transformations is denoted by ○.
Fig. 3.2 illustrates the composition of \(R _ { 120 }\) followed by \(R _ { 240 }\), denoted by \(R _ { 240 } \circ R _ { 120 }\). This shows that \(\mathrm { R } _ { 240 } \circ \mathrm { R } _ { 120 }\) is equivalent to the identity transformation, so that \(\mathrm { R } _ { 240 } \circ \mathrm { R } _ { 120 } = \mathrm { I }\). \begin{figure}[h] \end{figure}

1. Using the blank diagrams in the Printed Answer Booklet, find the single transformation which is equivalent to each of the following.
   The set of the six transformations is denoted by G and you are given that \(( \mathrm { G } , \circ )\) is a group. The table below is a mostly empty composition table for \(\circ\). The entry given is that for \(R _ { 240 } \circ R _ { 120 }\).
   First transformation performed is
   followed by

   ◯	I	\(\mathrm { M } _ { \mathrm { a } }\)	\(\mathrm { M } _ { \mathrm { b } }\)	\(\mathrm { M } _ { \mathrm { c } }\)	\(\mathrm { R } _ { 120 }\)	\(\mathrm { R } _ { 240 }\)
   I
   \(\mathrm { M } _ { \mathrm { a } }\)
   \(\mathrm { M } _ { \mathrm { b } }\)
   \(\mathrm { M } _ { \mathrm { c } }\)
   \(\mathrm { R } _ { 120 }\)
   \(\mathrm { R } _ { 240 }\)					I

2. Complete the copy of this table in the Printed Answer Booklet. You can use some or all of the spare copies of the diagram in the Printed Answer Booklet to help.
3. Explain why there can be no subgroup of \(( \mathrm { G } , \circ )\) of order 4.
4. A student makes the following claim.
   "If all the proper non-trivial subgroups of a group are abelian then the group itself is abelian."
   Explain why the claim is incorrect, justifying your answer fully.
5. With reference to the order of elements in the groups, explain why ( \(\mathrm { G } , \circ\) ) is not isomorphic to \(\mathrm { C } _ { 6 }\), the cyclic group of order 6 .

1. 1. The polynomial \(\mathrm { F } ( x )\) is a quartic such that

$$\mathrm { F } ( x ) = p x ^ { 4 } + q x ^ { 3 } + 2 x ^ { 2 } + r x + s$$ where \(p , q , r\) and \(s\) are distinct constants.
Determine the number of possible quartics given that

1. the constants \(p , q , r\) and \(s\) belong to the set \(\{ - 4 , - 2,1,3,5 \}\)
2. the constants \(p , q , r\) and \(s\) belong to the set \(\{ - 4 , - 2,0,1,3,5 \}\) (ii) A 3-digit positive integer \(N = a b c\) has the following properties
   • \(N\) is divisible by 11
   • the sum of the digits of \(N\) is even
   • \(N \equiv 8 \bmod 9\)
   • Use the first two properties to show that
   $$a - b + c = 0$$
3. Hence determine all possible integers \(N\), showing all your working and reasoning.

1. 1. A security code is made up of 4 numerical digits followed by 3 distinct uppercase letters.

Given that the digits must be from the set \(\{ 1,2,3,4,5 \}\) and the letters from the set \{A, B, C, D\}

1. determine the total number of possible codes using this system. To enable more codes to be generated, the system is adapted so that the 3 letters can appear anywhere in the code but no letter can be next to another letter.
2. Determine the increase in the number of codes using this adapted system.
   (ii) A combination lock code consists of four distinct digits that can be read as a positive integer, \(N = a b c d\), satisfying
   • all the digits are odd
   • \(\quad N\) is divisible by 9
   • the digits appear in either ascending or descending order
   • \(\quad N \equiv e ( \bmod a b )\) where \(a b\) is read as a two-digit number and \(e\) is the odd digit that is not used in the code
   • Use the first two properties to determine the four digits used in the code.
   • Hence determine the code on the lock.

1

1. (a) Show that the number of arrangements of 25 distinct objects is an integer multiple of \(5 ^ { 6 }\).
   (b) Explain how this shows that the number of arrangements of 25 distinct objects is a whole number of millions.
2. (a) Calculate the values of

6 The network below has 11 vertices and 16 edges connecting some pairs of vertices. The numbers on the edges are their weights. The weight of the edge \(D G\) is given in terms of \(x\). There are three routes from \(A\) to \(K\) that have the same minimum total weight. \includegraphics[max width=\textwidth, alt={}, center]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-16_863_1444_552_299} Working backwards from \(\boldsymbol { K }\), use dynamic programming, to find:

1. the minimum total weight from \(A\) to \(K\);
2. the value of \(x\);
3. the three routes corresponding to the minimum total weight. You must complete the table opposite as your solution.
   [0pt] [12 marks] \section*{Answer space for question 6}

   Stage	State	From	Calculation	Value
   1	I	K
   	\(J\)	K

7 The table shows the times taken, in minutes, by four people, \(A , B , C\) and \(D\), to carry out the tasks \(W , X , Y\) and \(Z\). Some of the times are subject to the same delay of \(x\) minutes, where \(4 < x < 11\).

3 In the London 2012 Olympics, the Jamaican \(4 \times 100\) metres relay team set a world record time of 36.84 seconds. Athletes take different times to run each of the four legs.
The coach of a national athletics team has five athletes available for a major championship. The lowest times that the five athletes take to cover each of the four legs is given in the table below. The coach is to allocate a different athlete from the five available athletes, \(A , B , C , D\) and \(E\), to each of the four legs to produce the lowest total time. Use the Hungarian algorithm, by reducing the columns first, to assign an athlete to each leg so that the total time of the four athletes is minimised. State the allocation of the athletes to the four legs and the total time.
[0pt] [11 marks]

5 Tom is going on a driving holiday and wishes to drive from \(A\) to \(K\).
The network below shows a system of roads. The number on each edge represents the maximum altitude of the road, in hundreds of metres above sea level. Tom wants to ensure that the maximum altitude of any road along the route from \(A\) to \(K\) is minimised. \includegraphics[max width=\textwidth, alt={}, center]{b0f9523e-51dd-495f-99ec-4724243b5619-14_1522_1363_660_342}

1. Working backwards from \(\boldsymbol { K }\), use dynamic programming to find the optimal route when driving from \(A\) to \(K\). You must complete the table opposite as your solution.
2. Tom finds that the road \(C F\) is blocked. Find Tom's new optimal route and the maximum altitude of any road on this route.
   [0pt] [2 marks] \section*{Answer space for question 5}

   Stage	State	From	Value
   1	H	\(K\)
   	I	\(K\)
   	\(J\)	\(K\)
   2

   1. Optimal route is \(\_\_\_\_\)
   2. Tom's route is \(\_\_\_\_\) Maximum altitude is \(\_\_\_\_\) Figure 4 below shows a network of pipes.
      The capacity of each pipe is given by the number not circled on each edge. The numbers in circles represent an initial flow. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{b0f9523e-51dd-495f-99ec-4724243b5619-18_1039_1623_561_191}
      \end{figure}
   3. Find the value of the initial flow.
   4. 1. Use the initial flow and the labelling procedure on Figure 5 to find the maximum flow through the network. You should indicate any flow-augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
      2. State the value of the maximum flow and, on Figure 6, illustrate a possible flow along each edge corresponding to this maximum flow.
   5. Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut.
   6. On a particular day, there is a restriction at vertex \(G\) which allows a maximum flow through \(G\) of 30 . Find, by inspection, the maximum flow through the network on this day.
   7. Initial flow \(=\) \(\_\_\_\_\)
   8. 1. Figure 5 \includegraphics[max width=\textwidth, alt={}, center]{b0f9523e-51dd-495f-99ec-4724243b5619-19_2158_1559_543_296} \(7 \quad\) Arsene and Jose play a zero-sum game. The game is represented by the following pay-off matrix for Arsene, where \(x\) is a constant. The value of the game is 2.5 .

         Jose
         \cline { 2 - 4 }	Strategy	C	D
         \cline { 2 - 4 } Arsene	A	\(x + 3\)	1
         \cline { 2 - 4 }	B	\(x + 1\)	3
         \cline { 2 - 4 }
         \cline { 2 - 4 }

   9. Find the optimal mixed strategy for Arsene.
   10. Find the value of \(x\).
       \includegraphics[max width=\textwidth, alt={}]{b0f9523e-51dd-495f-99ec-4724243b5619-22_1636_1707_1071_153}
       \includegraphics[max width=\textwidth, alt={}]{b0f9523e-51dd-495f-99ec-4724243b5619-24_2288_1705_221_155}

2 Alan, Beth, Callum, Diane and Ethan work for a restaurant chain. The costs, in pounds, for the five people to travel to each of five different restaurants are recorded in the table below. Alan cannot travel to restaurant 1 and Beth cannot travel to restaurants 3 and 5, as indicated by the asterisks in the table.

5 Robert is planning to renovate four houses, \(A , B , C\) and \(D\), at the rate of one per month. The houses can be renovated in any order but the costs will vary because some of the materials left over from renovating one house can be used for the next one. The expected profits, in hundreds of pounds, are given in the table below.

3. \begin{figure}[h] \end{figure} The network in Fig. 2 shows possible routes that an aircraft can take from \(S\) to \(T\). The numbers on the directed arcs give the amount of fuel used on that part of the route, in appropriate units. The airline wishes to choose the route for which the maximum amount of fuel used on any part of the route is as small as possible. This is the rninimax route.

1. Complete the table in the answer booklet.
   (8)
2. Hence obtain the minimax route from \(S\) to \(T\) and state the maximum amount of fuel used on any part of this route.
   (2)