Illinois State University Mathematics Department

MAT 305: Combinatorics Topics for K-8 Teachers



Possible Solutions: Sample Semester Exam Questions


1.a

Replace a, b, c, and d in C(10,8) = C(a,b) + C(c,d) to illustrate Pascal's Formula.

C(10,8) = C(9,7) + C(9,8)

1.b

An individual's telephone number is made up of a 3-digit area code and a 7-digit local number. Until quite recently, the area code could not begin with 0 or 1, the area code was required to have a 0 or 1 as its middle digit, and the local number could not begin with 0 or 1. Under these conditions, how many 10-digit individual numbers were possible?

(8*2*10)(8*10*10*10*10*10*10)

1.c

A group of 11 people are to be separated into three rooms, A, B, and C, so that five are in room A, two are in room B, and four are in room C. In how many ways can this be done?

C(11,5)*C(6,2)*C(4,4)

1.d

A shelf is to contain 10 books, six indistinguishable paperback books and four indistinguishable hardback books. If the paperback books must be shelved in pairs (that is, exactly and only two paperback books must be adjacent to each other), in how many ways can the 10 books be arranged on an open shelf?

First, arrange the paperbacks into pairs. This can be done in C(6,2)*C(4,2)*C(2,2) ways. Now place the three pairs into the five spaces that exist among the four hardback books. This can be done in C(5,3) ways.

Therefore the total number of arrangements is C(6,2)*C(4,2)*C(2,2) * C(5,3).

1.e

Use symbol manipulation (algebra) to verify that .

Here are algebraic steps leading from the left expression to the right expression in the statement above.

.

2.

The following statement is to be proven true by induction:

What is the sum of the first n odd positive integers?

Write a conjecture, and then review the step-by-step induction process.

.

3.

Twenty-four distinct fair dice are rolled. How many ways are there for thirteen 6s to appear?

Think of the dice as numbered 1 through 24, or, equivalently, as appearing in some designated positions numbered 1 through 24. Now, as the dice appear in their designated positions, or as they are lined up according to their serial numbers 1 through 24, display the value of each die, 1 through 6.

In such a display, we are assured of showing exactly 13 6s. There are C(24,13) ways to pick out 13 of the 24 spots and display a 6 in each spot.

In each of the 11 remaining spots, there are five choices, namely, 1 through 5, for we cannot have any more 6s. So, there are 5^11 ways to fill the remaining 11 positions.

All in all, there are C(24,13)*(5^11) ways for thirteen 6s to appear when 24 distinct dice are rolled.

.

4.

Jan works 20 blocks east and 15 blocks north of her home. All streets from her home to her workplace are laid out in a rectangular grid, and all of them are available for walking. On her walk to work, Jan always stops at Benny's Bakery, located 6 blocks east and 4 blocks north of her home. On her way home from work, Jan always stops at Brink's Bank, located 5 blocks south and 2 blocks west of her workplace. If she walks 35 blocks from home to work and 35 blocks from work to home, how many different round-trip paths are possible for Jan?

Jan has C(10,4) paths to the bakery and then C(25,14) paths from there to work. She then has C(7,2) paths from work to the bank, with C(28,18) paths remaining from the bank to her home.

This results in C(10,4)*C(25,14)*C(7,2)*C(28.18) total round-trip paths from home to work and back with the designated stops.

.

5.

As of today there are 186 major-league baseball players with a batting average from .250 to .299. The batting average must be a three-digit decimal value between .000 and 1.000. Explain why at least four of these players must have the same batting average.

There are precisely 50 3-digit decimal values from .250 to .299. If each of the 50 possible averages was held by three players, that would represent 150 players. But we know there are 186 players with such averages. By the pigeonhole principle, at least one of those 50 averages must be held by more than three people.

.

6.

A certain zookeeper has n cages lined up in a row and has two lions that are indistinguishable from each other. The lions must be placed in separate cages and they may not be placed in adjacent cages.

Write a recurrence relation to describe L(n), the number of ways the two lions can be placed into n cages. Be sure to state any initial conditions of the relationship.

You might begin this problem by looking at cases involving small numbers of cages. The table below shows some of these.

number of cages
ways to place the 2 lions
1

2

3

4

5

0

0

1

3

6

How do we count the increase from one case, or more, to the next?

Suppose there are 5 cages lined up left to right. Then one of two things must be true of the left-most cage: either there is or is not a lion in it.

If there is no lion in that cage, we've reduced the problem of counting the ways to accomplish the task with (n-1) cages, and we know that number of ways is just L(n-1), or, here, L(4).

If there is a lion in the left-most cage, then there cannot be a lion in the cage next to that one. There can, however, be a lion in any of the other three cages. Thus, for this case, there are three ways to cage the lion. With n cages and a lion in the first cage, there would be (n-2) ways to place the second lion.

