Illinois State University Mathematics Department
MAT 405: Combinatorics Topics for K8 Teachers Summer 2006 
Possible Solutions 
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 test. You may not use anyone else's work nor may you refer to any materials as you complete the test. You may ask me questions.
Evaluation Criteria
You may earn up to 10 points on each of questions 1 through 10. 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?
The BONUS! question is worth 10 points.
1. 
Respond to each of these questions by placing your solution in the blank. While you may show steps leading to your solution, you do not need to generate written explanations for questions (a) through (e). (2 points each)


2. 
Respond to each question below by placing your solution in the blank. 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)


3. 
Respond to each question below by placing your solution in the blank. 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)


4. 
Consider the expansion of (p + r + i + d + e)^99.


5. 
Ms Glorininininia reviewed her records at the end of the school year and found that she had assigned grades to 126 students. Her grade assignments all came from the set {A,B,C,D,F} with no plus or minus grades. Explain why no less than 26 of these 126 students must have earned the same grade from Ms Glorininininia. 

6. 
Fiftyeight (58) distinct fair dice are rolled. How many ways are there for exactly twentyfour 3s to appear? 

7. 
On a previous test in MAT 305/409, the following question was posed.
Here are some of the correct answers that were submitted:
(a) Use arithmetic to show that (i) and (ii) are equivalent. (2 points) (b) Use arithmetic to show that (iii) and (iv) are equivalent. (2 points) (c) Choose four of the five correct solutions and, referring to the context of the problem, explain why each is a correct solution. DO NOT simply show that the expressions are equal in numerical value. (6 points) 

8. 
Suppose that Hodge Pole and the Sprucers are playing at the Pine Tree Theater. The theater has one section of seats, arranged with 60 seats in the first (front) row, 64 seats in the second row, 68 seats in the third row, and so on, for a total of 20 rows. The seats are numbered from left to right, with the first seat in the first row being #1, the first seat in the second row #61, and so on. a. Write both a recurrence relation and an explicit formula for R(n), the number of seats in Row n. Be sure to include information about initial conditions. Use your results to determine the number of seats in the 16th row. (6 points) b. Write either an explicit formula or a recurrence relation for S(n), the sum of all seats through Row n. Use that to determine the total number of seats in the Pine Tree Theater. (4 points) 

9. 
Use this difference table for parts (a) and (b).
a. Complete as many open rows of the table (D1, D2, D3, D4) as necessary to determine the type of polynomial function that will model the relationship between the values in the first two lines of the table (x and f(x)). Write a brief explanation describing how you know what type of function this will be. (4 points) b. Use the information in the difference table to generate an explicit formula for the relationship between the values in the first two lines of the table, that is, between x and f(x). (6 points) 

10. 
The following conjecture is to be proven true by induction or shown to be false using a counterexample: 1*2+3*4+5*6+7*8+...+(2n1)(2n)=[n(4n1)(n+1)]/3 a. State and carry out the first step in the induction process. (3 points) b. State and carry out the second step in the induction process. (3 points) c. State the third step in the induction process. Do not carry out this step, but do describe the general process you would use in this step. (4 points) 

BONUS! 
Exactly 12 chocolate chips are to be distributed at random into 9 chocolatechip cookies. What is the probability that some cookie has at least 4 chips in it? (10 points) 





