1.
|
Respond to each of these questions by
placing your solution in the blank. While you may show steps
leading to your solution, you do not need to generate
written explanations for questions (a) through (e).
a. There are 6 ways to complete Task A and 10
ways to complete Task B. Assume that Task A and
Task B are independent events that share no common
elements.
(i) How many unique ways exist to complete Task
A or Task B?
(ii) How many unique ways exist to complete Task
A and then Task B?
|
b. Single copies of the digits
0,1,2,3,4,5,6,7,8, and 9 are to be arranged in a
single line. How many unique arrangements are there
for these digits?
|
c. How many distinct arrangements exist for the
letters in the word SENSELESSNESS?
Solution:
(13!) / (6!4!2!1!)
|
|
d. How many unique ways exist to arrange 10
pennies in a line such that 6 of them are heads
up?
|
e. Given an unlimited supply of letters M, A,
and D to choose from, how many unique 10-letter
sets can be created that contain at least 3 Ds?
|
|
|
2.
|
Respond to each of these questions by
placing your solution in the blank. While you may show steps
leading to your solution, you do not need to generate
written explanations for questions (a) through (e).
a. A recursive relationship has first term t(1)
= -4 with t(n) = -2t(n-1)+ 3. Determine the value
of t(4).
|
b. Jan had to answer the following question:
Julie's Eastside Eatery
serves three different sandwiches: a cheese
sandwich that sells for $2, a deli sandwich
that sells for $4, and a deluxe veggie
sandwich for $5. How many ways are there to
spend $16 for sandwiches at Julie's?
To answer the question, Jan created a generating
function that, when expanded, included the
following terms:
What answer did Jan provide, based on the
expansion shown here?
|
c. State the explicit formula for the number of
derangements of n distinct items.
Solution:
D(n) = n!*( 1/0! - 1/1! + 1/2! - 1/3! + .
. . + (/1)^n/n! )
|
|
d. Study this completed difference table:
x
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
f(x)
|
3
|
15
|
75
|
243
|
603
|
1263
|
2355
|
|
D1 --->
|
12
|
60
|
168
|
360
|
660
|
1092
|
|
D2 --->
|
48
|
108
|
192
|
300
|
432
|
|
D3 --->
|
60
|
84
|
108
|
132
|
|
D4 --->
|
24
|
24
|
24
|
|
D5--->
|
0
|
0
|
|
If we assume there exists a polynomial function
that best represents the relationship between x and
f(x), what is the degree of that polynomial?
|
e. Replace a, b, and c in C(21,a) = C(b,9) +
C(c,10) to correctly illustrate Pascal's
Formula.
Solution:
a = 10, b = 20, c = 20
|
|
|
|
3.
|
Respond to each question below by placing
your solution in the blank. While you may show steps leading
to your solution, you do not need to generate written
explanations for questions (a) through (e) on this page. (2
points each)
a. At Blaise's Bistro, the Friday night special
is Pizza! For $6.95 plus tax, patrons choose one of
12 different pre-made pizzas and one of 8 different
beverages. No additions or substitutions are
allowed for this price. How many different $6.95
pizza/beverage options are there?
|
b. Eighteen (18) donuts are to be placed in a
single line on a serving tray. Among the 18 donuts,
there are 4 identical jelly donuts, 6 identical
chocolate donuts, and 8 identical cream-filled
donuts. How many unique arrangements exist for
these 18 donuts?
Solution:
(18!) / (4!6!8!)
|
|
c. One version of the current automobile license
plates issued in Minnesota shows three letters
followed by a three-digit number. If no letter or
digit may be repeated, how many unique license
plates of this format can be created?
Solution:
P(26,3) * P(10,3)
|
|
d. A group of 15 people are to be separated into
three rooms called the Blue Room, the Green Room,
and the White Room. If there are no restrictions on
how many people go in each room, and we are only
concerned with the number of people in each room,
how many ways can the separation occur?
|
e. Pauline works 10 blocks west and 12 blocks
south of her apartment. All streets from her
apartment to her workplace are laid out in a
rectangular grid, and all of them are available for
walking. On her walk to work, Pauline stops at an
ATM that is located 3 blocks west and 5 blocks
south of her apartment. On her way home from work,
Pauline stops at People's Produce, located 7 blocks
north and 3 blocks east of her workplace. If she
walks 22 blocks from her apartment to work and 22
blocks from work to her apartment, how many
different round-trip paths are possible for
Pauline, given the stops she makes along the
way?
Solution:
C(8,3) * C(14,7) * C(10,3) *
C(12,5)
|
|
|
|
4.
|
Consider the expansion of (p + h + a + n +
t + o + m)^666.
a. Determine the number of uncollected terms in
the expansion. (2 points)
|
b. Determine the number of collected terms in
the expansion. (2 points)
Solution:
C(666+7-1,7-1) = C(672,6)
|
|
c. Determine the coefficient C for the collected
term C*p^111*h^222*n^333. (3 points)
Solution::
(666!)
/ (111!222!333!)
|
|
d. How many unique collected terms in the
expansion are of the form K*x^r*y^s*z^t, where x,
y, and z are distinct elements from the set
{p,h,a,n,t,o,m}? (3 points)
Solution:
C(7,3) * C(665,2)
First,
choose three distinct letters from
{p,h,a,n,t,o,m}. This can be done in
C(7,3) ways. Next, determine the number of
ways for r+s+t = 666, where r, s, and t
must all be positive integers (if 0, the
factor would not appear within a collected
term). This can be done in C(666-1,3-1) =
C(665,2) ways.
|
|
|
|
5.
|
A public opinion poll of 1400 college
students shows that
- 675 are females
- 682 range from 20 to 21 years old
- 684 are in extra-curricular activities
- 195 are females and are from 20 to 21 years old
- 467 are females in extra-curricular activities
- 318 are in extra-curricular activities and range in
age from 20 to 21 years
- 165 are females in extra-curricular activities and
range in age from 20 to 21 years
The Venn diagram here was created using the information
above, starting with the last bullet and working up the
list.
a. In this group of 1400 college students, how
many were males who are not aged 20 or 21, and who
are not in extra-curricular activities? (4
points)
|
b. In this group of 1400 college students, how
many females not involved in extra-curricular
activities range in age from 20 to 21 years? (3
points)
|
c. In this group of 1400 college students, how
many males not involved in extra-curricular
activities were questioned? (3 points)
Solution:
334 + 174 = 508
|
|
|
|
6.
|
The set of letters {D,D,D,E,E,E,E,F,F} is
to be used to create subsets with k elements in them.
a.State the range of values for k that is
possible for this situation. (2 points)
Solution:
k is between 0 and 9,
inclusive
|
|
b. How many subsets in all can be created? (2
points)
|
c. Create a generating function that can be used
to determine the number of 6-element subsets that
will have at least one E and at least two Ds. Show
the factors of the generating function but do not
expand the expression. Explain what each factor
represents within the context of this problem. (3
points)
Solution:
(x^2 + x^3) * (x + x^2 + x^3 + x^4) * (1 +
x + x^2)
The
first factor represents options for
choosing Ds, as you must have 2 but can
have no more than the 3 that are
available. The second factor represents
options for Es (from 1 to 4 of these) and
the third factor options for Fs (none, 1,
or at most 2 Fs).
|
|
d. Explain what you would do with this
generating function in order to determine the
number of 6-element subsets that will have at least
one E and at least two Ds. (3 points)
Solution:
Expand the generating function, collect
like terms, and read off the coefficient
of the term with x^6 as a
factor.
|
|
|
|
7.
|
Abby leads cryptography workshops at a
local university and consults for the government when not
teaching. She used a recent consulting case in one of her
workshops. The government had intercepted a diplomatic pouch
that contained a CD and hired Abby to analyze it when they
discovered it contained code words.
The CD contained a long list of 4-character code words.
Abby determined that:
- (1) Each code word was created from a set of 36
characters that included letters of the alphabet
(a,b,c,
,x,y,z) and the ten digits
(0,1,2,3,4,5,6,7,8,9).
- (2) A code word could contain either letters or
digits or both letters and digits.
- (3) In any one code word, no character appeared
more than once.
- (4) The CD list contained 1.5 million code
words.
a. Generate an argument to justify that the list
of code words must contain one or more duplicate
code words, or provide evidence to the contrary. (5
points)
Solution:
Begin by determining how many different
code words are possible, given the
provided information. This is P(36,4) or
1,413,720 different words. But the list
has 1,500,000 entries in it, so by the
Pigeonhole Principle, there must be at
least one code word
duplicated.
|
|
b. Will your argument hold if item (3) above is
changed to say that characters can be repeated
within a code word? Explain. (5 points)
Solution:
No, it won't. Now there are 36^4 possible
words, or 1,679,616. So the list of
1,500,000 words could be a list with no
duplicate words.
|
|
|
|
8.
|
A company with the trade name MOBILES has a
website display with the letters of its name, "MOBILES,"
splashed across the top of its welcome page.
MOBILES
A solid color is used for each letter in the name, but
the colors may be repeated. On one particular day, for
example, the colors of the letters might be blue, red,
green, yellow, black, blue, and red, respectively. The
company wishes to use a different color scheme for the
MOBILES name on the website for each of the days in the 100
years that comprise the 21st century.
Determine the minimum number of different colors that are
required for this task.
Solution:
There are approximately 365 * 100 + 25 = 36,525
days in the 21st century, roughtly accounting for a
leap year every four years. Therefore, we need at
least 36,525 different color schemes. To solve
this, we seek the smallest value k such that
k*k*k*k*k*k*k is at least 36,525, because we will
have k choices for each of the 7 letters in the
word MOBILES. By guess and test, we see that k = 5
colors is the smallest value that satisfies this
requirement.
|
|
|
9.
|
A theatrical producer intends to invest
$250,000 in one Broadway production each year so long as the
number of flops in which she has invested does not exceed
the number of hits. Assuming that each year's production can
be either a flop or a hit, and nothing else, determine the
number of sequences of flops and hits that result in the
producer continuing her investment strategy into the 7th
year of productions.
Solution: By
brute force or more sophiticated counting
techniques, there are 20 different scenarios that
would lead to the investment continuing into the
7th season.
|
|
|
10.
|
Two types of rectangles, each composed of
an array of squares, are to be arranged in a line. Here are
the shapes to be used:
- The left rectangle measures 3-by-2 and the
right rectangle measures 3-by-1.
- The arrangement to be created is to have 3
rows and n columns. One or more of the
rectangles may be rotated 90º degrees when
creating a line-up.
|
|
Here are a few examples. Note that the middle two figures
show the same end result, a 3-by-2 arrangement, created two
different ways. The first is created using a 3-by-2
rectangle and the second using two 3-by-1 rectangles. Also,
note that the right-most figure, a 3-by-4 arrangement, has
components that were rotated from their original
perspective.
Your task is to explore this situation and create a
recursive relationship A(n) to describe the number of unique
3-by-n arrangements that can be created.
Solution:
A(n) = 3*A(n-3) + A(n-2) + A(n-1), with A(1) = 1,
A(2) = 2, and A(3) = 6.
|
|
|
BONUS!
|
In the May 1996 issue of the
Mathematics Teacher (p 368), R. S. Tiberio of Wellesley (MA)
High School shared the following student discovery:
Your task: Justify that this relationship will hold in
general, or, alternatively, show that the result cannot be
generalized to all of Pascal's triangle.
Solution: By
brute-force symbolic manipulation we can show
that
C(n,k-2) +
C(n,k-1) + C(n,k) - [ C(n-3,k-3) + C(n-2,k-3) +
C(n-1,k-3) ] - [ C(n-3,k-2) + C(n-2,k-1) +
C(n-1,k-1) ] = C(n-2,k-2) + C(n-1,k-2) +
C(n-1,k-1).
This is left
as an exercise for you!
A
less-symbolically intense method is to replace
"positions" within the relationship with variables
and relate them using Pascal's Formula and other
known relationships.
|
|
|