MAT 305 Spring 1996

Possible Solutions: Comprehensive Final Exam


Part I: Questions for Small-Group Exploration

1. While lounging in the lobby of the Embassy Suites hotel in San Diego, I watched hotel employees open a door after entering a code by pushing a digital keypad. The keypad is similar to the one shown below. From my vantage point, I could see neither the door nor the keypad. I could see people pushing buttons from the side. After carefully watching several people enter the door, I concluded that the sequence of keystrokes they used looked like the figure shown below. I knew the order of the keystrokes, as indicated by "first, second" and so on shown here. I did not know which keypad was struck first. I did know that the fourth push was directly below the first and second, and that the third and fifth pushes were directly below the fourth.

Based on this information, determine the number of different 5-number codes that could possibly unlock this door.

There are three possible keypads that could have been pushed first. This generates 6 different possible first numbers. The second through fifth pushes each have 2 possible numbers associated with them. This results in 2^4 = 16 different 4-number sequences. Together, then, there are 6*16 = 96 possible 5-digit codes.


2. Forty-one (41) pennies are placed on a 10-by-10 grid, one in each square of the grid. Prove that for any such placement, it is possible to choose a set of five pennies so that no two are in either the same row or the same column.

Consider worst-case scenarios, trying to place pennies so that the condition is not met.

(i) To keep pennies in less than five columns, I can use no more than 40 pennies (4 columns by 10 rows). As soon as the 41st penny is placed, by the pigeonhole principle we are assured that at least 5 columns and 5 rows are occupied, thereby providing a placement from which we can choose a set of 5 pennies that meets the condition described above.

(ii) If any empty grid squares exist in a set of 4 columns, a penny must exist in a fifth column. Given this condition, 5 different rows must have pennies in them, for if not, the pennies would only be in 4 different rows, which by (i) above is impossible.

(iii) By symmetry, the words "rows" and "columns" can be interchanged in (i) and (ii) with no loss of generality.


3. A certain zookeeper has n cages in a row and two indistinguishable lions. The lions must be in separate cages, and they may not be placed in adjacent cages. Determine the number of ways that the zookeeper can assign the 2 lions to the n cages.

See solution to question from Spring 99 sample exam questions!


4. In the May 1996 issue of the Mathematics Teacher (p 368), R. S. Tiberio of Wellesley (MA) High School shared the student discovery replicated below.

Your task: Justify that this relationship will hold in general, or, alternatively, show that the result cannot be generalized to all of Pascal's triangle.

By brute force symbolic manipulation we can show that

C(n,k-2) + C(n,k-1) + C(n,k) - [ C(n-3,k-3) + C(n-2,k-3) + C(n-1,k-3) ] - [ C(n-3,k-2) + C(n-2,k-1) + C(n-1,k-1) ] = C(n-2,k-2) + C(n-1,k-2) + C(n-1,k-1).

This is left as an exercise for you!

A less-symbolically intense method is to replace "positions" within the relationship with variables and relate them using Pascal's Formula and other known relationships.

a
b

c
d
e

f
g
h
i

j
k
l

Here, we know that a+d=b, c+d=g (or g-c=d), d+e=h (or h-e=d), f+g=j, g+h=k, and h+i=l.

We need to show that (j+k+l) - (a+c+f+b+e+i) = d+g+h. I'll let you work through the arithmetic and the substitutions that lead to success.


Part II: Questions for Individual Exploration

1. Consider the letters in the word purchase.

a. How many unique arrangements exist for the letters in the word?

P(8,8) = 8!

b. If an arrangement must begin with a consonant and end with a vowel, how many unique arrangements exist for the letters in the word?

5*3*6! There are 3 consonants to choose from to begin the arrangement and 5 vowels to choose from to end the arrangement. The remaining 6 letters can be arranged in 6! ways.


2. At Bagwanna State University, students' programs of study must include course credit in mathematics, science, English, history, and the arts. Each student must complete a total of exactly 46 credits that include these areas of study. Furthermore, no less than 6 credits must be in mathematics, at least 8 credits must be in science, and 10 or more credits must be from English. How many different student programs, based on credits earned, can be designed under these restrictions?

Exactly 46 credits are required, with 26 of theose already determined in courses in the five areas. This leaves 20 credits yet to be determined. The solution can be found by determining the number of non-negative integer solutions that exist for the equation M+S+E+H+A = 20, where the letters M, S, E, H, and A respresent the 5 groups.

There are C(20+5-1,5-1) = C(24,4) different student programs that could be created.


3. Consider the expansion of (R + D + A + Y)^16.

a. Determine the number of uncollected terms in the expansion.

4^16

b. Determine the number of collected terms in the expansion.

C(19,3)

c. Determine the coefficient P of the collected term PD^6A^2Y^8.

16!/(6!2!8!)

d. How many collected terms in the expansion will have the numerical coefficient P that you determined in (c) above?

The terms will be of the form R^aD^bA^cY^d where a,b,c, and d are from the set {0,2,6,8). There are 4! ways to make this assignment.


4. A shelf is to contain nine different books, six different paperback books and three different hardback books. If the paperback books must be shelved in pairs (that is, exactly two paperback books must be adjacent to each other), how many ways can the nine books be shelved?

First, arrange the three hardback books. There are 3! ways for this to occur. Once these are shelved, there are 4 places among the hardbacks to place the three pairs of paperbacks. These places can be chosen in C(4,3) ways. Finally, there are 6! ways to arrange the six paperback books.

There are 3!*C(4,3)*6! shelving arrangements.