Summer 1997 Test #1: Possible Solutions

1. 96 responses
This problem may be solved by applying the Pigeonhole Principle. Imagine a basket for each of the five professional groups, into which completed surveys are deposited as they are received. The worst possible situation that fails to meet the condition is that each of the five baskets will have 19 replies. This represents 95 completed surveys. Upon receiving the 96th reply, however, we can be sure that at least one basket contains at least 20 replies.

2.
(a) C(20,5)
Here, order or arrangement is not important because each of the 5 funds is to receive \$40,000. There are C(20,5) sets of 5 funds that can be selected for investment.

(b) P(20,5)/(2!2!)
Now the match-up of dollars with a particular fund does matter, because differing amounts are being invested. There is duplication, however, in that two funds receive \$20,000 and two others receive \$60,000. For example, if stocks A,B,C,D,E are chosen, \$20,000 in A and B, \$40,000 in C, and \$60,000 in D and E is the same as \$20,000 in B and A, \$40,000 in C, and \$60,000 in D and E. There are P(20,5) ways to arrange 5 of the 20 funds, and we divide by 2!2! to account for duplication of amounts invested.

3.
We assume that all individuals are distinguishable, because we are told that they all differ in height.

(a) 8!6!
Chunk the men into one "position" in line. This reduces the task to placing 8 objects in line (7 women and 1 chunk of men). This can be done in 8! ways. The six men can be arranged in 6! ways within their group.

(b) P(7,2)*P(6,2)*9!
There are P(7,2) ways to arrange two women at the front of the line. Likewise, there are P(6,2) ways to arrange two men at the end of the line. This leaves 9 people to fill the remaining positions, which they can do in 9! ways.

(c) 7!*6!
In order to alternate, the line must form with a woman in front and then alternate from there. This means each position in line is assigned to a gender in one and only one way. Within that restriction, there are 7! ways to arrange the women and 6! ways to arrange the men.

4. 11!/(5!2!2!)
There are 11 letters in the word so there are 11! ways to arrange the letters. With identical letters a, b, and r, however, some of those 11! arrangements are duplicates. There are 5! ways to interchange the letters a, 2! ways to interchange the letters b, and 2! ways to interchange the letters r. We divide by these values to account for the duplication.

5. 3*7!
Label the rows and columns to allow for convenient discussion, calling the column c1 through c8 left to right and the rows r1 through r8 top to bottom. We first place a rok in r1 because it is the most restrictive. There are three places for a rook in r1. Once a rook is placed, its row and column are eliminated because the rooks must be arranged in non-attacking positions. Without loss of generality, suppose the rook is in c8 of r1. We now move to r2 where there are seven spots available for a rook. Suppose the rook is placed in c1 of r2. This eliminates c1 and r2 for further placement. Continue this progression of placing a rook in available spots and eliminating that row and column from further placement. Eventually, one spot remains in r8 for the last rook. This gives us 3·7·6·5·4·3·2·1 ways to place the eight rooks into non-attacking positions.

6.
I. Prove (a) or (b) using induction.

(a) Prove that C(1,1) + C(2,1) + ... + C(n,1) = C(n + 1,2) for every positive integer n.

Step 1: Show the result holds for n = 1: Is C(1,1) equal to C(1 + 1,2)? Yes, because C(1,1) = 1 and C(1 + 1,2) = C(2,2) = 1.

Step 2: Assume the result holds for n = k: Here, we assume that .

Step 3: Use the assumption from Step 2 to prove that the result holds for n = k + 1. That is, we seek to show that .

From the assumption in Step 2, add C(k + 1,1) to each side: .

The LS of this equation matches the LS of the equation we seek to justify as correct. Now, simplify the RS: This last expression is just the result we seek, as shown in the initial equation of Step 3.

We have proved through mathematical induction that C(1,1) + C(2,1) + ... + C(n,1) = C(n + 1,2) for every positive integer n.

(b) Prove that 1(1!) + 2(2!) + ... + n(n!) = (n + 1)! - 1 for every positive integer n.

Step 1: Show the result holds for n = 1: Is 1(1!) = (1 + 1)! - 1? Yes, because 1(1!) = 1 and (1 + 1)! - 1 = 2! - 1 = 1.

Step 2: Assume the result holds for n = k: Here, we assume that .

Step 3: Use the assumption from Step 2 to prove that the result holds for n = k + 1. That is, we seek to show that .

From the assumption in Step 2, add(k + 1)(k + 1)! to each side: The LS of this equation matches the LS of the equation we seek to justify as correct. Now, simplify the RS: This last expression is just the result we seek, as shown in the initial equation of Step 3.

We have proved through mathematical induction that 1(1!) + 2(2!) + ... + n(n!) = (n + 1)! - 1 for every positive integer n.

II. Use your knowledge of combinatorial notation and algebra to prove that the left- and right-side expressions of each equation are equivalent.

(a) Prove that r*C(n,r) = n*C(n &endash; 1,r &endash; 1) for n <= r <= 1.

Simplify the LS: Simplify the RS: The two expressions are equivalent, thereby justifying the result.

(b) Prove that C(n,m)*C(m,k) = C(n,k)*C(n &endash; k,m &endash; k) for k <= m <= n.

Simplify the LS: Simplify the RS: The two expressions are equivalent, thereby justifying the result.