STAT 418 MID-TERM EXAMINATION 1 SPRING, 2009NAME (in BLOCK letters): SOLUTIONSSIGNATURE:Student Number:Instructions:1. Please verify that your exam paper contains all seven questions.2. You may use a calculator and one sheet of notes, but you may not use any books.3. Illegible handwriting wil l not be g raded!4. To earn partial credit, explain your arguments carefully and show all your work. If youneed extra paper then please write on the back of your paper.5. Your instructor or teaching assistant will answer no questions during th e examinationperiod. Simply explain any error you may find in a question and proceed to the nextquestion.DO NOT WRITE BELOW THIS LINEQuestion Marks1234567TotalProblem 1. [This question is based on Problem 10, p. 16, in the textbook.]A group of 4 men and 5 women attend a dinner party at La Grenouille, a fancy restaurantin New York. In how many ways can the group be seated in a single row if:(a) There are no restrictions on the seating arrangement?(b) Ann and Bob must sit next to each other?(c) No 2 men or 2 women can sit next to each other?(d) The group consists of 4 married couples and 1 single woman, and each couple must beseated t ogether?(e) Jack and Jill, one of t he couples, refuse to sit together?Solution:(a) Because there are no restrict ions on the seating arrangement, there are 9 choices forthe first seat, after which there are 8 choices for the second seat, ..., after which there is1 choice for the last seat. By t he multiplication principle, there are9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 9!ways of seating all ni ne peopl e.(b) Because A nn and Bob must sit together, we wi ll regard Ann and Bob as one “unit”and the remaining persons as 7 “units.” Then, by the multiplication principle, there are8! ways to seat all eight units. For each of these 8! ways, Ann and Bob can be permutedamongst themselves in 2! ways. Therefore, there are 8! · 2! to seat everyone in such a waythat A nn and Bob a re seated together.(c) The first seat must be filled by a woman, then the next by a man, then the next by awoman, and so on. Therefore, there are 5 choices for the first seat and, once that seat isfilled, there are 4 choices for the second seat, and so on. Therefore, there are5 · 4 · 4 · 3 · 3 · 2 · 2 · 1 · 1 = 5! · 4!ways to seat them.(d) We treat each couple as one unit and the remaining woman as a unit. Then, there are5! ways to seat the units. Also, for each couple, there are 2! ways to seat them as a unit.Therefore, the number of ways is5! · 2! · 2! · 2! · 2! = 5! · (2!)4.(e) By part (a), there are 9! ways to seat everyone without restricti ons. Also, by part (b),there are 8! · 2! ways to seat them so that Jack and Jill are together. Therefore, there are9! − 8! 2!ways of seating them so that Jack and Jill are not together.Problem 2. [This question is based on Problems 9, 13, and 27, pp. 17-23 in the textbook .](a) If everyone in a group of twenty people shakes hands with everyone el se, how manyhandshakes have taken place?(b) In how many ways can a deck of 52 playing cards be divided into 4 groups, eachcontaining 13 cards?(c) Suppose that we construct seven-digit numbers from the integers 1, 2, . . . , 9. How manysuch numbers are there for which no two consecutive digits are the same?(d) How many five-digit numbers can be formed from the integers1, 2, . . . , 9 if no digitcan a ppear more than twice? (Thus, for i nsta nce, the number 41434 is not allowed.)Solution:(a) Each handshake consists of 2 people shaking hands. Therefore, the number of hand-shakes is the number of ways of choosing 2 people from the g roup of 20 people:!202"(b) This is the number of ways of dividing 52 cards into groups of 13, 13, 13, 13. Therefore,the number o f ways is the multinomi al coefficient#5213, 13, 13, 13$=52!13! 13! 13! 13 !Here is an alt ernat ive solutio n: The first group of 13 cards can be chosen in!5213"ways;once that group i s chosen, the second group of 13 cards can be chosen from the remaining39 cards i n!3913"ways; once the first two groups a re chosen, the third group of 13 cards canbe chosen from the remaining 26 cards in!2613"ways; and finally the l ast g roup of cards canbe chosen in!1313"= 1 way. Therefore, the number of ways all four groups can be chosen is#5213$·#3913$·#2613$·#1313$=52!13! 13! 13! 13 !(c) Because dig its cannot be repeated consecutively, there are 9 ways to choose the firstdigit, and then any other di git can be chosen in 8 ways. Therefore, the total number ofways is 9 · 86.(d) Because no digit can app ear more than twice then there are 3 cases: (i) No digit isrepeated (e.g., 246 89); (ii) A digit is repeated (e.g, 24682); (iii) Two di gits a re repeated(e.g, 24642 ).Case (i): We choose 5 di gits from the list of 9; this can be done in!95"ways; and thenthe chosen di gits can be permuted in 5! ways; hence there are!95"· 5! possible numbers.(Another way of doing this is: There are 9 ways to choose the first digit, t hen 8 ways tochoose the second digit, and so on; therefore, there are 9 · 8 · 7 · 6 · 5 possible numbers.)Case (ii): There are 9 ways to choose the digit t hat will be repeated. Once we choose thatdigit, there are!52"ways to choose the two places in the list where that digit will appear.Once we have placed that digit, there are 8 ways to choose the next dig it, then 7 ways forthe next, and then 6 ways for the last digit. Therefore, there are 9 ·!52"· 8 · 7 · 6 ways forCase (ii).Case (iii): There are!92"ways to choose the two digits that will be repeated. Once thosetwo digits are chosen, the remaining dig it can be chosen in!71"= 7 ways. The first pairof repeated digits can be placed in!52"ways; and after that, the second pair of repeateddigits can be placed in!32"ways; and finally the last digit can be placed in only 1 way.Therefore, there are!92"· 7 ·!52"·!32"ways for Case (iii).Finally, the total number of ways is:#95$· 5! + 9 ·#52$· 8 · 7 · 6+#92$· 7 ·#52$·#32$.Problem 3. [This question is based on Self-Test Problem 8 , p. 64, in the text book.]From a group of 3 freshmen, 4 sophomores, 5 juniors, and 6 seniors a commit tee of size 5is selected randomly. Find the probability that the committee consists of:(a) 1 person from each class.(b) 2 sophomores and 3 juniors.(c) Only sophomores or juniors.(d) Only sophomores.(e) At most one freshman (and any other class members).Solution:(a) Because it is not possible to form a 5 -person committee by choosing (exactly) 1