1.

Respond to each of these questions. While you may show
steps leading to your solution, you do not need to generate
written explanations for questions (a) through (d) of
problem 1.
a) Determine the number of derangements of the
elements in the set {1,2,3,4,5,6}, where the natural
position for 1 is the first position, the natural position
for 2 is the second position, and so on.
There are at least two efficient strategies for
solving this problem.
You can use the explicit formula for determining
the number of derangements of n objects. That is
Here D(6) = 265.
You can also refer to the recursive relationship
D(n)=n[D(n1) + D(n2)], where D(1)=0 and
D(2)=1. Again, D(6) = 265.

b) Answer the following questions for the recurrance
relationship described by:
a(n)=5a(n1)  2a(n3) for n a positive
integer,
where a(1) = 5, a(2) = 6, and a(3) = 1.
(i) Determine a(6).
(ii) Determine the smallest value of n such that
a(n+1) &endash; a(n) is greater than 5000.
(i) a(6) = 5a(5)  2a(3), but we do not know
a(5); a(5) = 5a(4)  2a(2), but we do not know
a(4); a(4) = 5a(3)  2a(1) = 5(1)  2(5) = 5.
Using this, a(5) = 5(5)  2(6) = 37. This results
in a(6) = 5(37)  2(1) = 187.
(ii) Further calculations show that a(7)=925,
a(8)=4551, a(9)=22381, and a(10)=110055. comparing
the differences of pairs of values, we see that
a(9) and a(8) provide the first pair with a
difference greater than 5000. The desired value of
n is 8.

c) In the expansion of ,
state:
i) the number of uncollected terms
ii) the coefficient K in the collected term .
(i) The number of uncollected terms is 4^10.
(ii) The desired coefficient is
10!/(3!1!2!4!).

d) Determine the number of collected terms in the
expansion of .
The number of collected terms is n+1 = C(n+1,n)
= C(n+1,1).



2.

Georgania Higgenbottom served a variety of cool drinks at
her spring garden party. Each of the 120 guests selected
exactly one beverage, chosen from the following list:
ginsing gogetter, spinach surprise,
cabbage combo, tomato torment, and cucumber
delight.
Georgania's head waiter, Christof, kept a tally sheet of
drink selections for the 120 guests.
a) Suppose Christof noticed that each of the beverages
had been selected by at least one guest. How many different
tally sheets could Christof have generated for the party's
drink selection under these circumstances?
We need to determine the number of solutions,
over the positive integers, for the equation
GG+SS+CC+TT+CD=120, where each variable represents
the number of guests who selected a particular
beverage. The desired solution is C(1201,51) =
C(119,4).

b) Suppose instead that when Georgania screamed to
Christof, "What are our minimums on drinks?" he replied, "I
see that at least 10 people chose the ginsing gogetter, 20
or more went for the spinach surprise, more than 6 people
tried the cabbage combo, no one selected tomato torment, and
at least 15 drank cucumber delight." Under these conditions,
how many different tally sheets could Christof have
generated for the party's drink selection?
We begin with the same equation,
GG+SS+CC+TT+CD=120, but modify it to account for
the known information. We know GG is greater than
or equal to 10, SS is greater than or equal to 20,
CC is greater than or equal to 7, TT is 0, and CD
is greater than or equal to 15.
If we adjust the equation to include these
conditions, writing new variables for the remaining
numbers of guests who could delect beverages, we
have GG' + SS' + CC' + CD' = (1201020715) or
GG' + SS' + CC' + CD' = 68. We seek the number of
nonnegative integer solutions to GG' + SS' + CC' +
CD' = 68. This is C(68+41,41)=C(71,3).
The desired solution is C(71,3).

c) Try to picture Amiele, the beverage host, walking
around the table asking guests for their beverage choice.
How many guests would Amiele have to ask before he would be
assured that a beverage choice repeated itself? What
assumptions underlie your response?
We apply the pigeonhole principle here,
considering the worstcase scenario. It could be
that the first 5 guests Amiele encountered each
chose a different beverage. The sixth guest,
however, would be assured of repeating a beverage
choice, by the pigeonhole principle.
The assumption is that each guest selects one
and only one beverage from the list of five
beverages discussed in the problem situation.



3.

