Illinois State University Mathematics Department

 MAT 405: Combinatorics Topics for K-8 Teachers Summer 2006

 Semester Exam 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)

 a. There are 5 ways to complete Task X and 12 ways to complete Task Y. Assume that Task X and Task Y are independent events that share no common elements. (i) How many unique ways exist to complete Task X or Task Y? (ii) How many unique ways exist to complete Task Y and then Task X? b. Single copies of the letters A,C,E,G,I,K, and M are to be arranged in a single line. How many unique arrangements are there for these letters? c. How many distinct arrangements exist for the letters in the word DILLYDALLY? d. How many unique ways exist to arrange 24 identical dimes in a line such that 15 of them are heads up? e. Given an unlimited supply of letters F, U, and N to choose from, how many unique 15-letter sets can be created that contain at least 2 Ns?

solution

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)

 a. At Blaise's Bistro, the Sunday special is omelets. For \$8.99 plus tax, patrons choose one of 20 different omelets and one of 6 different beverages. No additions or substitutions are allowed for this price. How many different \$8.99 omelet/beverage options are there? b. Eighteen (18) donuts are to be placed in a single line on a serving tray. Among the 18 donuts, there are 4 identical jelly donuts, 6 identical chocolate donuts, and 8 identical cream-filled donuts. How many unique arrangements exist for these 18 donuts? c. One version of the current state identification number in North Dakota assigns a ten-digit number to each person. The first digit cannot be 0 or 9. How many unique ID numbers are possible? d. A group of 48 dogs are to be separated into four holding areas labeled H1, H2, H3, and H4. If there must be at least three dogs in each holding area, and we are only concerned with the number of dogs in each area, how many ways can the separation occur? e. Ernestine works for the phone company, 8 blocks east and 10 blocks north of her condo. All streets from her condo to her workplace are laid out in a rectangular grid, and all of them are available for walking. If she walks 18 blocks from her apartment to work and 18 blocks from work to her apartment, how many different round-trip paths are possible for Ernestine?

solution

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)

a. A recursive relationship has first term a(1) = 6 with a(n) = 3a(n-1) - 4. Determine the value of a(5).

Jane's Junkfood Jungle sells four different bulk-size salty snacks: cheese puffs that sell for \$4 a bag, popcorn that sells for \$5 per bucket, pretzels that sell for \$7 a sack, and corn chips that sell for \$8 each canister. How many ways are there to spend \$60 for these salty snacks at Jane's?

To answer the question, Julio created a generating function that, when expanded, included the following terms:

...+4x^16+ 3x^17+3x^18+4x^19+6x^20+5x^21+...
...+41x^52+40x^53+41x^54+44x^55+49x^56+48x^57+49x^58+52x^59+58x^60+...
...+95x^76+95x^77+97x^78+99x^79+105x^80+...

What correct answer should Julio provide, based on the expansion shown here?

c. State the explicit formula for the number of derangements of k distinct items.

d. Study this completed difference table:

 x 1 2 3 4 5 6 7 f(x) 2 5 10 29 80 189 392 D1 ---> 3 5 19 51 109 203 D2 ---> 2 14 32 58 94 D3 ---> 12 18 26 36 D4 ---> 6 8 10 D5---> 2 2

If we assume there exists a polynomial function that best represents the relationship between x and f(x), what is the degree of that polynomial?

e. Replace x, y, and z in C(40,x) = C(y,22) + C(z,23) to correctly illustrate Pascal's Formula.

solution

4.

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

 a. Determine the number of collected terms in the expansion. (2 points) b. Determine the number of uncollected terms in the expansion. (2 points) c. Determine the coefficient M for the collected term M*p^22*r^33*d^44. (2 points) d. How many unique collected terms in the expansion are of the form N*a^s*b^t*c^v, where a, b, and c are distinct elements from the set {p,r,i,d,e}, s, t, and v are positive integers, and N repreents any coefficient that fits thesituation? (4 points)

solution

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.

solution

6.

Fifty-eight (58) distinct fair dice are rolled. How many ways are there for exactly twenty-four 3s to appear?

solution

7.

On a previous test in MAT 305/409, the following question was posed.

• From a group of 17 different students, choose a team of 8 students and designate one of the 8 as team captain. In how many ways can this be done?

Here are some of the correct answers that were submitted:

• (i)  C(17,8)*C(8,1)
• (ii) 17*C(16,7)
• (iii) P(17,1)*C(16,7)
• (iv) C(17,8)*P(8,1)
• (v) C(17,8)*8

(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)

solution

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)

solution

9.

Use this difference table for parts (a) and (b).

 x 1 2 3 4 5 6 7 f(x) 6 18 46 96 174 286 438 D1 ---> D2 ---> D3 ---> D4 ---> D5--->

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)

solution

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+...+(2n-1)(2n)=[n(4n-1)(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)

solution

BONUS!

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

 Syllabus Grades & Grading Session Notes Assignments and Problem Sets Tests and Quizzes