Illinois State University Mathematics Department

 MAT 305: Combinatorics Topics for K-8 Teachers Spring 1999 6:00 - 8:50 pm Tuesday STV 332 Dr. Roger Day (day@ilstu.edu)

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

 a. If we label the rows of Pascal's Triangle starting with n = 0 and the columns starting with k = 0, what is the value of the entry in row 14, column 11? b. Express P(18,3) in three different ways: (i) as the product of three consecutive integers; (ii) using factorial notation; and (iii) in terms of C(18,3). c. In how many ways can 12 donuts be distributed to 6 people, allowing that some may receive no donuts or that one person may get them all? d. A biologist plans to complete an experiment with 14 mice, aptly numbered 1 through 14. Six of the mice will receive a double dose of Vitamin E, 5 of the mice will receive a single dose of Vitamin E, and the rest will receive no doses of Vitamin E. In how many ways can this distribution take place? e. A committee of three is to be formed from among four men (Adam, Bill, Cal, and Dan) and four women (Eve, Fran, Gert, and Hanna). In how many ways can this be done if Adam and Eve refuse to serve on it together?

2.

The following conjecture is to be proven true by induction or shown to be false using a counterexample: 1 + 2 + . . . + (n-1) + n + (n-1) + . . . + 2 + 1 = n^2.

 a. Describe and carry out the first step in the induction process. b. Describe and carry out the second step in the induction process. c. Describe but do not carry out the third step in the induction process.

3.

There are 6 men and 5 women on a committee. A subcommittee of 6 is to be formed. The subcommittee must have no less than two men and two women. In how many ways can such a subcommittee be formed?

4.

A domino is a rectangle formed by two congruent squares. Each square contains an orderly pattern of "pips" or dots representing a number from zero through six. How many different dominoes can be made under these restraints?

5.

For some positive integer n, how many integers between 0 and 2n inclusive must you pick to be sure that at least one of them is odd?

6.

Suppose that Jay Cool and the Gingos are playing at the Starlite Theatre. The theatre has one section of seats, arranged with 70 seats in the first (front) row, 72 seats in the second row, 74 seats in the third row, and so on, for a total of 30 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 #71, and so on.

 a. Write 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 last (30th) row. 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 theatre.

7.

The set of letters {A,A,A,B,B,B,B,C,C} is to be used to create k-element subsets.

 a. State the range of values for k that is possible for this situation. b. How many subsets in all can be created?

Create a generating function that can be used to determine the number of 6&endash;element subsets that will have at least one A and at least two Bs.

 c. Show the factors of the generating function before expanding them. Explain what each factor represents within the context of this problem. d. Expand your response to part (c). e. Use part (d) to determine the number of 6-element subsets that will have at least one A and at least two Bs. Include a brief explanation for how you used part (d).

8.

Determine numerical values for x, y, and z that make a collected term in the expansion of .

9.

 a. How many positive integers are there that are composed of n digits such that each digit is 1, 2, or 3? b. Of these, how many contain all three of the digits 1, 2, and 3 at least once?

10.

My nephew Seth noticed that Kellogg's cereals offers a set of 5 cartoon characters in its current cereal selections. One cartoon character is in each specially marked box of cereal and the cartoon characters are equally distributed among the cereal boxes currently coming off the production line.

Seth has been around me enough so that he can figure out some probabilities. He knows that the probability of getting a complete set by purchasing less than five boxes is 0. He also explained how to determine the probability he could get a complete set by buying exactly 5 boxes of cereal. He said that there are 5! ways he could buy 5 boxes and get all different characters. He also told me that there were 5^5 different ways to get a set of 5 characters, not necessarily all different. The probability of getting a complete set in the first five purchases is 5!/(5^5).

Here's where he needs your help: What's the probability that it takes exactly 6 boxes of cereal to collect a complete set of 5 cartoon characters?

BONUS!

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

 a. 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? Clearly show your work in solving the problem. b.Steffi Graf was also ranked #1 during these time periods: August 5 to August 11, 1991 August 19 to September 8, 1991 June 7, 1993, to February 5, 1995 February 20 to February 26, 1995 April 10 to April 30, 1995 Including your response to (a), for how many total weeks of her career, through 30 April 1995, was Steffi Graf ranked #1?

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