In the Ancient yet littleknown game of gnikoj,
scoring occurs several ways. A player can earn 1 point for a
kaboom, 1 point for a laboom, and 1 point for
a maboom. A player earns 2 points for executing a
bifter or for executing a cifter. In
traditional gnikoj, there is no way to earn 3 points
on a single move, and the only way to earn 4 points is by
the rarely seen move called a gemserp. Points are
added and the player with the highest point total wins.
a) Show at least three different scoring sequences a
gnikoj player could execute and earn 11 points. Note
that the order in which points are earned is significant. A
kaboom followed by a cifter is a different
scoring sequence than a cifter followed by a
kaboom.
Three possible routes to 11 points:
 gemserp + gemserp + maboom + bifter (4+4+1+2
= 11)
 gemserp + gemserp + bifter + maboom (4+4+2+1
= 11)
 maboom + gemserp + gemserp + bifter (1+4+4+2
= 11)
Note from the next solution that there are
1,055,505 different ways to score 11 points in
gnikoj.

b) In gnikoj, play continues until an
essapmi is reached. Individual player totals could
exceed 100 points. Create a recursion relationship
T(n), including any required initial conditions, to
describe the number of different sequences of gnikoj
moves that result in a total of n points. Show
justification for your result.
We know T(1)=3 [three different 1point
scoring methods], T(2)=11 [9 pairs of
1point/1point scoring methods plus two 2point
scoring methods], T(3)=39 [6 different
1point/2point scoring methods plus 33
2point/1point scoring methods], and T(4)=140
[117 different ways to get from 3 points to 4
points, 22 different ways to get from 2 points to 4
points, no ways to get from 1 point to 4 points,
and 1 way to get from 0 points to 4
points].
If we consider how we can get to n points, we
can get there from already having n1 points, from
already having n2 points, and from already having
n4 points. For each way we can get to n1 points
(there are T(n1) ways), there are 3 ways to add a
point and get to n points. For each way we can get
to n2 points (there are T(n2) ways), there are
two ways to add 2 points and get to n points. For
each way we can get to n4 points (there are T(n4)
ways), there is one way to add 4 points and get to
n points.
Summarizing information in the preceeding
paragraph, T(n)=3*T(n1) + 2*T(n2) + T(n4). This
is the desired recursive relationship, given the
initial conditions of T(1)=3, T(2)=11, T(3)=39, and
T(4)=140.



4.

What is wrong with the following problem situation?
A survey of 144 new teachers in a
metropolitan school district determined that 16 new
teachers had been to Europe, 13 had been to Asia, and 17
had been to Africa. Of those who had been to Europe, 10
had been to Africa. Of those who had been to Asia, 9 had
been to Africa. Of all the new teachers surveyed, 5 had
been to Africa, Asia, and Europe, and 111 new teachers
had been to none of those continents.
Describe specifically and clearly what is wrong
and how you determined that.
This is a counting situation that involves three
categories of inclusion/exclusion. Visually, we can
represent the situation with a Venn diagram, like
the one shown here.
The letters A through G shown above represent
the various travel categorizations into which we
could place each of the 144 new teachers. Using the
notation developed in class, we can represent the
number of people in each category by using vertical
brackets around each category symbol. From the
given information, we know that:
 (1) E+B+C+G=16
 (2) A+B+C+D=13
 (3) C+D+F+G=17
 (4) C+G=10
 (5) C+D=9
 (6) C=5
 (7) H=111.
Using equations (3),(4), (5), and (6) shown
above, we can conclude that
 (8) G=5
 (9) D=4
 (10) F=3 [using (8) and (9) just
derived].
Using equations (1), (2), (6), (8), and (9), we
know that
 (11) E+B=10
 (12) A+B=4.
Using equations (6) through (10), and the fact
that 144 new teachers took the survey, we know
that
 (13) A+B+E=16.
From (11) and (12), by addition, we see that
 (14) A+2*B+E=14.
Here's where the contradiction can be shown. If
we subtract (13) from (14), we get
 (15) B=2.
But equation (15) is impossible, for we cannot
have a negative number of people responding to a
survey question.



5.

