C%29 Combinatorics - Worksheet 2

Combinatorics Worksheet 2 – More Counting Problems All SMC, BMO and Mentoring problems are © UKMT (www.ukmt.org.uk) For question 1, refer to Tip 3 in Part 2 of the Combinatorics slides for help. For question 3, refer to Tips 1 and 2. For questions 4 and 5, Tip 6. 1. How many ways are there of arranging eight different books on a shelf, if: a. You must keep the four red ones separate? b. You must keep the four red ones separate but in alphabetical order by author? 2. How many orderings are there for a deck of 52 cards if all the cards of the same suit are together? (Note: leave your answer as an expression involving factorials, as the value is huge!) 3. [SMC] A hockey team consists of 1 goalkeeper, 4 defenders, 4 midfielders and 2 forwards. There are 4 substitutes: 1 goalkeeper, 1 defender, 1 midfielder and 1 forward. A substitute may only replace a player of the same category e.g.: midfielder for midfielder. Given that a maximum of 3 substitutes may be used and that there are still 11 players on the pitch at the end, how many different teams could finish the game? A 110 B 118 C 121 D 125 E 132

4. [SMC Level 5/5] A postman's sack contains five letters, one each for the five houses in Cayley Close. Mischievously, he posts one letter through each door without looking to see if it is the correct address. In how many different ways could he do this so that exactly two of the five houses receive the correct letters? A 5 B 10 C 20 D 30 E 60 5. [BMO Round 1] The number 916238457 is an example of a nine-digit number which contains each of the digits 1 to 9 exactly once. It also has the property that the digits 1 to 5 occur in their natural order, while the digits 1 to 6 do not. How many such numbers are there? 6. [STEP] Three married couples sit down at a round table at which there are six chairs. All of the possible seating arrangements of the six people are equally likely. 2 a. Show that the probability that each husband sits next to his wife is . 15 b. Find the probability that exactly two husbands sit next to their wives. c. Find the probability that no husband sits next to his wife.

www.drfrostmaths.com/rzc

Combinatorics Worksheet 2 – More Counting Problems - ANSWERS 1. Answers: a. Allocate 4 slots for non-red books first. There’s (54) = 5 ways of choosing four of the five gaps around these slots to put the slots for red books. Then there’s 4! ways of organising the red books within these slots, and similarly 4! ways for the non-red books. That’s 5 × (4!)2 = 2880 ways. b. The only difference is that we no longer need to consider the possible arrangements of red books, since their order is determined. That’s 5 × 4! = 5! = 120 ways. 2. Imagine the cards in a line. We have 4 blocks of cards (where the cards in each block have the same suit). There’s 4! ways in which suits can be allocated to these blocks. Then (13!)4 ways in which the cards can be arranged within each suit. That’s 4! × (13!)4 ways. 3. Answer B: (Official solution) Firstly, we note that of the players on the pitch at the end of the game, the goalkeeper is one of two players; the four defenders form one of five different possible combinations, as do the four midfielders, and the two forwards form one of three different possible combinations. So, if up to four substitutes were allowed, the number of different teams which could finish the game would be 2 × 5 × 5 × 3, that is 150. From this number we must subtract the number of these teams which require four substitutions to be made. This is 1 × 4 × 4 × 2, that is 32, so the required number of teams is 118. 4. Answer C: (Official solution) Let the letters be p, q, r, s, t and the corresponding houses be P, 5! Q, R, S, T. The number of ways of correctly putting in two letters is = 10. For the third 2!3! letter, there are just two wrong choices and then the others are fixed. (If p, q have been correctly delivered, then clearly r can go to S or T. If r is put to S then t must go to R and s to T. If r is put to T then t must go to S and s to R.) So there are just 2 × 10 = 20 ways. 5. JAF’s solution: One way is to start with the 1 2 3 4 5 in that order. We want to now insert the other numbers into the sequence. We can insert the number 6 in five different places such that it doesn’t come after the 5. We have (96) of then picking six out of the nine number slots to put these numbers in. Finally, we have 3! arrangements of the 7, 8 and 9 into the three remaining slots. That gives 5 × (96) × 3! = 2520. An alternative strategy is to start by inserting the 9 into the sequence (which can go in 9 places), then the 8 (which can go in 8 of the remaining places), then the 7 (in 7 places). The 6 is not allowed to go in the last slot of the remaining places, so there’s 5 places it can go. Then the other numbers are fixed because 1 to 5 have to be ordered. That gives 9 × 8 × 7 × 5 = 2520. 6. Note that my method differs slightly to the one given in the official STEP solutions, which you can find here: http://www.mathshelper.co.uk/STEP%202008%20Solutions.pdf. There are a multitude of different strategies for solving these kinds of problems. Whichever you choose, care should be taken to avoid either overcounting or missing arrangements. a. There are 6! ways of arranging the people in the chairs. Note that we’re assuming the orientation of the table is significant, e.g. were everyone to move one position clockwise, it would be considered a distinct arrangement. Similar to the ‘sisters/non-sisters’ problems, we allocate chairs for a particular purpose, i.e. pairs for a particular couple to sit in. There’s 6 ways in which we could www.drfrostmaths.com/rzc

allocate chairs for the first couple. Then for the second couple, there’s only 2 places we can choose (i.e. either to the first couple’s left or to their right). Now that we have the chairs labelled for each couple, we have 2! = 2 ways of arranging the members of each couple in their allocated chairs. Thus there’s (6 × 2) × (2!)3 = 96 96 2 ways of seating the couples. This gives us a probability: = . 6! 15 b. The only way we can separate the members of one couple (while keeping the other couples together) is if they are at opposite ends of the table. There’s three ways in which these couple’s seats can be chosen, which leaves the other seats naturally paired (at this stage, note that we’re only identifying pairs of seats, not what couples go into them). There’s 3! ways in which we can allocate the couples to these seat pairs. And then within each couple, there’s 2! ways in which the members of each 144 1 couple can be arranged. That’s 3 × 3! × (2!)3 = 144. Thus the probability is = . 720 5 c. We can use a similar strategy to before: (i) Find all the ways of pairing seats then (ii) associate a couple with the pair and finally (iii) consider the arrangement of each couple’s members. For stage one, we could either have all couple’s members sitting directly opposite each other (there’s 1 such arrangement) or just one couple sitting directly opposite each other and the other two separated by one person (there’s 3 such arrangements – see the diagram). For stage two, for all four of these possible seat pairings, there’s 3! ways of allocating couples to these pairs. Finally, there’s (2!)3 ways of organising the people within each couple. This gives 4 × 3! × (2!)3 = 192 4 192. The probability is thus = . 720

www.drfrostmaths.com/rzc

15