Illinois State University Mathematics Department

 MAT 305: Combinatorics Topics for K-8 Teachers Spring 2001

 Possible Solutions: Semester Exam

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

 a. Replace a, b, and c in C(a,5) = C(5,b) + C(5,c) to illustrate Pascal's Formula. Solution: a=6, b=5, and c=4, or a=6, b=4, and c=5. b. A relationship s(n) is described recursively as s(n) = 3*s(n-1) - 2n, with s(1) = 4. State numerical values for s(2), s(3), and s(4). Solution: s(2)=8, s(3)=18, and s(4)=46 c. A group of 24 employees will be shuttled across town in three vans, including a blue van, a red van, and a white van. How many different ways can the employees shuttle across town if 12 people are in the blue van, 7 are in the red van, and 5 are in the white van? Solution: (24!)/(12!7!5!) d. A shelf is to contain 12 books, 8 indistinguishable paperback books and 4 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 12 books be arranged on a shelf? Solution: C(5,4) e. State the explicit formula for determining the number of derangements of n objects. Solution: D(n)=n!( (1/0!) - (1/1!) + (1/2!) - (1/3!) + ... + (-1)^n(1/n!) )

2.

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

 a. Determine the number of collected terms in the expansion of (2a-7c)^n. Solution: n+1 b. Determine the value of the coefficient R in the collected term Ra^5bc^12 resulting from the expansion of (a+b+c)^18. Solution: (18!)/(5!1!12!) c. Determine the number of uncollected terms in the expansion of (s+t+a+r)^101. Solution: 4^101 d. Determine the number of collected terms in the expansion of (b+r+a+i+n+s)^16. Solution: C(21,5) e. Consider Pascal's Triangle, where 1 is the 0th row, 1 1 is the 1st row, and 1 2 1 is the 2nd row. i. Show the elements in row 5 of Pascal's Triangle. Solution: 1 5 10 10 5 1 ii. State the difference between the sum of the elements that appear in row 15 of Pascal's Triangle and the sum of the elements that appear in row 16 of Pascal's Triangle. Solution: 2^15

3.

After updating my advising records this week, I have found that 54 of my advisees each have accumulated from 54 credit-hours to 100 credit-hours. Explain why at least two of these 54 advisees must have the same number of accumulated credit-hours.

Solution: Here we assume that credit-hours accumulate in whole number increments. The range of values, from 54 to 100 credit-hours, spans 47 integer values: 54, 55, 56, ..., 98, 99, 100. The first 47 advisees may all have different numbers of accumulated credit-hours, but the 48th advisee is assured to match at least one of the first 47. This is justified by the pigeonhole principle.

4.

Gary drives a city taxicab during the summer. A client of his, Patti, always rides home in Gary's taxicab. Her apartment is 14 blocks north and 6 blocks east of the office building where she works. The streets between the office building and Patti's apartment are laid out in a rectangular grid, and all streets are accessible to Gary's taxi. How many different paths are available for Gary to make the 20-block trip from Patti's workplace to her apartment?

Solution: This is a basic grid problem: C(20,14)=C(20,6).

5.

Thirty-two (32) distinct fair dice are rolled. How many ways are there for nineteen 5s to appear?

Solution: Because the dice are distinct, we must first select 19 of them as those that show a 5. This can be done in C(32,19) ways. Next we look at all ways that the remaining 13 dice can be rolled. There are 5 choices for the first die, 5 for the next, and so on, resulting in 5^13 ways for the remaining 13 dice to appear. Because each of the C(32,19) is a unique set of 19, each is paired with the 5^13 ways for the remaining dice to appear. This results in C(32,19)*5^13 ways for the nineteen 5s to appear.

6.

After administering a new medicine, a collection of 314 lab rats was tested for four diseases.

One-hundred fifty-three (153) of the rats tested positive for asefachia, 179 tested positive for bunkeritis, 148 tested positive for cluenegligencia, and 155 tested positive for dipchillase.

Among the same 314 rats, 85 tested positive for both asefachia and bunkeritis, 71 tested positive for both asefachia and cluenegligencia, 75 tested positive for both asefachia and dipchillase, 85 tested positive for both bunkeritis and cluenegligencia, 90 tested positive for both bunkeritis and dipchillase, and 77 tested positive for both cluenegligencia and dipchillase.

