Illinois State University Mathematics Department

 MAT 305: Combinatorics Topics for K-8 Teachers Spring 2001 Dr. Roger Day (day@ilstu.edu)

 Possible Solutions: Test #3

Please write your solutions on one side only of each piece of paper you use, and please begin each solution on a new sheet of paper. You may use factorial notation as well as combination and permutation notation where appropriate (i.e., there is no need to expand 24!).

You are to work alone on this take-home test. You may not use anyone else's work nor may you refer to any materials as you complete the test. You may contact me with your questions. Signing or writing your name in the space below will indicate that you have complied with these restrictions.

Evaluation Criteria

You may earn up to 10 points on each of questions 1 through 6. For each question:

• 6 points count toward a correct solution to the problem. I will evaluate the mathematics you use:
• Is it accurate and appropriate?
• Have you provided adequate justification?
• 4 points count toward how you express your solution. I will evaluate how you communicate your results:
• Is your solution clear and complete?
• Have you expressed logical connections among components of your solution?
 1 Respond to each of these questions. While you may show steps leading to your solution, you do not need to generate written explanations for questions (a) through (e) on this page. (2 points each) (a) What value r satisfies the equation C(42,19) = C(42,r)? Solution: r = 23 (b) How many different arrangements exist for the letters in the word antivivisectionist? Solution: 18!/(2!3!5!2!2!) In the expansion of (v+w+x+y+x)^20 , state: (c) the number of uncollected terms, Solution: 5^20 (d) the number of collected terms, Solution: C(24,4) (e) the coefficient T in the collected term Tv^13wy^2z^4. Solution: 20!/(13!1!0!2!4!) 2 Solve each of the following counting problems. (2 points each) (a) You are ordering a 5-course dinner at a fancy restaurant. For each course, you have 7 choices. How many different dinners can you order? Solution: 7^5 (b) Ten people arrive for a casting call and four are chosen, to play the roles of Annie, Bud, Cathy, and Dianne, respectively. In how many ways can such a cast be created from the 10 people who arrived? Solution: P(10,4) (c) From a room containing 13 people, choose a team of 5 people and designate one as a team captain. In how many ways can this be done? Solution: C(13,5)*5 = 13*C(12,4) (d) From a pool of 17 girls and 10 boys, how many ways can you create a team of 8 girls and 2 boys? Solution: C(17,8) * C(10,2) (e) From a room filled with 17 people, how many ways can you create a team consisting of 3 or 4 people? Solution: C(17,3) + C(17,4) 3 Determine the number of different arrangements of AABBCCDDEE such that each of the following conditions holds. Each of (a), (b), and (c) is a separate and independent problem. (a) The two As appear next to each other. (3 points) Solution: 9!/(2!2!2!2!) (b) The two As are separated. (3 points) Solution: 8!/(2!2!2!2!) * C(9,2) (c) The four vowels (A, A, E, E) are all separated. (4 points) Solution: 6!/(2!2!2!) * P(7,4)/(2!2!) 4 Ten dogs come upon eight biscuits, and dogs do not share biscuits! (a) In how many different ways can the biscuits be consumed by the dogs, assuming the dogs are distinguishable but the biscuits are not? (5 points) Solution: C(17,9) Let d(i) represent the number of biscuits eaten by the ith dog, where 0 � i � 10. Then we seek the number on non-negative interger solutions to d(1)+d(2)+…+d(10) = 8. (b) In how many different ways can the biscuits be consumed by the dogs, assuming both the dogs and the biscuits are distinguishable? (5 points) Solution: 10^8 For each of the 8 biscuits, there are 10 possible dogs that could have eaten the biscuit. 5 (a) Stacey and Petra are among 10 different women standing in line to enter a theatre. There are exactly 2 people between Stacey and Petra. In how many ways can such a line-up occur? (5 points) Solution: 2 * 7 * 8! Stacey (S) and Petra (P), together with the two people between them, make up a fixed unit. With the four people fixed through this requirement, there are six others to account for, or a total of 7 "spots" in the line-up. First, choose one of the seven spots for the 4-person unit. This can be done in 7 ways. Now, using the six other spots and the two between S and P, permute the 8 other people into these 8 spots. This can be done in 8! ways. Finally, recognize that P and S could change places, thus there are two ways for S and P to arrange each other within the four-person unit. (b) Generalize your solution to the problem above for Stacey and Petra being among n different women standing in line to enter a theatre, with exactly k people between Stacey and Petra. (5 points) Solution: 2*(n-k-1)(n-2)! Stacey (S) and Petra (P), together with the k people between them, make up a fixed unit. With the k+2 people fixed through this requirement, there are n-(k+2) others to account for, or a total of n-(k+2)+1 = n-k-1 "spots" in the line-up. First, choose one of the n-k-1 spots for the (k+2)-person unit. This can be done in n-k-1 ways. Now, using the n-(k+2) other spots and the k between S and P, permute the n-2 other people into these n-2 spots. This can be done in (n-2)! ways. Finally, recognize that P and S could change places, thus there are two ways for S and P to arrange each other within the (k+2)-person unit. 6 Two soccer teams play until one team scores 10 points. The judges write down on a score sheet a record of how the score changes. For example, a score sheet might look like this: 1/0, 1/1, 1/2, 1/3, 1/4, 2/4, 2/5, 2/6, 3/6, 4/6, 5/6, 6/6, 7/6, 8/6, 9/6, 9/7, 10/7 How many different score sheets can be obtained? Solution: 2[C(9,9)+C(10,9)+C(11,9)+…+C(18,9)] Think about this as a modification or application of a grid problem. A "path" passes through integer ordered pairs (x,y), starting at the origin (0,0) and ending at either (a) an ordered pair on the line y = 10, with x an integer ranging from 0 to 9, or (b) an ordered pair on the line x = 10, with y an integer ranging from 0 to 9. We just need to count the paths, using the grid-problem strategy, required to get to each of these ending points. The only way to get to (x,10) or (10,y), for x <= 9 and y <=9, is to get there from (x,9) or from (9,y), respectively. That is, once the value "10" is reached, there is no more moving along the horizontal line y=10 or the vertical line x=10. As soon as a team scores 10, the match is over. The picture below may help illustrate this. Syllabus Grades & Grading Content Notes Session Outlines Assignments and Problem Sets Tests and Quizzes