Correct ordering probability

3

1. There are 5 runners in a race. How many different finishing orders are possible? [You should assume that there are no 'dead heats', where two runners are given the same position.] For the remainder of this question you should assume that all finishing orders are equally likely.
2. The runners are denoted by \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\). Find the probability that they either finish in the order ABCDE or in the order EDCBA.
3. Find the probability that the first 3 runners to finish are \(\mathrm { A } , \mathrm { B }\) and C , in that order.
4. Find the probability that the first 3 runners to finish are \(\mathrm { A } , \mathrm { B }\) and C , in any order.

8 Alex claims that he can read people's minds. A volunteer, Jane, arranges the integers 1 to \(n\) in an order of Jane's own choice and Alex tells Jane what order he believes was chosen. They agree that Alex's claim will be accepted if he gets the order completely correct or if he gets the order correct apart from two numbers which are the wrong way round. They use a value of \(n\) such that, if Alex chooses the order of the integers at random, the probability that Alex’s claim will be accepted is less than \(1 \%\). Determine the smallest possible value of \(n\). \section*{END OF QUESTION PAPER}

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.

12. Alex claims that he can read people's minds. A volunteer, Jane, arranges the integers 1 to \(n\) in an order of Jane's own choice and Alex tells Jane what order he believes was chosen. They agree that Alex's claim will be accepted if he gets the order completely correct or if he gets the order correct apart from two numbers which are the wrong way round. They use a value of \(n\) such that, if Alex chooses the order of the integers at random, the probability that Alex's claim will be accepted is less than \(1 \%\). Determine the smallest possible value of \(n\).