7.01e Permutations: ordered subsets of r from n elements

2 A project is represented by the activity network and cascade chart below. The table showing the number of workers needed for each activity is incomplete. Each activity needs at least 1 worker. \includegraphics[max width=\textwidth, alt={}, center]{7717b4ca-45ab-4111-9f59-5a3abb04b388-2_202_565_1605_201} \includegraphics[max width=\textwidth, alt={}, center]{7717b4ca-45ab-4111-9f59-5a3abb04b388-2_328_560_1548_820}

1. Complete the table in the Printed Answer Booklet to show the immediate predecessors for each activity.
2. Calculate the latest start time for each non-critical activity. The minimum number of workers needed is 5 .
3. What type of problem (existence, construction, enumeration or optimisation) is the allocation of a number of workers to the activities? There are 8 workers available who can do activities A and B .
4. 1. Find the number of ways that the workers for activity A can be chosen.
   2. When the workers have been chosen for activity A , find the total number of ways of choosing the workers for activity B for all the different possible values of x , where \(\mathrm { x } \geqslant 1\).

4 The first 20 consecutive positive integers include the 8 prime numbers \(2,3,5,7,11,13,17\) and 19. Emma randomly chooses 5 distinct numbers from the first 20 consecutive positive integers. The order in which Emma chooses the numbers does not matter.

1. Calculate the number of possibilities in which Emma's 5 numbers include exactly 2 prime numbers and 3 non-prime numbers.
2. Calculate the number of possibilities in which Emma's 5 numbers include at least 2 prime numbers. The pairs \(\{ 3,13 \}\) and \(\{ 7,17 \}\) each consist of numbers with a difference of exactly 10 .
3. Calculate the number of possibilities in which Emma's 5 numbers include at least one pair of prime numbers in which the difference between them is exactly 10 . A new set of 20 consecutive positive integers, each with at least two digits, is chosen. This set of 20 numbers contains 5 prime numbers.
4. Use the pigeonhole principle to show that there is at least one pair of these prime numbers for which the difference between them is exactly 10 .

4

1. Show that there are 127 ways to partition a set of 8 distinct elements into two non-empty subsets. A group of 8 people ( \(\mathrm { A } , \mathrm { B } , \ldots\) ) have 8 reserved seats ( \(1,2 , \ldots\) ) on a coach. Seat 1 is reserved for person A , seat 2 for person B , and so on. The reserved seats are labelled but the individual people do not know which seat has been reserved for them. The first 4 people, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , choose their seats at random from the 8 reserved seats.
2. Determine how many different arrangements there are for the seats chosen by \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D . The group organiser moves \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D to their correct seats (A in seat \(1 , \mathrm {~B}\) in seat \(2 , \mathrm { C }\) in seat 3 and D in seat 4).
   The other 4 people ( \(\mathrm { E } , \mathrm { F } , \mathrm { G }\) and H ) then choose their seats at random from the remaining 4 reserved seats ( \(5,6,7\) and 8 ).
3. List the 9 derangements of \(\{ \mathrm { E } , \mathrm { F } , \mathrm { G } , \mathrm { H } \}\), where none of these four people is in the seat that has been reserved for them. Suppose, instead, that the 8 people had chosen their seats at random from the 8 reserved seats, without the organiser intervening.
4. Determine the total number of ways in which the seats can be chosen so that 4 of the people are in their correct seats and 4 are not in their correct seats.

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

1. How many different ways are there to pair the letters with the envelopes?
2. Find the number of arrangements with exactly three letters in the correct envelopes.
3. (a) Show that there are two derangements of the three symbols A , B and C .
   (b) Hence find the number of arrangements with exactly two letters in the correct envelopes. Let \(\mathrm { D } _ { n }\) represent the number of derangements of \(n\) symbols.
4. Explain why \(\mathrm { D } _ { n } = ( n - 1 ) \times \left( \mathrm { D } _ { n - 1 } + \mathrm { D } _ { n - 2 } \right)\).
5. Find the number of ways in which all five letters are in the wrong envelopes.

1. (i) Use the Euclidean algorithm to find the highest common factor of 602 and 161.

Show each step of the algorithm.
(ii) The digits which can be used in a security code are the numbers \(1,2,3,4,5,6,7,8\) and 9. Originally the code used consisted of two distinct odd digits, followed by three distinct even digits. To enable more codes to be generated, a new system is devised. This uses two distinct even digits, followed by any three other distinct digits. No digits are repeated. Find the increase in the number of possible codes which results from using the new system.

5

1. How many arcs does the complete bipartite graph \(K _ { 5,5 }\) have? A subgraph of \(K _ { 5,5 }\) contains 5 arcs joining each of the elements of the set \(\{ 1,2,3,4,5 \}\) to an element in a permutation of the set \(\{ 1,2,3,4,5 \}\). Suppose that \(r\) is connected to \(p ( r )\) for \(r = 1,2,3,4,5\).
2. How many permutations would have \(p ( 1 ) \neq 1\) ?
3. Using the pigeonhole principle, show that for every permutation of \(\{ 1,2,3,4,5 \}\), the product \(\Pi _ { r = 1 } ^ { 5 } ( r - p ( r ) )\) is even (i.e. an integer multiple of 2, including 0 ).
4. Is the result in part (iii) true when the permutation is of the set \(\{ 1,2,3,4,5,6 \}\) ? Give a reason for your answer.

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

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