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