Discrete Mathematics
5.1 Define a sequence as follows.
,
,
…
for
a) Find the following: (0 points)
b) What is the general formula for ? (3 points)
c) Use regular (not strong) mathematical induction to prove that your formula is correct. (7 points)
5.2 (10 points) The Tribonacci sequence is defined by , for . Use strong induction to prove that for all n.
A3/3.1 Describe a non-recursive algorithm that takes a list of integers and finds the index of the last even number in the list. If there is no even number on the list, return . Write your answer in pseudo-code or any well-known procedural language like Python, Java, C++, …. (5 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.
E.g. For the list = 5, 6, 7, 8, 9 your program should return 4 because is the last even number on the list.
procedure
Index_of_Last_Even (integers)
8.3 (7.3) Recall the Fibonacci numbers we defined in class (here denoted by ),
, , for
One could prove by induction that the following relationships hold for the Fibonacci numbers.
a) Use the given recursions to compute and . Show your work. (2 points)
b) Write a recursive algorithm in pseudo-code or any well-known procedural language like Python, Java, C++, &c to compute based on the above recurrences. (8 points)
procedure
Fib()
3.2/3.2 (2.5 points each)
a) Find C and k to show that is
b) True or False?: is
If true, find C and k to show this. If false, explain why.
c) True or False?: is
If true, find C and k to show this. If false, explain why.
d) True or False?: is
If true, find C and k to show this. If false, explain why.
3.3 Give a big-Theta estimate for the number of additions in the following algorithm. Express your answer in the form where (2.5 points each)
a)
procedure
p(n)
i = 1
while (i < n):
i = i *2
return
i
This algorithm is
(Write your answer in the parentheses above)
b)
procedure
p(n)
i = 1
while (i < n):
j = 1
while (j < n):
j = j + 2
i = i + 1
return
i
This algorithm is
(Write your answer in the parentheses above)
8.3 Consider the procedure T given below.
procedure
T (n: positive integer)
if
n < 2:
return 1
else:
for
i = 1 to
n:
for
j = 1 to
n:
return
Let be the number of additions in the procedure for an input of n and note that satisfies a recurrence relation of the form.
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
Given , then
is
This algorithm is
(Write your answer in the parentheses above)
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)
6.4/5.4 Assuming , prove that .
Hints: a) Work with instead.
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:
6.2 Consider the first 250 Fibonacci numbers
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
Exam#2: Solution
5.1 Prove by mathematical induction that
1 1 1
1
… 1
2 4 2
2
n n
(5 points)
1 1
1 1
1
2 2
Assume
1 1
1 1 1 1
… 1
2 4 2 2
n n
Then
1 1 1
1 1 1 1 1 1 1 2 1 2 1 1
… 1 1 1 1
2 4 2 2 2 2 2 2 2 2 2 2
n n n n n n n n n
QED
5.2 Using strong induction, prove that for every 8n , 3 5n a b for some nonnegative integers a and b. (5 points)
8 1 3 1b
9 3 3 0 5
10 0 3 2 5
Assume for all k n where 10k that 3 5k a b for some nonnegative
integers a and b.
Specifically, for 3k n , let a and b be such that 3 3 5n a b .
Then 1 3 5 3 5n a b a b where 1a a
QED
A3/3.1 Describe a non-recursive algorithm that takes a list of positive integers
1 2
, ,…,
n
a a a and finds the largest even
number on the list. Write your answer in pseudo-code or any well-known procedural language like Python, Java, C++,
….
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.
You may also assume that there will be at least one even number on the list. (5 points)
E.g. For the list
1 2 3 4 5
, , , ,a a a a a = 2, 3, 6, 5, 4 your program should return 6.
procedure Largest_Even (
1 2
, ,…, :
n
a a a positive integers)
largest_even = 0
for i = 1 to n
if
i
a is even and
i
a largest_even
index = i
largest_even =
i
a
return index
8.3 (7.3) Write a recursive algorithm to solve the same problem as above. (5 points)
You may assume that you have all of the primitive functions for lists: (first(L), rest(L), …)
procedure Largest_Even (L: list of integers)
if L is empty return 0
else if first(L) is even and first(L) > Largest_Even(rest(L))
return first(L)
else
return Largest_Even(rest(L))
8.3.3 Consider the procedure T given below.
procedure T (n: positive integer)
if n < 2 return 1
else for i = 1 to 5
x = x + 1
return 4 4 4n n nT T T
Let ( )f n be the number of additions in the procedure for an input of n and note that ( )f n satisfies a recurrence relation
of the form dncbnfanf / .
a) Determine the values of a, b, c, and d.
(4 points)
3a 4b 5c 0d
b) Apply The Master Theorem (given below) to T to determine its complexity. (1 points)
Master Theorem
Given dncbnfanf / , then
)(nf is
log
log
b
d d
d d
a d
n if a b
n n if a b
n if a b
Since
d
a b , the complexity is 4log 3n
6.5 a) How many ways to rearrange the letters AARDVARK ?
8!
3!2!
(2 points)
b) A donut store has 100 different types of donuts. You want to buy 1,000 donuts.
i) How many different ways can you do this?
10
99
99
(4 points)
ii) How many different ways can you do this if you need at least 5 of each type?
599
99
(5 points)
8.5 80 workers were interviewed for an electrical, painting or plumbing position. Every worker knew at least one skill.
45 workers knew electrical, 45 knew how to paint and 50 knew plumbing. 15 workers knew all three skills.
How many workers knew exactly two skills? (5 points)
# # # # # # # #
80 = 45 + 45 + 50 # # # 15
# # # 75
A B C A B C A B A C B C A B C
A B A C B C
A B A C B C
6.1/6.3 Emmy has 5 different fingernail polish colors (red, orange, yellow, green, blue) and wants to paint the nails on her
left hand. Red, orange and yellow are considered warm colors. Green and blue are considered cold colors. (2.5 points each)
a) How many different ways can she paint her first three nails?
3
5
b) How many ways can she paint her first three nails if she uses a different color for each one? 5 4 3
c) How many ways can she paint all of her nails if the first three nails must be a warm color and the last two must be a
cold color? She is allowed to repeat as many colors as she wants.
3 2
3 2
d) Same question as c), except she is not allowed to repeat any color? 3 2 1 2 1
7.1 A Discrete Math quiz has 10 True/False questions. An unprepared student guesses for each problem and has 50%
change of getting the problem right. (10 points)
a) What is the probability that the student gets all 10 questions correct?
10
1
2
b) What is the probability that the student gets exactly one question correct?
10
10
1
2
c) What is the probability that the student gets exactly 7 questions correct?
10
10
7
2
6.2 A certain class has 100 students. Recall that there are seven days in a week and 12 months in a year.
a) Find the largest number that can be used to fill in the blank to make a true statement. (2.5 points)
There are at least 15 students born on the same day of the week.
b) Find the largest number that can be used to fill in the blank to make a true statement. (2.5 points)
There are at least 9 students born in the same month.
6.4 (5.4) Prove that
n m n n k
m k k m k
(5 points)
Story: The left hand side is the number of ways of picking a committee of size
m and then an executive subcommittee of size k from n different students.
The right hand side is the number of ways to pick the executive committee of
size k from the n students, then fill out remaining m k committee members |
from the remaining n k students.
Proof from the definition:
! ! !
! ! ! ! ! ! !
!! !
! ! ! ! !! !
n m n m n
m k m n m m k k n m m k k
n n k n kn n
k m k n k k k m k n mm k n k m k
Exam2: Solution
5.1 Prove by mathematical induction that 0 1 11 2 2 2 … 2 1 2 1n nn n (5 points)
0 11 2 1 1 2 1
Assume 1 10 1 11 2 2 2 … 1 2 1 1 2 1n nn n
I.e. 0 1 2 11 2 2 2 … 1 2 2 2 1n nn n
Then 0 1 2 1 1 11 2 2 2 … 1 2 2 2 2 1 2n n n nn n n n
0 1 1 1 1
1
0 1 1 1
0 1 1 1
0 1 1 1
0 1 1
1 2 2 2 … 2 2 2 2 1
2
1 2 2 2 … 2 2 ( 2 ) 1
1 2 2 2 … 2 2 (2 2) 1
1 2 2 2 … 2 2 2( 1) 1
1 2 2 2 … 2 ( 1)2 1
n n
n
n
n n
n n
n n
n n
n n n
n n n
n n
n n
n n
5.2 Let
1 2 1 2
2, 4, 2 if 2
n n n
a a a a a n
. Use strong induction to prove that 2
n
n
a . (5 points)
1
1
2a ,
2
2
2a
Assume 2
k
k
a for all k n with 2k
So for 1k n ,
1
1
2
n
n
a
, and for 2k n ,
2
2
2
n
n
a
1 2 1 1 1
1 2 1 2
2, 4, 2 =2 2 2 2
2 2 2 2
n n n n n n
n n n
a a a a a
A3/3.1 Describe a non-recursive algorithm that takes a list of integers
1 2
, ,…,
n
a a a and finds the first location (i.e. index)
of the largest number on the list.. Write your answer in pseudo-code or any well-known procedural language like Python,
Java, C++, ….
E.g. For the list
1 2 3 4 5
, , , ,a a a a a = 2, 3, 6, 5, 6 your program should return 3 because
3
a , the third element of the list, is
the first time the largest number occurs.
procedure First_Time_Largest (
1 2
, ,…, :
n
a a a integers)
index = 1
largest_so_far =
1
a
for i = 2 to n
if
i
a largest_so_far
index = i
largest_so_far =
i
a
return index
8.3 (7.3) Write a recursive algorithm to compute the nth term of the recursively defined sequence
1 2 3 1 2 3
1, 2, 3, if 3
n n n n
a a a a a a a n
(5 points)
procedure nth-term ( n Z
)
if 1n
return 1
else if 2n
return 3
else
return nth-term(n-1)+nth-term(n-2)
6.1/6.3 A symphony orchestra has in its repertoire 30 Haydn pieces, 15 modern pieces, and 9 Beethoven pieces.
(2.5 points each)
a) How many ways can the orchestra play 3 pieces if they are allowed to play the same piece more than once?
3
54
b) How many ways can the orchestra play 3 pieces if they are not allowed to play the same piece more than
once? 54 53 52
c) How many ways can the orchestra play 3 pieces if they must play a Haydn piece first, a modern piece second
and a Beethoven piece last?
30 15 9
d) How many ways can the orchestra play 3 pieces if they must play one Haydn piece, one Beethoven piece and
one modern piece in any order?
3! 30 15 9
7.1 The lottery game 2by2 is played as follows:
First, you pick two different red numbers between 1 and 26 (inclusive) and two different white numbers between 1 and 26
(inclusive). Order does not matter. After all tickets have been purchased, two red numbers and two white numbers are
selected. The closer you are to having picked the correct numbers, the more money you will win!
E.g. You pick Red: 2, 25; White 3,10
The winning numbers are Red: 7,25; White: 2,25.
You matched one red number and no white numbers.
(10 points)
a) What is the probability that you match both red numbers and both white numbers?
1
26 25 26 25
b) What is the probability that you match either both red numbers or both white numbers, but not both?
Match both correct reds and pick two losing whites, or pick two losing
reds and both correct whites.
2 24 24 2
2 2 2 2
26 25 26 25
c) What is the probability that you match exactly one red number and no white numbers?
Pick one of the two winning red numbers, then one of the losing red
numbers, then pick two losing white numbers.
2 24 24
1 1 2
26 25 26 25
8.3 Consider the procedure T given below.
procedure T (n: positive integer)
if n < 2 return 1
else
for i = 1 to n
for j = 1 to n
x = x + 1
return 3 3 3 3n n n nT T T T
Let ( )f n be the number of additions in the procedure for an input of n and note that ( )f n satisfies a recurrence relation
of the form dncbnfanf / .
a) Determine the values of a, b, c, and d. (4 points)
4a 3b 1c 2d
b) Apply The Master Theorem (given below) to T to determine its complexity. (1 point)
Master Theorem
Given dncbnfanf / , then
)(nf is
log
log
b
d d
d d
a d
n if a b
n n if a b
n if a b
Since
d
a b , the complexity is 2n
6.5 a) How many ways to rearrange the letters BOOKKEEPERS ?
11!
2! 2! 3!
(2 points)
b) A bagel store has 500 different types of bagels. You want to buy 50,000 bagels.
i) How many different ways can you do this?
50,
499
499
(4 points)
ii) How many different ways can you do this if you need at least 10 of each type?
45, 499
499
(4 points)
8.5 Find # A B C given that # # # 10A B C , any two of A, B, C have 5 things in common, and there are
exactly two things in all three sets. (5 points)
# # # # # # # #
= 10 + 10 + 10 5 5 5 2
= 17
A B C A B C A B A C B C A B C
6.4 (5.4) Prove that
1
1
n n
k n
k k
(5 points)
Story: The left hand side is the number of ways to pick a committee of
size k from n students, then pick a president from the committee. The
right hand side the number of ways to pick the president first, then the
remaining 1k committee members from the remaining 1n students.
Definition:
! !
! ! 1 ! !
1 1 ! !
1 1 ! !1 ! 1 1 !
n n n
k k
k k n k k n k
n n n
n n
k k n kk n k
6.2 (5.2) An octopus is looking for socks to wear. In his dresser he has 20 red socks, 20 white socks and 20 blue
socks. Unfortunately, it is dark and he cannot distinguish between the different colors.
A human, having two feet, is happy with having two socks of the same color. An octopus, having 8 feet, is only
happy having 8 matching socks: 8 red, 8 white, or 8 blue.
a) How many socks must he pull out to guarantee he has eight that match? 22
It is possible to have 21 socks without 8 matching: 7 red, 7 white and 7
blue. Sock #22 must give 8 matching socks.
b) How many socks must he pull out to guarantee he has eight matching red socks or eight matching white
socks? 35
Worst case: All 20 blues, 7 reds and 7 whites = 34 socks.
Sock #35 will make a match.
c) How many socks must he pull out to guarantee he has eight matching red socks? 48
Worst case: 20 whites, 20 blues, 7 reds.
Sock #48 will match the 7 reds.