Illinois State University Mathematics Department


MAT 405: Combinatorics Topics for K-8 Teachers

Summer 2006


Semester Exam: Possible Solutions

 

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?

Solution: 17

(ii) How many unique ways exist to complete Task Y and then Task X?

Solution: 60

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?

Solution: 7!

c. How many distinct arrangements exist for the letters in the word DILLYDALLY?

Solution: 10!/(2!4!2!)

d. How many unique ways exist to arrange 24 identical dimes in a line such that 15 of them are heads up?

Solution: C(24,15)

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: C(15,2)

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?

Solution: 120

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?

Solution: 18!/(4!6!8!)

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?

Solution: 8*10^9

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?

Solution: C(39,3)

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: C(18,10)*C(18,10)=[C(18,10)]^2

3.

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. A recursive relationship has first term a(1) = 6 with a(n) = 3a(n-1) - 4. Determine the value of a(5).

Solution: a(5)=326

b. Julio had to answer the following question:

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?

Solution: 58

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

Solution: D(k)=k!(1/0! - 1/1! + 1/2! - . . . +(-1)^k/k!)

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?

Solution: 5th degree

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

Solution: x=23, y=39, z=39

4.

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

a. Determine the number of collected terms in the expansion. (2 points)

Solution: C(103,4)

b. Determine the number of uncollected terms in the expansion. (2 points)

Solution: 5^99

c. Determine the coefficient M for the collected term M*p^22*r^33*d^44. (2 points)

Solution: 99!/(22!33!44!)

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: C(5,3)*C(101,2)

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: Use the pigeonhole principle. The worst case scenario is that for the first 125 grade assignments, there are 25 A grades, 25 B grades, 25 C grades, 25 D grades, and 25 F grades. The assignment of a letter grade to the 126th student must be to one of the 5 letter-grade categories, so by the PHP there must be a letter grade that no less than 26 students have earned.

6.

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

Solution: C(58,24)*5^34

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)

Solution:
(i) C(17,8)*C(8,1) = 17!/(9!8!) * 8!/(7!1!) = 17!/(9!7!1!) = 17!/(9!7!)
(ii) 17*C(16,7) = 17*16!/(9!7!) = (17*16!)/(9!7!) = 17!/(9!7!)
So (i) and (ii) are equivalent expressions.

(b) Use arithmetic to show that (iii) and (iv) are equivalent. (2 points)

Solution:
(iii) P(17,1)*C(16,7) = 17!/16! * 16!/(9!7!) = 17!/(9!7!)
(iv) C(17,8)*P(8,1) = 17!/(9!8!) * 8!/7! = 17!/(9!7!)
So (iii) and (iv) are equivalent expressions.
(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:

(i) Select 8 from the group of 17, arrangement not important. From the 8, choose 1 as team captain, again with arrangment not of concern.

(ii) Choose a captain from among the 17 students. Now, from remaining 16 students, select 7 to complete the team, with their arrangement not important.

(iii) Same as (ii) where P(17,1) represents selecting 1 from 17.

(iv) Same as (i) where P(8,1) represents choosing one from the group of 8.

(v) Same as (i).

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)

Solution:
Recursive Relationship: R(n) = R(n-1) + 4, where R(1) = 60.
Explict formula: R(n) = 4n + 56.
R(16) = 120

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:
Recursive Relationship: S(n) = S(n-1) + (4n+56), where S(1) = 60.
Explict formula: S(n) = 2n^2 + 58n.
S(20) = 1960

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)

Solution: This is a 3rd-degree polynomial, based o nthe data at hand, because a constant difference first apppears in line D3.

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:f(x) = x^3 + 2x^2 - x + 4

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)

Solution: Show that the conjecture is true for the case when n=1.

LS: 1*2 = 2

RS: [1(4-1)(1+1)]/3 = 6/3 = 2

The LS equals the RS. The conjecture holds when n=1.

b. State and carry out the second step in the induction process. (3 points)

Solution: Assume that the conjecture is true for the case when n=k.

Assume that 1*2+3*4+5*6+7*8+...+(2k-1)(2k)=[k(4k-1)(k+1)]/3

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: Show that the conjecture is true when n = k+1, using the assumption made in the previous step.

Write out the LS and RS of this conjecture and manipulate one or both sides until LS = RS, at some point using assumption from Step 2.

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?

Solution: Keep trying!

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