1.

a. Show how to simplify the following expression
to generate a positive integer: C(5,2).

b. Determine the number of ways to arrange 10
distinct dogs in a straight line.
There are 10! arrangements.


c. There are 8 coffee choices and 12 tea choices
on the menu at Farms and Babble Bookstore. These
are the only beverage choices.
(i) If a customer orders either tea or
coffee, how many selections does the customer
have to choose from?
In this case, using the Addition
Principle, there are 8 + 12 = 20
selections.

(ii) If a customer orders one tea choice and
one coffee choice, how many choices are
possible? Disregard whether tea or coffee is
ordered or served first.
Using the Multiplication Principle,
there are 8 x 12 = 96 choices.


d. Determine the number of nonnegative integer
solutions to the equation
A + B + C + D + E + F = 40.

e. Consider Pascal's Triangle, where 1 is
the 0th row, 1 1 is the 1st row, and 1 2
1 is the 2nd row.
(i) Show the elements in row 6 of
Pascal's Triangle.
(ii) State the sum of the elements that
appear in row 20 of Pascal's Triangle.



2.

a. Determine the number of collected terms in
the expansion of .
There are w+1 collected terms.


b. Determine the value of the coefficient K in
the collected term
resulting from the expansion of .

c. Determine the number of uncollected terms in
the expansion of .
There are 4^15 uncollected terms.


d. Determine the number of collected terms in
the expansion of .
There are C(22+51,51) = C(26,4)
collected terms.




3.

The following conjecture is to be proven true by
induction or shown to be false using a counterexample:
a. State and carry out the first step in the
induction process.
Step 1: Show that the conjecture is
true when n=1.
When n=1, the LS is (21)(2x1)=2. When
n=1, the RS is (1x3x2)/3=2. When n=1,
LS=RS.


b. State and carry out the second step in the
induction process.
Step 2: Assume that the conjecture
holds when n=k.
When n=k, the conjecture is


c. State but do not carry out the third
step in the induction process.
Step 3: Use the assumption in Step 2 to
show that the conjecture holds when
n=k+1.




4.

A passenger jet may fly three routes from New York to
Chicago and four routes from Chicago to Los Angeles. For a
round trip from New York to Los Angeles and back, determine
the number of ways a passenger can travel without repeating
the same route on any leg of the round trip.
Starting in NY, there are 3 ways to get to
Chicago and 4 ways to get from Chicago to LA.
Therefore there are 3x4=12 different ways to get
from NY to LA via Chicago. On the return trip, the
passenger has only 3 ways to go from LA to Chicago
because a previously used route cannot be repeated.
Likewise there are 2 ways to go from Chicago back
to NY. Therefore, the return trip has 2x3=6 ways to
return to NY from LA via Chicago.
By the multiplication principle, there are
12x6=72 different round trips in all that reuse
none of the legs of the journey.



5.

Five unique dice are thrown simultaneously. Determine the
portion of all possible throws that result in at least two
5s appearing.
First determine the number of different throws
that are possible with no restrictions: There are 6
ways for each die to land, so there are
6x6x6x6x6=6^5 unique throws.
Now determine how many throws show at least two
5s. do this by subtracting from 6^5 the number of
ways to get exactly one 5 and exactly no 5s.
To get no 5s, there are 5x5x5x5x5=5^5 ways for
the dice to land, because each die can result in
one of five outcomes (everything but 5). To get
exactly one 5, there are 5 ways to choose which die
will be the 5, and then once that choice is made,
the remaining four dice each have 5 outcomes
possible. Therefore, there are 5(5x5x5x5)=5^5 ways
for exactly one 5 to appear.
Therefore, there are 5^5 + 5^5 ways to get
exactly zero or one 5 to appear, so there are
6^5(2x5^5) ways for at least two 5s to appear.
Of all possible throws, the portion that show at
least two 5s when five unique dice are thrown
is
[6^5(2x5^5)] / 6^5.



6.

A nurse walks from home at 10th and H to her clinic at
16th and M, always walking to higher numbers or to letters
further along in the alphabet. On a certain day, police
block off 13th street between K and L streets. What portion
of all possible paths from the nurse's home to the clinic
contain the blockedoff street?
First determine the total number of ways to walk
from 10th and H to 16th and M with no restrictions.
Assume that the numbered streets run east and west
and the lettered streets run north and south. Also
assume that the numbered streets get higher as you
move south and the lettered streets get further
into the alphabet as you move east. The nurse must
walk 6 blocks south and 5 blocks east. There are
C(11,6) ways to do this.
Now determine how many of these paths include
the blockedoff street. To get to K and 13th, you
must walk 3 blocks east and 3 blocks south.
Therefore, there are C(6,3) paths from 10th and H
to 13th and K. There is 1 way to get from 13th and
K to 13th and L. From 13th and L, there are 3
southerly blocks and 1 easterly block to walk to
get to 16th and M. There are C(4,3) walks to walk
this stretch. All in all, there are C(6,3)x1xC(4,3)
paths from 10th and H to 16th and M that include
the restricted street.
We remove these from the total number of paths,
yielding C(11,6)  [C(6,3)x1xC(4,3)] total
paths that do not include the blockedoff
street.



7.

