MODULE
THREE
PROBLEM
SET
1
Directions:
Type
your
solutions
into
this
document
and
be
sure
to
show
all
stepsfor
arriving
at
your
solution.
Just
giving
a
final
number
may
not
receive
full
credit.
P
ROBLEM
1
A
125-page
document
is
being
printed
by
five
printers.
Each
page
will
be
printed
exactly
once.
(a)
Suppose
that
there
are
no
restrictions
on
how
many
pages
a
printer
can
print.
How
many
ways
are
there
for
the
125
pages
to
be
assigned
to
the
five
printers?
One
possible
combination:
printer
A
prints
out
pages
2-50,
printer
B
prints
out
pages
1
and
51-60,
printer
C
prints
out
61-80
and
86-90,
printer
D
prints
out
pages
81-85
and
91-100,
and
printer
E
prints
out
pages
101-
125.
Page
1
=
5
options
Page
2
=
5
options
Page
3
=
5
options,
and
so
on...
Total
number
of
ways
to
assign
125
pages
to
five
printers
=
5*5*5*.
.
*5
(125times)
So
total
ways
=
5
125
(b)
Suppose
the
first
and
the
last
page
of
the
document
must
be
printed
in
color,
and
only
two
printers
are
able
to
print
in
color.
The
two
color
print-
ers
can
also
print
black
and
white.
How
many
ways
are
there
for
the
125
pages
to
be
assigned
to
the
five
printers?
Total
ways
=
5
123
For
the
first
and
last
pages,
there
are
2
printers
available
so
2
2
=
4
So
total
ways
=
(5
123
)
∗
4
(c)
Suppose
that
all
the
pages
are
black
and
white,
but
each
group
of
25
con-
secutive pages (1-25, 26-50, 51-75, 76-100, 101-125) must be assigned
to the
same
printer.
Each
printer
can
be
assigned
0,
25,
50,
75,
100,
or
125
pages
to
print.
How
many
ways
are
there
for
the
125
pages
to
be
assigned
to
the
five
printers?
5
∗
5
∗
5
∗
5
∗
5
=
5
5
=
3125
P
ROBLEM
2
Ten kids line up for recess. The names of the kids are:
{
Alex,
Bobby,
Cathy,
Dave,
Emy,
Frank,
George,
Homa,
Ian,
Jim
}
.
Let
S
be
the
set
of
all
possible
ways
to
line
up
the
kids.
For
example,
one
ordermight
be:
(Frank,
George,
Homa,
Jim,
Alex,
Dave,
Cathy,
Emy,
Ian,
Bobby)
The
names
are
listed
in
order
from
left
to
right,
so
Frank
is
at
the
front
of
theline
and
Bobby
is
at
the
end
of
the
line.
Let
T
be
the
set
of
all
possible
ways
to
line
up
the
kids
in
which
George
is
ahead
of
Dave
in
the
line.
Note
that
George
does
not
have
to
be
immediately
ahead
of
Dave.
For
example,
the
ordering
shown
above
is
an
element
in
T.
Now
define
a
function
f
whose
domain
is
S
and
whose
target
is
T
.
Let
x
be
an
element
of
S,
so
x
is
one
possible
way
to
order
the
kids.
If
George
is
ahead
of
Dave
in
the
ordering
x,
then
f
(x)
=
x.
If
Dave
is
ahead
of
George
in
x,
then
f
(x)
is
the
ordering
that
is
the
same
as
x,
except
that
Dave
and
George
have
swapped
places.
(a)
What
is
the
output
of
f
on
the
following
input?
(Frank,
George,
Homa,
Jim,
Alex,
Dave,
Cathy,
Emy,
Ian,
Bobby)
It
would
be
the
same.
Frank,
George,
Homa,
Jim,
Alex,
Dave,
Cathy,Emy,
Ian,
Bobby.
(b)
What
is
the
output
of
f
on
the
following
input?
(Emy,
Ian,
Dave,
Homa,
Jim,
Alex,
Bobby,
Frank,
George,
Cathy)
Dave
and
George
need
to
swap
places.
So,
Emy,
Ian,
George,
Homa,
Jim,
Alex,
Bobby,
Frank,
Dave,
Cathy
(c)
Is
the
function
f
a
k-to-1
correspondence
for
some
positive
integer
k?
If
so,
for
what
value
of
k?
Justify
your
answer.
Half
of
the
arrangements
will
be
George
ahead
of
Dave,
the
other
halfDave
ahead
of
George.
Where Dave is ahead, the output will be from the rest of the e e e half where
they’ve swapped places.
2
to
1
function
where
k
=
2.
(d)
There
are
3628800
ways
to
line
up
the
10
kids
with
no
restrictions
on
who
comes
before
whom.
That
is,
|
S
|
=
3628800.
Use
this
fact
and
the
answer
to
the
previous
question
to
determine
|
T
|
.
There
are
e
3628800
e
total
ways
e
to
arrange
e
10
e
kids,
so
|
S
e
=
3628800
And
in
these
total
ways,
half
the
ways
will
have
George
ahead
of
Dave
andin
the
other
half
Dave
ahead
of
George
We
know
T
is
an
arrangement
where
George
is
ahead
of
Dave,
so
half
the
total
arrangements
|
T
|
=
3628800/2
=
1814400
P
ROBLEM
2
Consider
the
following
definitions
for
sets
of
characters:
•
Digits
=
{
0,
1,
2,
3,
4,
5,
6,
7,
8,
9
}
•
Letters
=
{
a,
b,
c,
d,
e,
f,
g,
h,
i,
j,
k,
l,
m,
n,
o,
p,
q,
r,
s,
t,
u,
v,
w,
x,
y,
z
}
•
Special
characters
=
{∗
,
&,
$,
#
}
Compute
the
number
of
passwords
that
satisfy
the
given
constraints.
(i)
Strings
of
length
7.
Characters
can
be
special
characters,
digits,
or
letters,with
no
repeated
characters.
Total
number
of
characters
=
40
No.
of
ways
to
arrange
n
objects
taken
r
at
a
time
without
repetition
isP(n,r).
P(40,7)
=
40!
(33)!
(ii)
Strings
of
length
6.
Characters
can
be
special
characters,
digits,
or
letters,
with
no
repeated
characters.
The
first
character
can
not
be
a
special
char-
acter.
There
are
4
special
characters
and
since
the
e
first
character
cannot
be
aspecial
character,
we
get
40
-
4
=
36.
Remaining
5
characters
to
be
filled
from
39
other
characters.
=
(36)
P(39,
5)
=
(36)
(39)!
(34)!
P
ROBLEM
4
A
group
of
four
friends
goes
to
a
restaurant
for
dinner.
The
restaurant
offers
12different
main
dishes.
(i)
Suppose
that
the
group
collectively
orders
four
different
dishes
to
share.
The
waiter
just
needs
to
place
all
four
dishes
in
the
center
of
the
table.How
many
different
possible
orders
are
there
for
the
group?
Group
orders
4
different
dishes,
so
12
different
dishes.
Selecting
4
dishes
from
12
dishes
but
all
4
are
different.
12
c1 e
∗
e e e e
11
c1
∗
10
c1 e
∗
e e e e e
9
c1
e e
is
e
total
number
e
of
possible
orders.
=
12
∗
e
11
∗
10
∗
e e e
9
=
11,880
(ii)
Suppose
that
each
individual
orders
a
main
course.
The
waiter
must
re-
member
who
ordered
which
dish
as
part
of
the
order.
It’s
possible
for
more
than one person to order the same dish. How many different possible
orders
are
there
for
the
group?
Ea. person orders a dish and more than e one e person e can e order e the e e e
same dish.
12
c1 e
∗
e e
12
c1
∗
e e e e
12
c1
∗
e e
12
c1 e e
is
e
total
number
of
possible
orders.
=
12
∗
e
12
∗
e
12
∗
e e e
12
=
20,736
possible
orders.
How
many
different
passwords
are
there
that
contain
only
digits
and
lower-
case
letters
and
satisfy
the
given
restrictions?
(iii)
Length
is
7
and
the
password
must
contain
at
least
one
digit.
We
have
10
digits
and
26
lowercase
letters.
So,
36
total
characters.All
possible
pass
∗
wor
∗
ds:
e
3
∗
6
e e
∗
36
e
∗
36
e
∗
e e
36
36
e
36
e e
36
All
e
passwords
e e e e
with
e
letters
e e e e
only:
e
2
∗
6
e e
2
∗
6
e e
2
∗
6
e e
2
∗
6
e e
2
∗
6
2
∗
6
26No. e of passwords with at least 1 digit: −(36)7
(26)7
=
70332353920
=
7.033235392
*
10
10
(iv)
Length
is
7
and
the
password
must
contain
at
least
one
digit
and
at
leastone
letter.
Same
as
the
above
except
we
also
subtract
total
number
of
passwords
withdigits
only.
=
(36)
7
−
(26)
7
−
(10)
7
P
ROBLEM
5
A
university
offers
a
Calculus
class,
a
Sociology
class,
and
a
Spanish
class.
Youare
given
data
below
about
two
groups
of
students.
(i)
Group
1
contains
170
students,
all
of
whom
have
taken
at
least
one
of
the
three
courses
listed
above.
Of
these,
61
students
have
taken
Calculus,
78
have
taken
Sociology,
and
72
have
taken
Spanish.
15
have
taken
both
Cal-
culus
and
Sociology,
20
have
taken
both
Calculus
and
Spanish,
and
13
have
taken
both
Sociology
and
Spanish.
How
many
students
have
taken
all
three
classes?
A:
students
from
group
A
who
have
taken
Math
2A.
B:
students
from
group
A
who
have
taken
Math
2B.
C:
students
from
group
A
who
have
taken
Math
2C.
According
to
the
information
given
in
the
problem:
|A ∪ B ∪ C| = 157.|A| = 51, |B| = 80, and|C| = 70.|A ∩ B| = 15, |A ∩ C|
=20,
and
|
B
∩
C
|
=
13.
According
to
the
principle
of
inclusion-exclusion:
157
=
51
+
80
+
70
−
15
−
20
−
13
+
|
A
∩
B
∩
C
|
=
153
+
|
A
∩
B
∩
C
|
Therefore |A ∩ B ∩ C| = 4.
(ii)
You
are
given
the
following
data
about
Group
2.
32
students
have
taken
Calculus,
22
have
taken
Sociology,
and
16
have
taken
Spanish.
10
have
taken
both
Calculus
and
Sociology,
8
have
taken
both
Calculus
and
Span-
ish,
and
11
have
taken
both
Sociology
and
Spanish.
5
students
have
taken
all
three
courses
while
15
students
have
taken
none
of
the
courses.
How
many
students
are
in
Group
2?
|
A
|
=
28,
|
B
|
=
28,
|
C
|
=
25.
|
A
∩
B
|
=
11,
|
A
∩
C
|
=
9,
|
B
∩
C
|
=
10.
|
A
∩
B
∩
C
|
=
3.
A
∪
B
∪
C
|
=
|
A
|
+
|
B
|
+
|
C
|−|
A
∩
B
|
−|
A
∩
C
|
−|
B
∩
C
|
+
|
A
∩
B
∩
C
|
.
=
28
+
28
+
25
-
11
-
9
-
10
+
3
=
=
54
P
ROBLEM
6
N(S)
N(S)
2
A
coin
is
flipped
five
times.
For
each
of
the
events
described
below,
express
the
event
as
a
set
in
roster
notation.
Each
outcome
is
written
as
a
string
of
length
5
from
{
H,
T
}
,
such
as
HHHTH
.
Assuming
the
coin
is
a
fair
coin,
give
the
proba-
bility
of
each
event.
(a)
The
first
and
last
flips
come
up
heads.
S
=
HHHH,HHHT,HHTH,HTHH,THHH,HHTT,HTTH,HTHT,
THTH,TTHH,HTTT,TTTH,TTTT,THHT,TTHT,THTT
N(S)
=
2
4
=
16
(b)
There
are
at
least
two
consecutive
flips
that
come
up
heads.
B
=
HHHH,HHHT,HHTH,HTHH,HHTT,THHH,THHT,TTHH
N(B)
=
8
P(B)
=
N(B)
8
16
=
0.5
(c)
The
first
flip
comes
up
tails
and
there
are
at
least
two
consecutive
flips
thatcome
up
heads.
C
=
HHHH,TTTT
N(C)
=
2
P(C)
=
N(C)
=
16
=
0.125
=
P
ROBLEM
7
= +
2
An
editor
has
a
stack
of
k
documents
to
review.
The
order
in
which
the
doc-
uments
are
e
reviewed
e
is
e
random
e
with
e
each
e
ordering
e
being
e
equally
e
likely.
e
Of
thek
documents
to
review,
two
are
named
“Relaxation
Through
Mathematics”
and
“The
Joy
of
Calculus.”
Give
an
expression
for
each
of
the
probabilities
below
as
a
function
of
k.
Simplify
your
final
expression
as
much
as
possible
so
that
your
answer
does
not
include
any
expressions
in
the
form
a .)
b
(a)
What
is
the
probability
that
“Relaxation
Through
Mathematics”
is
first
toreview?
Documents
are
viewed
randomly,
so:
1
c
1
k
c
1
1
k
(b)
What
e
is
the
probability
that
“Relaxation
e
Through
Mathematics”
and
“TheJ
oy
of
Calculus”
e
are
next
e
to
e
each
other
in
the
e
stack?
=
P(relax
thru
math
+
the
joy)
+
P(the
joy
+
relax
thru
math)
1
*
1
e
+
1 *
1
k
k
k k
1 1
k
2
k
2
=
k
2
=
