Illinois State University Mathematics Department
MAT 305: Combinatorics Topics for K8 Teachers Spring 2001 
Possible Solutions: Semester Exam 
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).


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


After updating my advising records this week, I have found that 54 of my advisees each have accumulated from 54 credithours to 100 credithours. Explain why at least two of these 54 advisees must have the same number of accumulated credithours. Solution: Here we assume that credithours accumulate in whole number increments. The range of values, from 54 to 100 credithours, spans 47 integer values: 54, 55, 56, ..., 98, 99, 100. The first 47 advisees may all have different numbers of accumulated credithours, but the 48th advisee is assured to match at least one of the first 47. This is justified by the pigeonhole principle. 

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 20block trip from Patti's workplace to her apartment? Solution: This is a basic grid problem: C(20,14)=C(20,6). 

Thirtytwo (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. 

After administering a new medicine, a collection of 314 lab rats was tested for four diseases. Onehundred fiftythree (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. 

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. 

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 genderparent/student makeup of the respondents? Solution: We seek the number of nonnegative interger solutions to the equation MP+FP+MS+FS=208, where each twoletter variable represents one of the four categories of respondents. The number of such solutions is C(208+41,41)=C(211,3). 

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

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 2by1 rectangle. Write a recursive description for R(n), the number of different ways to build a 2byn 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 2by1 rectangles we can create with 2by1 dominoes. There is just one way to do this, so R(1)=1. R(2) represents the number of 2by2 rectangles we can create with 2by1 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 2by2 rectangles (i.e., those two in the R(2) case), we can append one vertical 2by1 domino. From the 2by1 rectangles (i.e., the one in the R(1) case), we can append two horizontal 2by1 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(n1) case and append one vertical domino, or look at those in the R(n2) case and appeand two horizontal dominoes. Therefore, R(n)=R(n1)+R(n2), 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.