A company named GAMES has an advertising display with the
letters of its name, "GAMES." Colors are used for each
letter, but the colors may be repeated. On one particular
day, for example, the colors might be red, green, green,
blue, red. The company wishes to use a different color
scheme for each of the 365 days in the year 2001. Determine
the minimum number of colors that are required for this
task.
One way to approach this problem is to think of
the choices available to fill each of 5 available
spaces. Here those 5 spaces are the letters, and
the things we fill them with are colors.
If there is 1 color available, we have 1 way to
fill the first space, 1 way to fill the second, and
so on. Repetition is allowed. Using the
multiplication principle, there is 1x1x1x1x1 way to
color the letters in the sign.
If there are 2 colors available, we have 2 ways
to fill the first space, 2 ways to fill the second,
and so on. Repetition is allowed. Using the
multiplication principle, there are 2x2x2x2x2=2^5
ways to color the letters in the sign.
In general, there are n^5 different coloring
schemes, where n is the number of available
colors.
We seek n such that n^5 >= 365. We have
1^5=1, 2^5=32, 3^5=243, and 4^5=1024.
The minimum number of colors is 4.



8.

In 7,843 families, all of which have a TV set, a
dishwasher, a microwave, and a car, there are six different
types of TV sets, five different types of dishwashers, four
different types of microwaves, and eight different types of
cars. What is the least number of families that have the
same type of TV, dishwasher, microwave, and car?
By the multiplication principle, there are
6x5x4x8=960 different combinations of the 4 objects
when we consider the different number of types of
each object.
By the pigeonhole principle, we may have the
first 960 families surveyed each identify a
different combination of the 4 objects, but by the
961st family, we will repeat one of the 960
combinations.
Dividing 7843 by 960, we get a quotient between
8 and 9. Thus we could have 8 full sets of the 960
pigeonholes, and some with at least 9 responses.
Thus, there are at least 9 families that share the
same type of objects.



9.

Cannon balls are stacked in a compact equilateral
triangular pattern. When there are n layers in the
stack, there are n balls per side of the
triangle on the lowest layer, n1 per side on
the next layer, and so on, up to 1 ball on the top.
Determine a recursion relationship B(n), including
any initial conditions, for the total number of balls in a
pile with n layers.
Here is a twodimensional visual image of
several layers, moving down from the top.
Notes:
 Each layer represents atriangular number:
1,3,6,10, and so on.
 These numbers each represent the sum of a
specific number of positive integers: 1=1,
3=1+2, 6=1+2+3, 10=1+2+3+4.
 Recall that the sum of the first n positive
integers is [n(n+1)]/2.
Now consider some initial examples of the
cannonball stacks.
 A stack with one layer has 1 cannon ball, so
B(1)=1.
 A stack with two layers has layers (a) and
(b) shown above, so it has 4 cannon balls.
Another way to think of this is that it has the
number B(1) plus the new layer, here figure (b).
So B(2)=B(1)+3.
 A stack with three layers has layers (a)
through (c) shown above, so it has 10 cannon
balls. Another way to think of this is that it
has the number B(2) plus the new layer, here
figure (c). So B(3)=B(2)+6.
 A stack with four layers has layers (a)
through (d) shown above, so it has 20 cannon
balls. Another way to think of this is that it
has the number B(3) plus the new layer, here
figure (d). So B(4)=B(3)+10.
So what do these examples illustrate in general?
Each new pile of cannon balls has the same number
as the previous pile plus the number in the lew
layer. That new layer will always have a number of
cannon balls equal to the sum of the positive
integers up to that layer number. That is, for a
stack with n layers, the number of balls will be
B(n1) plus the sum of the first n positive
integers.
In compact notation, we have
B(n)=B(n1)+[n(n+1)]/2, with initial
condition B(1)=1.



10.

Exactly 10 chocolate chips are to be distributed at
random into 6 chocolatechip cookies. What is the
probability that some cookie has at least 3 chips in it?
We need two values to compare as a ratio to
determine the desired probability: The total number
of ways to distribute 10 chocolate chips into 6
cookies and the number of those ways that result in
at least three chips in one cookie.
To determine the total number of ways to
distribute the chips, we determine the number of
nonnegative solutions to the equation
A+B+C+D+E+F=10,
where each letter represents a cookie. The
number of solutions is C(10+61,61)=C(15,5).
To determine the number of those ways that
result in at least three chips in one cookie, we
solve the complementary problem and subtract that
result from the total number of ways.
The complementary problem is to determine the
number of ways that the chips can be distributed so
less than three chips are in any cookie.
Considering the equation above, we want A,B,C,D,E,
and F to be values less than 3.
One case in this solution is for a cookie to
have no chips in it. If that is the case, the other
five cookies will each have two chips. There are 6
cookies to choose from in determining which will
have no chips, so there are 6 ways to distribute
the chips so one cookie gets no chips.
We can also distribute the chips so two cookies
get one chip each and the rest get two each. This
can be done in C(6,2) ways, for we need to
determine the number of ways to select two of the
six cookies into which we place one chip each.
There are no other ways to restrict the chips to
less than three chips, for there is no way to have
two or more cookies with no chips (without some of
the others having at least three chips), and if
more than two cookies each have one chip, we are
assured of at least one cookie getting three or
more chips.
So there are 6+C(6,2)=6+15=21 ways to restrict
chip distribution to two chips or less. That means
there must be C(15,5)21 ways to have three or more
chips in a cookie.
This means the desired probability is
[C(15,5)21]/C(15,5)=2982/3003 or
approximately a 99.3% probability that a cookie
will get three or more chips.



BONUS!

A survey was conducted of 983 families to determine
whether they possessed (1) a cell phone, (2) a microwave,
(3) a satellite dish, or (4) a CD player. No family was
completely without such items, and 481 families had at least
two of these items. At least three items were possessed by
345 families and 264 families possessed all 4 items.
a. Determine the total number of pieces of
equipment held by all 983 families.

b. Determine the number of families that held
the number of pieces of equipment specified below.
Assume that none of these families had more than
one of any particular item.
(i) exactly one piece of equipment
(ii) exactly two different pieces of
equipment
(iii) exactly three different pieces of
equipment


