7.01g Arrangements in a line: with repetition and restriction

2 Mo eats exactly 6 doughnuts in 4 days.

1. What does the pigeonhole principle tell you about the number of doughnuts Mo eats in a day? Mo eats exactly 6 doughnuts in 4 days, eating at least 1 doughnut each day.
2. Show that there must be either two consecutive days or three consecutive days on which Mo eats a total of exactly 4 doughnuts. Mo eats exactly 3 identical jam doughnuts and exactly 3 identical iced doughnuts over the 4 days.
   The number of jam doughnuts eaten on the four days is recorded as a list, for example \(1,0,2,0\). The number of iced doughnuts eaten is not recorded.
3. Show that 20 different such lists are possible.

1 Alfie has a set of 15 cards numbered consecutively from 1 to 15.
He chooses two of the cards.

1. How many different sets of two cards are possible? Alfie places the two cards side by side to form a number with 2,3 or 4 digits.
2. Explain why there are fewer than \({ } ^ { 15 } \mathrm { P } _ { 2 } = 210\) possible numbers that can be made.
3. Explain why, with these cards, 1 is the lead digit more often than any other digit. Alfie makes the number 113, which is a 3-digit prime number. Alfie says that the problem of working out how many 3-digit prime numbers can be made using two of the cards is a construction problem, because he is trying to find all of them.
4. Explain why Alfie is wrong to say this is a construction problem.

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

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 Alfred has bought six different chocolate bars. He wants to give a chocolate bar to each of his six friends. The table gives the names of the friends and indicates which of Alfred's six chocolate bars they like.