Together, then, because the two cases are distinct, there are L(4) + (5-2) = 3 + 3 = 6 ways to cage the two lions when there are five cages. That is, L(5) = 6. In general, with n cages, L(n) = L(n-1) + (n-2).

.

7.

The Washington Post intends to publish k interviews regarding a recent Supreme Count decision. They interviewed six white females, three black females, seven white males, and four black males. The article must include an interview from at least one person from each of the four categories. For example, if k = 6, the interviews may be from two white females, two black females, one white male, and one black male.

How many ways can the newspaper select the k interviews for publication? Create a generating function whose coefficients can be used to answer the question.

Each of the four factors of the generating function represents a category of interviewees. The first represents black males, the second black females, the third white males, and the last white females.

When the function is expanded and like terms are collected, the value C in Cx^k will indicate the number of different ways that k interviews can be selected for the article under the condition that at least one interview from each category does appear.

.

8.

Fran is a professional singer. She claims to have enough jokes in her repertoire to be able to tell a different set of three jokes in her warm-up act, every night of the year, for at least 50 years. What is the minimum number of jokes she must have?

Note that the set of jokes {A,B,C} is considered one set of jokes, no matter what order Fran tells those three jokes.

We first determine how many times Fran may appear on stage. We assume 366 days per year for 50 years, or 18,300 days. Thus we need that many sets of jokes. Because of the note in the final sentence of the problem statement, we solve the problem using combinations, assuming order does not matter. Thus, we need to determine the smallest positive integer k such that C(k,3) is equal to or larger than 18,300. By guess and test, one of several strategies that can be used, we find that k = 49 is the smallest positive integer that works.

Fran must have 49 jokes.

.

9.

How many ways are there to deal n cards to two persons? It is permissible that the persons may receive unequal numbers of cards.

One way to solve this problem is to consider the number of subsets possible for a set of n objects. We know there are 2^n such subsets, but two of those do not involve both players, for the subset of size n means nothing remains for the other player, and, likewise, the subset of size 0 means one player gets no cards.

Therefore, there are 2^n - 2 = 2(2^(n-1) - 1) ways to deal n cards to 2 people.

.

10.

Exactly 7 chocolate chips are to be distributed at random into 6 chocolate chip cookies. What is the probability that some cookie has at least 3 chips in it?

To determine this probability, we need to create a ratio of two values. When expressed as a common fraction, the denominator of the ratio describes the total number of ways the 7 chips can be distributed; the numerator of the ratio describes the number of ways the chips can be distributed so that some cookie has at least 3 chips.

The denominator is just the number of nonnegative solutions to the equation x1+x2+...+x6=7. This assumes the cookies represent 6 distinguishable entities, for the solution (2,1,1,1,1,1) is different from the solution (1,1,1,1,1,2). Other arguments or approaches will be considered. Under our assumptions, the number of solutions is C(7+6-1,6-1)=C(12,5).

The numerator of the ratio will be determined indirectly by answering a related question: How many ways can the chips be distributed so that NO COOKIE has 3 or more chips in it? This is the event complementary to the originally stated event, so when we solve this and subtract from C(12,5) we will have the number required for the numerator of our probability ratio.

There are only three cases to consider here:

I) One cookie has 2 chips and the remaining 5 each have 1 chip. There are only 6 ways this can happen, for either the first cookie has 2 chips, the second cookie has 2 chips, and so on, through to the sixth cookie with 2 chips. For Case I we get 6 ways.

II) Two cookies have 2 chips each, three cookies each have 1 chip, and one cookie gets no chips. Thus, we are arranging the numbers 2,2,1,1,1,0 in all possible configurations. The number of ways this can be done is just a multinomial coefficient: 6!/(2!3!1!) = 60. For Case II we get 60 ways.

III) Three cookies have 2 chips each, one cookie has 1 chip, and two cookies gets no chips. Here we are arranging the numbers 2,2,2,1,0,0 in all possible configurations. The number of ways this can be done is just a multinomial coefficient: 6!/(3!1!2!) = 60. For Case III we get 60 ways.

This represents all possible cases, for no cookie can have more than 2 chips and no more than three cookies can each have 2 chips.

The sum of the values, or 126, represents the number of ways our condition is NOT met, so C(12,5)-126 represents the number of ways our condition is met. The desired probability ratio is [C(12,5)-126] / C(12,5) or 666/792 which reduces to 37/44. Almost 85% of the cases will meet our condition.

.

Bonus!

In how many ways can 2n people be divided into n pairs?

This problem will remain open throughout the next several days. I can assure you, however, that this specific question will NOT appear as required or optional on the semester exam.

.

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