**Test #3: Possible Solutions**

1.

a) 5^11

To expand the multinomial, you make a choice of one term from five
available in each of the 11 factors (m+n+p+s+v). Because the choices
are independent, we use the multiplication principle:
5*5*5*5*5*5*5*5*5*5*5

b) C(15,4)

Each collected term of the expansion is of the form where
M+N+P+S+V=11. Thus we seek the number of nonnegative-integer
solutions to the equation M+N+P+S+V=11. There are C(11+5-1,5-1) ways
to solve this equation.

c)11!/(4!2!4!)

There are 11! arrangements of the letters mmmmnnpvvvv. We divide by
(4!2!4!) to account for the duplicate letters m, n, and v.

BONUS Solution: 20 collected terms

For the coefficient K of the collected term to be 11, we must have
. This means
the collected terms look like .
We need to determine the number of ways to arrange two elements from
{m,n,p,s,v} so that one is x1 and the other is x2. This is
P(5,2)=5*4.

2.

a)

There are 14! arrangements of the letters in the word. We divide by
(3!3!2!) to account for the duplicate letters.

b)

Place the consonants first. There are 9!/(3!2!) ways to do this. This
leaves us with 10 spots into which we place 5 vowels. This can be
done in P(10,5) ways. We divide by 3! to account for the letter
**i** appearing 3 times.

Bonus Solution: Many solutions are possible.

The word you submitted was checked to determine whether all three
criteria were met.

Double Bonus Solution: 13 letters

Consider some examples. There must be at least 6 letters in the word,
based on conditions (i) and (ii). The word **picnic** is such a
word. We symbolize the unique and total number of letters as
{1,1,2,2} to show there are 4 unqiue letters (elements in the set)
and 6 letters in all (sum of the values in the set). There are
6!/(2!2!)=180 unique arrangements of the letters in this word.

If we continue to duplicate letters and introduce no new letters, the progression of unique arrangements is (using the symbolism shown above) {1,2,2,2}--> 630 arrangements, {2,2,2,2}--> 2520 arrangements, {2,2,2,3}--> 7560 arrangements, and {2,2,3,3}--> 25200 arrangements. This shows that we could have at most 9 letters.

Another way to duplicate letters and not increase the number of new letters is to only further duplicate one letter. Here's what we get for that scenario: {1,1,2,3}--> 420 arrangements, {1,1,2,4}--> 840 arrangements, {1,1,2,5}--> 1512 arrangements, {1,1,2,6}--> 2520 arrangements, {1,1,2,7}--> 3960 arrangements, {1,1,2,8}--> 5940 arrangements, {1,1,2,9}--> 8580 arrangements, and {1,1,2,10}--> 12012 arrangements. This shows that we could have at most 13 letters.

Yet another option is to simply add additional new letters without duplicating any. Here's what happens: {1,1,1,2,2}--> 1260 arrangements and {1,1,1,1,2,2}--> 10080 arrangements. This shows that we could have at most 7 letters.

There are no other ways to uniquely increase the number of letters, duplicate or otherwise.

3.

a) 2^4=16

For each of 4 categories there are 2 choices.

b) C(53,15)

There are 16 categories to fill with the information from the 38
diners, and it's possible that a category may have zero entries.
We're determining the number of nonnegative-integer solutions to the
equation x1+x2+...+x16=38. This is C(53+16-1,16-1).

4.

Consider the stages of the process of selecting and matching tenacles
between the two critters. One way to consider this is to first choose
4 tenacles from Octopus A. this can be done in C(8,4) ways. Now
choose 4 tenacles from Octopus B, done in C(8,4) ways. Now permute
the 4 chosen tenacles of Octopus B and match each permutation with
the 4 already selected from Octopus A. This last step can be done in
P(4,4)=4! ways. Let this be the situation where Octopus A pins 4 of
Octopus B's tenacles.

While this is going on, each octopus has 4 tenacles remaining. Permute the idle 4 tenacles of either octopus (but not both), done in P(4,4)=4! ways. Match these with the remaining 4 tenacles of the other octopus.

Because each of these steps is independent from the others, we multiply the results of each step to get C(8,4)*C(8,4)*P(4,4)*P(4,4). This is equivalent to P(8,4)*P(8,4), and you can make a combinatorial argument to satisfy that form as well.

5.

a) C(50,2)=1225

The value 1225 is just C(50,2) which precisely matches the situation
presented in the problem. We're simply grabbing two unique objects
from the 50 that are in the jar, and the order we pull them from the
jar is not important.

b) 445 pairs

This solution requires some degree of enumeration for the several
cases that exist. We need to consider what could be the difference
between any pair drawn and then count those that meet the condition
of being within 10 of each other.

Concentrate on one number in a pair. If it ranges from 11 to 40, it has 20 different values (10 less than it and 10 greater than it) that it could pair with and yield a difference 10 or less. If one number is 10 or 41, it has 19 different values it could pair with and generate a difference of 10 or less. If one number is 11 or 42, is has 18 different values, and so on, to one number being 1 or 50, pairing with only 10 possible values.

We now add the possibilities: 30(20)+2(19)+2(18)+...+2(10). This sum is 890. We must divide that be 2, however, because, we are not distinguishing a first number from a second in any pair. For instance, pairing 14 with 9 is counted twice, first when looking at 14 matching with 20 possible values and then 9 matching with 18 possible values. Therefore, our correct solution is 445 pairs.

6.

First consider a legitimate solution to the problem and then compare
it to that of the student.

We use the hardback books (HBB) as barriers to the paperback books (PBB), so place the HBB first, in 3! ways. This gives us 4 places to places pairs of PPB. Select 3 of those, in C(4,3) ways. Now, consider how the PBB can be rearranged in their chosen places. Despite the fact that the PBB are paired, there are P(6,6)=6! ways to arrange them in their places. Each of the three steps in the process are independent of one another, so there are 3!*C(4,3)*6! ways to carry out this shelving task.

Now consider the student's solution. Comparing it to mine, the first step seems legitimate: placing the HBB as barriers. The next step, however, is incorrect. The student's arrangement of 6 books among the 8 spots designated does not assure pairing of PBB, despite the solver's drawing that shows "pairs" of available spots between the HBB. The student's solution does nothing to prevent a single PBB to appear somewhere between two HBB.

BONUS QUESTIONS

Correct solutions were not presented for all three problems, so the
bonus solutions will be left open.