a) Using an unlimited supply of letters from the set
{A,B,C,D}, how many 7letter sets are possible to create
with at least one C in the set?
Here we are not concerned with the
arrangement of the letters within the set, merely
the collection of letters to form a 7letter set.
For example, the set {A,A,A,A,A,A,C} is the same as
{C,A,A,A,A,A,A}.
An efficient way to determine a solution for
this question is to count all possible 7letter
sets that can be created and subtract from that the
number of 7letter sets that have no Cs. The
remaining sets will all have at least one C.
To determine the total possible number of
7letter sets, we consider nonnegative integer
solutions to the equation a+b+c+d=7, where each
variable represents the number of times that letter
appears in the set. The number of such sets is
C(7+41,41)=C(10,3).
To determine the total possible number of
7letter sets that have no Cs, we consider
nonnegative integer solutions to the equation
a+b+d=7, where each variable represents the number
of times that letter appears in the set. The number
of such sets is C(7+31,31)=C(9,2).
Using the two results, we can conclude that the
number of 7letter sets with at least one C is
C(10,3)C(9,2) = C(9,3).

b) Using an unlimited supply of letters from the set
{A,B,C}, how many 5&endash;letter words (meaningless or not)
are possible to create with exactly one A in the word?
Now we must consider each arrangement of 5
letters, not merely the collection of them.
There are 5 places to position exactly one A in
our word. We must fill the remaining 4 positions
with Bs and Cs. If we select from 0 to 4 of those
remaining 4 positions and place the letter B in
those selected positions, we have only one way to
place Cs for each such selection.
For example, suppose A is in the leftmost
position in the word. We have 4 positions to fill.
Suppose we put Bs in positions 2,3, and 4. By
selecting those positions for B, we force letter C
to occupy position 5. This means that placing the
Bs forces the C placement as well.
There are 5 places to fix the letter A and there
are C(4,i) ways to place the letter B in from
0<= i <= 4 remaining positions. For each of
these, there is just one way to position C in any
remaining positions. By the multiplication
principle, our solution is
5*[C(4,0)+C(4,1)+C(4,2)+C(4,3)+C(4,4)].



6.

In a local chess competition, two players compete until
one player wins 4 matches. With no regard for the ability of
the players, what fraction of all possible twoplayer
competitions will require exactly 7 matches?
Every possible twoplayer rounds in this
scenario will require from 4 to 7 matches. It is
also the case that the person winning the
competition wins the last match in each round. For
example, for a round to require 5 matches, not only
must the winner win 4 of those matches, the 4th win
must occur during the 5th match of the round
(otherwise the round would have ended at 4
matches). We also must consider that each rouind of
competition could be won by one of the two players
in the competition.
Let us represent the two players as Black (B)
and White (W), where the letter and placement of
that letter represent a match win for that player.
Thus, BBWBB represents a 5match round with Black
winning 4 matches, including the first, second,
fourth, and fifth matches. Referring to the
previous paragraph, we note that BBBBW is NOT a
legitimate 5match round, for Black would be the
round winner after 4 matches.
Thus we need to count the number of ways each
player can win rounds of 4, 5, 6, and 7
matches.
First look at how Black can win. We start by
placing a B at the last match position, to assure
that Black wins the last match of each round.
For a 4match round, the record of matches won
must be
_ _ _ B,
where the first 3 matches must include 3 wins by
Black. This can be done in C(3,3) ways, which is
just 1.
For a 5match round, the record of matches won
must be
_ _ _ _ B,
where the first 4 matches must include 3 wins by
Black. This can be done in C(4,3) ways.
For a 6match round, the record of matches won
must be
_ _ _ _ _ B,
where the first 5 matches must include 3 wins by
Black. This can be done in C(5,3) ways.
For a 7match round, the record of matches won
must be
_ _ _ _ _ _ B,
where the first 6 matches must include 3 wins by
Black. This can be done in C(6,3) ways.
So for Black to win a round, there are
C(3,3)+C(4,3)+C(5,3)+C(6,3) ways. The same
reasoning can be used to show there are
C(3,3)+C(4,3)+C(5,3)+C(6,3) ways for White to win a
round.
Therefore, the total number of possible matches
is 2*[C(3,3)+C(4,3)+C(5,3)+C(6,3)]. Of
these, 2*[C(6,3)] require exactly 7
matches.
The desired fraction, then, is just
(2*[C(6,3)]) /
(2*[C(3,3)+C(4,3)+C(5,3)+C(6,3)])
or
C(6,3) /
([C(3,3)+C(4,3)+C(5,3)+C(6,3)]).