We also know that 38 tested positive for all three of asefachia, bunkeritis, and cluenegligencia, 41 tested positive for all three of asefachia, bunkeritis, and dipchillase, 34 tested positive for all three of asefachia, cluenegligencia, and dipchillase and 47 tested positive for all three of, bunkeritis, cluenegligencia, and dipchillase.

Finally, we know that 17 of the 314 lab rats tested positive for all four of the diseases.

How many of the 314 lab rats tested negative for all four of the diseases?

Solution: Use the Inclusion/Exclusion principle:

314 - (153+179+148+155) + (85+71+75+85+90+77) - (38+41+34+47) + 17=19

Nineteen (19) of the 314 rats tested negative for all four diseases.

7.

President John Kennedy was well known for his heroic efforts in World War II. During his career in politics, including service in Congress and as President, he developed a reputation for using war stories in his speeches. In fact, those who knew him best claim he told exactly 4 war stories per speech. They also claim that, in the 5004 speeches in which he told exactly 4 war stories, he never once repeated the same 4 stories in the exact same order.

What is the minimum number of war stories Kennedy must have had at his disposal in order for those claims to be true?

Solution: We need to determine n so that P(n,4) is greater than or equal to 5004. By trial and error, n=10. Kennedy needed 10 war stories.

8.

Illinois State University surveyed parents/guardians and new students who took part in the university's "preview" activities. If the "preview" office kept track of whether each response was from a male parent/guardian, a female parent/guardian, a male new student, or a female new student, and the "preview" office received a total of 208 responses, how many different sets of 208 responses were possible, with respect to the gender-parent/student make-up of the respondents?

Solution: We seek the number of non-negative interger solutions to the equation MP+FP+MS+FS=208, where each two-letter variable represents one of the four categories of respondents. The number of such solutions is C(208+4-1,4-1)=C(211,3).

9.

A strange bequest by a recently deceased mathematician involved the two nephews of the mathematician. The two nephews were to divide the mathematician's sports card collection, with the only requirement being that each nephew get at least one card. If there were k different cards in the collection, with no card appearing more than once, how many different divisions were possible between the two nephews?

Solution: This problem can be viewed as determining the number of subsets from a k-element set and adjusting for the requirement that each nephew get at least one card. There are 2^k different subsets, including the empty set. We must eliminate both the empty set and the set itself as potential subsets, for use of either of these violates the restriction that each nephew get at least one card. Therefore, there are 2^k - 2 ways to divide the cards.

10.

An unlimited supply of dominoes is available for building a rectangle that measures exactly 2 units high and n units long. Each domino is a 2-by-1 rectangle.

Write a recursive description for R(n), the number of different ways to build a 2-by-n rectangle with dominoes. Be sure to state any initial conditions of the relationship and to explain the basis for your recursive formula.

Solution: Let us look at some of the initial values for R(n).

R(1) represents the number of 2-by-1 rectangles we can create with 2-by-1 dominoes. There is just one way to do this, so R(1)=1.

R(2) represents the number of 2-by-2 rectangles we can create with 2-by-1 dominos. There are two way to do this, with a pair of dominoes both horizontal or both vertical, so R(2)=2.

Now let's see how we can build R(3) from previous cases. From the 2-by-2 rectangles (i.e., those two in the R(2) case), we can append one vertical 2-by-1 domino. From the 2-by-1 rectangles (i.e., the one in the R(1) case), we can append two horizontal 2-by-1 dominoes. It seems, then, that R(3) is just R(2)+R(1), or, equivalently, R(3)=3.

This pattern will continue, for to get R(n) we need to just look at those in the R(n-1) case and append one vertical domino, or look at those in the R(n-2) case and appeand two horizontal dominoes.

Therefore, R(n)=R(n-1)+R(n-2), with R(1)=1 and R(2)=2.

BONUS!

Each week two World Professional Tennis Organizations determine who are the #1 players in the world for both womens' and mens' professional tennis.

 I. A rare disease is known to affect 0.1% of the population. A test for the disease is 95% accurate. You test positive for the disease. What is the probability you actually have the disease? II. Each week two World Professional Tennis Organizations determine who are the #1 players in the world for both womens' and mens' professional tennis. Steffi Graf was #1 in womens' tennis without interruption over the period Monday, August 17, 1987, until Sunday, March 10, 1991. This is the greatest number of consecutive weeks that any woman or man has been #1 in the professional rankings. How many consecutive weeks were there in Steffi Graf's record?

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