DISCRETE MATHEMATICS
RiverFlowsInYou
Math11.docxDiscrete Mathematics
…
a) Find the following: (0 points)
c) Use regular (not strong) mathematical induction to prove that your formula is correct. (7 points)
You may assume that you have a function even? built in to your language. even? will return TRUE for even numbers and FALSE for odd numbers.
One could prove by induction that the following relationships hold for the Fibonacci numbers.
3.2/3.2 (2.5 points each)
If true, find C and k to show this. If false, explain why.
If true, find C and k to show this. If false, explain why.
a) procedure p(n) i = 1 while (i < n): i = i *2 return i
b) procedure p(n) i = 1 while (i < n): j = 1 while (j < n): j = j + 2 i = i + 1 return i
8.3 Consider the procedure T given below.
a) Determine the values of a, b, c, and d. (4 points)
b) Apply The Master Theorem (given below) to T to determine its complexity. (1 point)
Master Theorem
6.1 (5.1) Hexadecimal numbers are made using the sixteen digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. (2.5 points each)
a) How many 5 digit hexadecimal numbers that do not start with the digit 0 and do not end with the digit 0?
b) How many 5 digit hexadecimal numbers start with a letter or end with a letter but not both?
c) How many 5 digit hexadecimal numbers start with a letter or end with a letter or both?
d) How many 5 digit hexadecimal numbers where all digits are consecutive? E.g. 01234, 89ABC, … Note: the numbers can’t “wrap-around”: EF0123 is not allowed.
6.3/5.3 A class has 21 students and is to be divided into indistinguishable groups. I.e, The two groups ABC and DEF are the same as the two groups DEF and ABC
a) How many ways to divide the students into three groups of 7? (2.5 points)
b) How many ways to divide the students into seven groups of 3? (2.5 points)
6.5/8.3 (5.5/7.3) You have 12 bones that you want to distribute to three dogs.
a) How many ways to do this? (3 points)
b) How many ways to do this if each dog gets at least 2 bones? (3 points)
c) How many ways to do this if each dog gets at most 5 bones? (4 points)
7.1 An urn contains 7 red balls, 7 white balls and 7 blue balls. 5 balls are randomly picked from the urn without replacement.
a) What is the probability that all of the balls are red? (2 points)
b) What is the probability that all of the balls are the same color? (2 points)
c) What is the probability that none of the balls are blue? (3 points)
d) What is the probability that 3 balls are red and 2 balls are white? (3 points)
b) You did some similar calculations in Calculus 2 using the Ratio Test.
c) Subtracting k from both sides of the inequality might be useful.
Extra Credit:
a) Fill in the blank with the largest possible integer that will make a true sentence. (1 point) There are at least __ that have the same remainder when divided by 11.
b) Fill in the blank with the largest possible integer that will make a true sentence. (1 point) There are at least 19 that have the same remainder when divided by ___.
312
1
aaa
=++
(
)
(
)
d
n
c
b
n
f
a
n
f
+
=
/
a
=
b
=
c
=
d
=
)
(
n
f
(
)
(
)
(
)
log
log
b
dd
dd
a
d
nifab
nnifab
nifab
q
q
q
ì
<
ï
ï
=
í
ï
>
ï
î
21
nk
<+
1
nn
kk
æöæö
<
ç÷ç÷
+
èøèø
4123
1
aaaa
=+++
1
n
k
n
k
æö
ç÷
+
èø
æö
ç÷
èø
1,1,2,3,5,...,78963258261317305092827389
43634332893686268675876375
121
1...
nn
aaaa
-
=++++
1
n
>
2
a
=
3
a
=
4
a
=
5
a
=
n
a
123
0,1,1
aaa
===
123
nnnn
aaaa
---
=++
3
n
>
2
n
n
a
<
12
,,...,
n
aaa
1
-
n
a
12345
,,,,
aaaaa
4
a
12
,,...,:
n
aaa
n
F
1
1
F
=
2
1
F
=
12
nnn
FFF
--
=+
2
n
>
(
)
22
211
21
2
nnn
nnnn
FFF
FFFF
--
+
=+
=-
34
,
FF
1
1
a
=
5
F
3
F
=
4
F
=
5
F
=
nZ
+
Î
2
n
n
(
)
!
On
3
n
(
)
2
n
O
(
)
log3
n
21
1
aa
=+
(
)
log(2)
n
O
(
)
log3
n
(
)
(
)
log2
n
O
(
)
()
fn
q
{
}
23
()1,log(),,log(),,,...,2,3,...,!,...,,..
.
nnn
fnnnnnnnnn
Î
(
)
q
1
xx
=+
(
)
(
)
(
)
(
)
(
)
(
)
3333
nnnn
TTTT
×××
êúêú
éùéù
êúêú
ëûëû
()
fn
