• 0

# 3_4_Problem_Set

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